[AdditionalFile5439.zip](file://AdditionalFile5439.zip?type=additional_file)

#5439. 「ROI 2013 Day 1」乌拉尔冰球锦标赛

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

译自 ROI 2013 Day1 T1. Хоккей на Урале

为了推广冰球运动并提高乌拉尔地区冰球队的水平，组织了一场全乌拉尔锦标赛。共有 $N$ 支来自乌拉尔各城市的冰球队受邀参加本次锦标赛。

在前两轮比赛中，每支队伍各参加了一场比赛，但发现参赛队伍数量过多。锦标赛组织者决定只允许 $K$ 支队伍继续参加后续比赛，并且这 $K$ 支队伍中任意两支在头两轮比赛中都没有对阵过。

你需要编写一个程序，找到满足条件的 $K$ 支队伍组合，或者输出无法找到满足条件的组合的信息。如果存在多个符合条件的组合，可以输出任意一个。

输入格式

输入文件的第一行包含一个整数 $N$（$2 \leq N \leq 100000$，$N$ 为偶数），表示参赛队伍的数量。

接下来的 $N$ 行描述了所有已进行的比赛。每场比赛的描述包含两个不超过 $N$ 的自然数，表示参赛的两支队伍的编号。前 $N/2$ 行对应第一轮比赛，后 $N/2$ 行对应第二轮比赛。

最后一行包含一个整数 $K$ $(2 \leq K \leq N)$，表示需要选出的队伍数量。

保证每支队伍恰好参加了两次比赛：第一轮一次，第二轮一次。

输出格式

如果无法找到满足条件的组合，则输出唯一的数字 $0$；如果存在满足条件的组合，则输出 $K$ 个不同的数字，表示选出的队伍编号。

样例 1

输入

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

输出

1 4 3

样例 2

输入

4
1 2
3 4
2 1
4 3
3

输出

0

数据范围与提示

详细子任务附加限制及分值如下表所示：