히카리는 카이스트에 서식하는 거위들의 생태를 연구하는 학자이다. 그녀는 카이스트의 서식지에 존재하는 거위들의 둥지가 총 $N$개 있으며, 그 사이에는 거위들의 통행로가 총 $M$개 존재한다는 사실을 알아내었다. $M$개의 통행로는 각각 서로다른 두 둥지를 연결한다. 어떠한 두 통행로도 같은 쌍의 둥지를 연결하지 않는다.

히카리는 거위들의 생태를 조사하다가, 거위들의 토속 신앙에 대해서 알게 되었다! 히카리는 그들이 빛과 대립의 거위에 대한 신화를 믿는다는 사실을 알게 되었으며, 심지어 거위들이 이를 기리기 위한 신전 또한 존재함을 알게 되었다.

서로 다른 $N-2K+2$개의 거위들의 둥지 $P_1,P_2,\cdots,P_{N-2K+2}$가 빛의 신전이라는 것은, 임의의 $1\le i< N-2K+2$에 대해서 $P_i,P_{i+1}$ 사이에 통행로가 존재한다는 것이다. 이때 $K$는 거위들이 믿는 신성한 숫자이다.

서로 다른 $2K$개의 거위들의 둥지 $A_1,A_2,\cdots,A_K,B_1,B_2,\cdots,B_K$가 대립의 신전이라는 것은, 임의의 $1\le i\le K$와 $1\le j\le K$에 대해서 $A_i,B_j$ 사이에 통행로가 존재하지 않는다는 것이다.

히카리는 거위들의 생태를 연구하기 위해 빛의 신전과 대립의 신전 중 하나를 찾고자 한다. 히카리는 자신의 대학원생인 당신에게 빛의 신전과 대립의 신전 중 적어도 하나를 찾아내는 것을 요구했다. 히카리의 요구에 맞춰 빛의 신전과 대립의 신전 중 하나를 찾아보자. 빛의 신전과 대립의 신전 중 적어도 하나가 존재함을 증명할 수 있다.

제약 조건

• $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}$

부분문제

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

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

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

4. (40점) 추가 제약 조건 없음.

입력 형식

첫째 줄에 세 음이 아닌 정수 $N,M,K$가 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 걸쳐 통행로에 관한 정보가 주어진다. 이중 $i$번째 줄에는 두 양의 정수 $U_i,V_i$가 공백으로 구분되어 주어지는데, 이는 $i$번째 통행로가 $U_i$번 둥지와 $V_i$번 둥지를 잇는다는 것이다.

출력 형식

만약 빛의 신전을 발견하였다면 $1$을, 대립의 신전을 발견하였다면 $2$를 출력한다.

만약 빛의 신전을 발견하였다면, 이후 $N-2K+2$개의 양의 정수 $P_1,P_2,\cdots,P_{N-2K+2}$를 공백으로 구분하여 출력한다. 이는 빛의 신전을 구성하는 둥지들을 나타내야 한다.

만약 대립의 신전을 발견하였다면, 이후 두 줄에 걸쳐 각 줄마다 $K$개의 양의 정수를 공백으로 구분하여 출력한다. 이는 대립의 신전을 구성하는 둥지들을 나타내야 하며, 첫 번째 줄의 출력은 $A_1,A_2,\cdots,A_K$이고 두 번째 줄의 출력은 $B_1,B_2,\cdots,B_K$여야 한다.

예제

예제 1

입력

2 1 1
2 1

출력

1
1 2 

예제 2

입력

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

출력

2
6 8 
3 4