CF653E Bear and Forgotten Tree 2

树是一个包含 $n$ 个顶点和 $n-1$ 条边的连通无向图。顶点编号为 $1$ 到 $n$。 Limak 是一只小北极熊。他曾经拥有一棵有 $n$ 个顶点的树，但他把它弄丢了。不过他还记得一些关于这棵树的信息。 你得到了 $m$ 对顶点 $(a_{1},b_{1}),(a_{2},b_{2}),...,(a_{m},b_{m})$。Limak 记得对于每个 $i$，在他的树上，$a_{i}$ 和 $b_{i}$ 之间没有边。他还记得顶点 $1$ 恰好连接有 $k$ 条边（也就是说顶点 $1$ 的度为 $k$）。 是否可能存在一棵满足上述条件的树？请判断是否存在至少一棵满足条件的树。

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 3 \times 10^{5}$，$0 \le m \le \min{( n^2 ,3 \times 10^{5})}$，$0 \le k \le n-1$）——表示顶点数、禁止连边的顶点对数，以及顶点 $1$ 的度数。 接下来的 $m$ 行，每行包含两个不相等的整数 $a_{i}$ 和 $b_{i}$，表示第 $i$ 个禁止连边的顶点对（$1 \le a_{i}, b_{i} \le n, a_{i} \neq b_{i}$）。保证输入中每一对顶点最多只出现一次。

如果存在至少一棵满足条件的树，输出 "possible"（不带引号）；否则输出 "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$ 无法与其它任意顶点连接。这意味着不存在合适的树。 由 ChatGPT 5 翻译