P14552 [ROI 2013 Day1] 乌拉尔冰球赛

为了普及冰球运动并提高乌拉尔地区冰球队的技术水平，组织了一场全乌拉尔锦标赛。锦标赛邀请了来自乌拉尔各城市的 $N$ 支冰球队参加。 在前两轮比赛后，每支球队各进行了一场比赛，结果发现参赛队伍过多。锦标赛组织者决定只允许 $K$ 支球队继续参赛，且这些球队中任意两支在前两轮比赛中均未相遇。 需要编写一个程序，找出满足条件的 $K$ 支球队集合，或者输出无法实现的消息。如果存在多个符合条件的集合，只需找出其中任意一个。

输入文件的第一行包含一个数字 $N$（$2 \leqslant N \leqslant 100,000$，$N$ 为偶数）。 随后的 $N$ 行包含所有已进行比赛的描述。每场比赛的描述由两个不超过 $N$ 的自然数组成——表示参加比赛的球队编号。 前 $N/2$ 行对应第一轮的比赛，其余行对应第二轮的比赛。 输入文件的最后一行包含一个数字 $K$（$2 \leqslant K \leqslant N$）。 保证每支球队恰好进行了两场比赛：一场在第一轮，一场在第二轮。

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

### 评分 本题包含三个子任务。每个子任务的评分使用独立的测试组。仅当通过该组所有测试时，子任务的得分才会被计入。 #### 子任务 1 $N \leqslant 10$。 该子任务分值为 30 分。 #### 子任务 2 $N \leqslant 1000$。 该子任务分值为 30 分。 #### 子任务 3 $N \leqslant 100,000$。 该子任务分值为 40 分。