← 返回题目列表

Codeforces · 653/E

E. 熊与被遗忘的树 2

中文机器翻译题面 查看原题

树是由 n 个顶点和 n - 1 条边组成的连通无向图。顶点编号为 1 到 n。

Limak 是一只小北极熊。他曾经拥有一棵有 n 个顶点的树,但他失去了它。不过,他仍然记得有关那棵丢失的树的一些事情。

给定 m 对顶点 (a1, b1), (a2, b2), ..., (am, bm)。利马克记得,对于每个 i,ai 和 bi 之间没有边缘。他还记得顶点 1 恰好与 k 个边相关(其度数等于 k)。

利马克有可能正确记得所有事情吗?检查是否存在满足给定条件的树。

输入

输入的第一行包含三个整数 n、m 和 k ($$2 \leq n \leq 300 \, 000, \, 0 \leq m \leq \min(300 \, 000, \frac{n(n-1)}{2}), \, 1 \leq k \leq n - 1$$) — 中的顶点数分别是 Limak 树、禁止顶点对的数量和顶点 1 的度。

接下来 m 行的第 i 行包含两个不同的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi) - 第 i 对被禁止的整数。保证每对顶点在输入中最多出现一次。

输出

如果存在至少一棵满足给定条件的树,则打印“可能”(不带引号)。否则,打印“不可能”(不带引号)。

示例

输入 #1

5 4 2
1 2
2 3
4 2
4 1

输出 #1

possible

输入 #2

6 5 3
1 2
1 3
1 4
1 5
1 6

输出 #2

impossible

注意

在第一个样本中,有 n = 5 个顶点。顶点 1 的度数应为 k = 2。 对于具有边 1 - 5、5 - 2、1 - 3 和 3 - 4 的树,所有条件都满足。

在第二个示例中,Limak 记得不存在以下边:1 - 2、1 - 3、1 - 4、1 - 5 和 1 - 6。因此,顶点 1 无法连接到任何其他顶点,这意味着没有合适的树。