Hikari is a scholar who studies the ecology of geese inhabiting KAIST. She discovered that there are a total of $N$ nests of geese within KAIST, and that there are $M$ pathways connecting them. Each of the $M$ pathways connects two distinct nests. No two pathways connect the same pair of nests.

While studying the ecology of the geese, Hikari learned about their indigenous beliefs! She found that they believe in a myth about the Geese of Light and Conflict, and even that there exist temples built in their honor.

A sequence of $N-2K+2$ distinct nests $P_1, P_2, \cdots, P_{N-2K+2}$ is called a Temple of Light if, for every $1 \le i< N-2K+2$, there exists a pathway between $P_i$ and $P_{i+1}$. Here, $K$ is a sacred number believed by the geese.

A collection of $2K$ distinct nests $A_1, A_2, \cdots, A_K, B_1, B_2, \cdots, B_K$ is called a Temple of Conflict if, for every $1 \le i \le K$ and $1 \le j \le K$, there is no pathway between $A_i$ and $B_j$.

To further study the ecology of the geese, Hikari wants to find either a Temple of Light or a Temple of Conflict. She has asked you, her graduate student, to find at least one of them. Find either a Temple of Light or a Temple of Conflict that satisfies her request. It can be proven that at least one of them always exists.

Constraints

• $2\le N\le 100{,}000, 0\le M\le \min(200{,}000,\frac{N(N-1)}{2}), 1\le K\le \frac{N}{2}$

Subtasks

1. (20 points) $N\le 10$.

2. (10 points) $K=1$.

3. (30 points) $N,M\le 1{,}000$.

4. (40 points) No additional constraints.

Input

The first line contains three nonnegative integers $N, M, K$ separated by spaces.

Each of the next $M$ lines describes a pathway. The $i$-th line contains two positive integers $U_i, V_i$, separated by spaces, indicating that the $i$-th pathway connects nest $U_i$ and nest $V_i$.

Output

If you find a Temple of Light, output $1$. If you find a Temple of Conflict, output $2$.

If you find a Temple of Light, then output $N-2K+2$ positive integers $P_1, P_2, \cdots, P_{N-2K+2}$ separated by spaces, representing the nests that form the Temple of Light.

If you find a Temple of Conflict, then output two lines. Each line should contain $K$ positive integers separated by spaces. These represent the nests forming the Temple of Conflict, where the first line corresponds to $A_1, A_2, \cdots, A_K$ and the second line corresponds to $B_1, B_2, \cdots, B_K$.

Example

Example 1

Input

2 1 1
2 1

Output

1
1 2 

Example 2

Input

10 10 2
6 2
10 5
2 10
2 5
7 5
3 9
2 8
3 2
10 1
4 2

Output

2
6 8 
3 4