树是由 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 无法连接到任何其他顶点,这意味着没有合适的树。