Conference

A large scientific conference takes place in Nicosia. $N$ people attend it, and $K$ of them are scientists, numbered 1 through $K$. The other $N-K$ people are journalists. Each scientist makes exactly one invention, and no two inventions are the same. Call the invention of scientist $i$ invention $i$.

The conference runs for $M$ consecutive days, numbered 1 through $M$, and everyone attends every day. On each day exactly one meeting between two people takes place, and the two people tell each other about every invention they have already heard about or invented themselves. If $A$ knows the set of inventions $U$ and $B$ knows the set $V$ before the meeting, then after the meeting both know every invention in $U \cup V$.

Every scientist wants the invention to become public, so at least one journalist has to know about it by the end of the conference. A scientist creates the invention in the morning, before that day's meeting starts, so if the scientist meets someone on that day, the new invention is shared too.

Every scientist is extremely lazy and creates the invention on the latest day that still lets at least one journalist learn about it.

Write a program that reports three things.

1. For each scientist, the latest day on which the invention can be created.
2. The journalists who learn about at least one invention during the conference.
3. For each scientist, the first journalist who hears about that invention.

Answer parts 2 and 3 assuming every scientist creates the invention on the latest day found in part 1.

The first line contains the integers $N$, $M$, $K$ separated by spaces. ($1 \le K \le N \le 10^6$, $1 \le M \le 10^6$)

Each of the next $M$ lines contains two integers $i$, $j$, the two people who meet that day. ($1 \le i, j \le N$, $i \ne j$) The meetings are given in the order they take place, so the meeting on line $d$ happens on day $d$.

On the first line print $K$ integers separated by spaces. The $i$-th integer is the day on which scientist $i$ creates the invention. If no journalist can learn about it on any day, print -1 in that position instead.

On the second line print the number $x$ of journalists who learn about at least one invention, followed by their $x$ indices in increasing order. Here $x$ is at most $N-K$. If $x$ is 0, the second line contains only 0.

On the third line print $K$ integers separated by spaces. The $i$-th integer is the index of the first journalist who learns about the invention of scientist $i$. If no journalist learns about it, print -1 instead.

In the first example the latest day on which scientist 1 can create the invention is day 3. Creating it on day 4 tells only person 3, who is a scientist, and nobody else ever hears about it. Creating it on day 3 tells person 2 the same day, and on day 5 person 4, who is a journalist, hears about it from person 2.