Hockey in the Urals

Time limit1sMemory limit1024 MB

Summary

Given two perfect matchings on N teams, find K teams containing no matched pair from either round, or report that none exists.

Level: Medium7 of 10
Topics: Graph, Greedy, Implementation, Math
Solved: No attempts yet

Problem

To promote hockey in the Urals and raise the skill of its hockey teams, an All-Ural tournament was organized. $N$ hockey teams from cities of the Urals were invited to take part.

After the first two rounds, in each of which every team played one match, it turned out that there were too many teams. The organizers decided to admit to further participation only $K$ teams, no two of which had met in the first two rounds.

Write a program that finds a set of $K$ teams satisfying the conditions, or reports that this is impossible. If several suitable sets exist, find any one of them.

Input

The first line of the input file contains the number $N$ ( $2 \leqslant N \leqslant 100\,000$ , $N$ is even).

The next $N$ lines describe all the matches played. Each match description consists of two natural numbers not exceeding $N$ , the numbers of the teams that played the match. The first $N/2$ of them correspond to matches of the first round, and the rest to matches of the second round.

The last line of the input file contains one number $K$ ( $2 \leqslant K \leqslant N$ ).

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

Output

The output file must contain either the single number $0$ if no solution exists, or $K$ distinct numbers, the numbers of the selected teams.

Constraints

$N \leqslant 100\,000$

Examples2

Example 1
Input
```
6
1 2
3 5
4 6
2 3
4 5
1 6
3
```
Expected output
```
1 4 3
```
Example 2
Input
```
4
1 2
3 4
2 1
4 3
3
```
Expected output
```
0
```