13968번 - Conference 서브태스크스페셜 저지다국어

A big scientific conference takes place in Nicosia and we know that N people are going to attend it, but only K of them are scientists, each one of them about to make a great invention. The rest of them are journalists that will publish articles about what they witnessed at the conference. The conference takes place during M consecutive days and everyone attends it.

Of course, each scientist wants their invention to get publicity, so they want at least one journalist to know about it until the end of the conference. In every one of the M days exactly one meeting takes place between two people. In this meeting, they share knowledge about every invention that they have already heard or invented themselves. For example, if A and B are meeting, A knows about the inventions in the set U and B knows about the inventions in the set V, then after the meeting they will both know about all inventions in the union of U and V.

Note that every scientist will make exactly one invention throughout the whole conference and no two inventions are the same. Also, the people are numbered from 1 to N, days are numbered from 1 to M, and the scientists are 1, 2, ..., K.

Being extremely lazy, each scientist will create their invention in the latest day possible, so that at least one journalist can learn about it. In fact, each scientist will create their invention in the morning before the conference day starts, so if they meet with someone that day they will also tell them about their new invention.

You have three tasks:

1. For each scientist, find the last possible day of the conference that they can create their invention, so that at least one journalist will learn about it.
2. Find the journalists that learn about at least one invention throughout the conference.
3. For each scientist find the first journalist that hears about his invention.

In the first line the integers N, M, K (N, M ≤ 1 000 000) are given, separated by spaces. In each of the next M lines two integers i, j (i ≠ j) are given, which denote a meeting between i and j. The meetings are given in the order that they take place.

In the first line of the output K space-separated integers should be printed, the i-th of which will be the day that scientist i will make his invention. If no journalist can learn about their invention, print -1 instead for that specific scientist. In the second line there should be some integer x ≤ N - K followed by x numbers, which are exactly the journalists that learn about at least one invention, in increasing order of index. In the third line there should be K integers, the i-th of which is the first journalist that learns about i's invention. Again, print -1 instead if no journalist can learn about the invention of the corresponding scientist

The latest day scientist 1 can create his invention is day 3. If he creates it on day 4, only person 3 (who is a scientist) will learn about it and nobody else. On the other hand, if he creates it on day 3, person 2 will learn about it in the same day, and then person 4 (who is a journalist) will learn about it (from person 2) on day 5.