학회

니코시아에서 큰 학술 대회가 열린다. 참가자는 $N$명이고 그중 $K$명이 과학자다. 과학자는 1번부터 $K$번까지이고, 나머지 $N-K$명은 기자다. 과학자는 각자 발명을 정확히 하나씩 만들며, 서로 같은 발명은 없다. $i$번 과학자가 만드는 발명을 발명 $i$라고 하자.

대회는 $M$일 동안 이어지고 날에는 1일째부터 $M$일째까지 번호가 붙는다. 참가자는 모두 매일 대회에 나온다. 하루에 두 사람 사이의 만남이 정확히 한 번 일어나고, 만난 두 사람은 자기가 이미 들었거나 직접 만든 발명을 전부 서로 알려 준다. 만남 전에 $A$가 아는 발명의 집합이 $U$, $B$가 아는 집합이 $V$였다면 만남 뒤에는 둘 다 $U \cup V$의 발명을 안다.

과학자는 자기 발명이 세상에 알려지기를 바라므로 대회가 끝날 때까지 기자 중 적어도 한 명이 그 발명을 알게 되기를 원한다. 발명은 그날 아침, 그날의 만남이 시작되기 전에 만든다. 그래서 발명을 만든 날에 누군가와 만나면 새 발명까지 함께 알려 준다.

과학자는 모두 아주 게을러서, 기자 중 적어도 한 명이 발명을 알게 되는 조건을 지키는 한 가능한 가장 늦은 날에 발명을 만든다.

다음 세 가지를 구하는 프로그램을 작성하시오.

1. 과학자마다 발명을 만들 수 있는 가장 늦은 날
2. 대회 기간에 발명을 하나 이상 알게 되는 기자
3. 과학자마다 그 발명을 가장 먼저 알게 되는 기자

2번과 3번은 모든 과학자가 1번에서 구한 가장 늦은 날에 발명을 만든다고 보고 답한다.

첫째 줄에 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1 \le K \le N \le 10^6$, $1 \le M \le 10^6$)

다음 $M$개 줄에는 그날 만나는 두 사람의 번호 $i$, $j$가 주어진다. ($1 \le i, j \le N$, $i \ne j$) 만남은 일어나는 순서대로 주어지므로 $d$번째 줄에 적힌 만남이 $d$일째에 일어난다.

첫째 줄에 $K$개의 정수를 공백으로 구분해 출력한다. $i$번째 정수는 $i$번 과학자가 발명을 만드는 날이다. 어느 날에 만들어도 기자가 그 발명을 알 수 없다면 그 자리에는 -1을 출력한다.

둘째 줄에는 발명을 하나 이상 알게 되는 기자의 수 $x$를 먼저 출력하고, 이어서 그 기자의 번호를 커지는 순서로 $x$개 출력한다. $x$는 $N-K$ 이하다. $x$가 0이면 둘째 줄에는 0만 출력한다.

셋째 줄에 $K$개의 정수를 공백으로 구분해 출력한다. $i$번째 정수는 $i$번 과학자의 발명을 가장 먼저 알게 되는 기자의 번호다. 그 발명을 아는 기자가 없다면 -1을 출력한다.

첫 번째 예제에서 1번 과학자가 발명을 만들 수 있는 가장 늦은 날은 3일째다. 4일째에 만들면 과학자인 3번만 발명을 알게 되고 그 밖에는 아무도 알지 못한다. 3일째에 만들면 같은 날 2번이 발명을 알고, 5일째에 2번에게서 기자인 4번이 알게 된다.