CF653E.Bear and Forgotten Tree 2

A tree is a connected undirected graph consisting of n vertices and n  -  1 edges. Vertices are numbered 1 through n.

Limak is a little polar bear. He once had a tree with n vertices but he lost it. He still remembers something about the lost tree though.

You are given m pairs of vertices (_a_1, _b_1), (_a_2, _b_2), ..., (a__m, b__m). Limak remembers that for each i there was no edge between a__i and b__i. He also remembers that vertex 1 was incident to exactly k edges (its degree was equal to k).

Is it possible that Limak remembers everything correctly? Check whether there exists a tree satisfying the given conditions.

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

Limak 是一只小北极熊。他曾经拥有一棵含 $n$ 个顶点的树，但后来弄丢了。不过，他仍记得关于这棵丢失的树的一些信息。

你将得到 $m$ 对顶点 $(a_1,\,b_1),\,(a_2,\,b_2),\,\dots,\,(a_m,\,b_m)$。Limak 记得：对每个 $i$，顶点 $a_i$ 与 $b_i$ 之间没有边相连。他还记得顶点 $1$ 恰好与 $k$ 条边相邻（即其度数等于 $k$）。

Limak 所记得的信息是否可能全部正确？请判断是否存在一棵满足上述所有条件的树。

The first line of the input contains three integers n, m and k () — the number of vertices in Limak's tree, the number of forbidden pairs of vertices, and the degree of vertex 1, respectively.

The i-th of next m lines contains two distinct integers a__i and b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i) — the i-th pair that is forbidden. It's guaranteed that each pair of vertices will appear at most once in the input.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（），分别表示 Limak 的树中的顶点数、禁止的顶点对数量，以及顶点 1 的度数。

接下来的 $m$ 行中，第 $i$ 行包含两个互异的整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，且 $a_i \ne b_i$），表示第 $i$ 个被禁止的顶点对。保证输入中每对顶点至多出现一次。

Print "possible" (without quotes) if there exists at least one tree satisfying the given conditions. Otherwise, print "impossible" (without quotes).

如果存在至少一棵满足给定条件的树，则输出 "possible"（不带引号）；否则，输出 "impossible"（不带引号）。

In the first sample, there are n = 5 vertices. The degree of vertex 1 should be k = 2. All conditions are satisfied for a tree with edges 1 - 5, 5 - 2, 1 - 3 and 3 - 4.

In the second sample, Limak remembers that none of the following edges existed: 1 - 2, 1 - 3, 1 - 4, 1 - 5 and 1 - 6. Hence, vertex 1 couldn't be connected to any other vertex and it implies that there is no suitable tree.

在第一个样例中，共有 $n = 5$ 个顶点。顶点 1 的度数应为 $k = 2$。边集 $\{1\text{-}5,\ 5\text{-}2,\ 1\text{-}3,\ 3\text{-}4\}$ 构成的树满足所有条件。

在第二个样例中，Limak 记得以下边均不存在：$1\text{-}2$、$1\text{-}3$、$1\text{-}4$、$1\text{-}5$ 和 $1\text{-}6$。因此，顶点 1 无法与任何其他顶点相连，这意味着不存在满足条件的树。