题目描述

为了普及冰球运动并提高乌拉尔地区冰球队的技术水平，组织了一场全乌拉尔锦标赛。锦标赛邀请了来自乌拉尔各城市的 $N$ 支冰球队参加。

在前两轮比赛后，每支球队各进行了一场比赛，结果发现参赛队伍过多。锦标赛组织者决定只允许 $K$ 支球队继续参赛，且这些球队中任意两支在前两轮比赛中均未相遇。

需要编写一个程序，找出满足条件的 $K$ 支球队集合，或者输出无法实现的消息。如果存在多个符合条件的集合，只需找出其中任意一个。

输入格式

输入文件的第一行包含一个数字 $N$（$2 \leqslant N \leqslant 100,000$，$N$ 为偶数）。

随后的 $N$ 行包含所有已进行比赛的描述。每场比赛的描述由两个不超过 $N$ 的自然数组成——表示参加比赛的球队编号。 前 $N/2$ 行对应第一轮的比赛，其余行对应第二轮的比赛。

输入文件的最后一行包含一个数字 $K$（$2 \leqslant K \leqslant N$）。

保证每支球队恰好进行了两场比赛：一场在第一轮，一场在第二轮。

输出格式

输出文件应包含：如果无解，则仅输出一个数字 $0$；否则输出 $K$ 个不同的数字——所选球队的编号。

6
1 2
3 5
4 6
2 3
4 5
1 6
3

1 4 3

4
1 2
3 4
2 1
4 3
3

0

提示

评分

本题包含三个子任务。每个子任务的评分使用独立的测试组。仅当通过该组所有测试时，子任务的得分才会被计入。

子任务 1

$N \leqslant 10$。 该子任务分值为 30 分。

子任务 2

$N \leqslant 1000$。 该子任务分值为 30 分。

子任务 3

$N \leqslant 100,000$。 该子任务分值为 40 分。