favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Hockey in Ural

To promote hockey and to improve the skill of the Ural hockey teams, the Ural tournament was organised. n hockey teams from the cities of the Urals were invited to participate in the tournament.

After the first two rounds, where in each round each team played one match, it turned out that there were too many teams. The organisers of the tournament decided to allow only k teams to continue participation, no two of which have met in the first two rounds.

Write a program that finds a set of k teams that satisfies the conditions, or prints a message that this cannot be done. If there are several solutions, print any of them.


The first line contains number n (2n105, n is even). Next n lines give the description of all passed matches. The description of each match consists of two positive integers not greater than n - the numbers of the teams that played in the match. The first n / 2 of them correspond to the matches of the first round, the rest correspond to the matches of the second round.

The last line contains one integer k (2kn).

It is guaranteed that each team played exactly two matches: one in the first round and one in the second.


Print either a single number 0 if there is no solution, or k different numbers - the numbers of selected teams.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 2
3 5
4 6
2 3
4 5
1 6
Output example #1
1 4 3
Input example #2
1 2
3 4
2 1
4 3
Output example #2
Source 2013 XXV All Russia Informatics Olympiad, March 26, Problem A