朋友聚会
题目描述
在 ИOI5202 的举办地厂川有 个小镇，小镇之间通过 条路彼此相连，形成了一个树形结构。
这些小镇之间并不友好，具体而言，每个小镇都恰好仅存在另一个小镇，使得这两个小镇互相不友好。这就形成了 对不友好关系。
一天，小镇之间要开一个朋友聚会。显然，两个不友好的小镇的人不能同时来聚会，也就是说，最多有来自 个小镇的人会来聚会。为了不惊动不聚会的小镇，参加聚会的小镇需要是树上的一个连通块。所以请你找出这样 个可以一起聚会的小镇，或者报告无解。
输入格式
本题包含多组测试数据。
第一行一个正整数 ，表示数据组数。每一组数据包含 行。
每一组数据的第一行包含一个整数 ，表示 是小镇的数量。
第二行包含 个数字 。如果有 ，说明第 个小镇和第 个小镇不友好。保证对于每个 恰好一个 使得 。
接下来 行，每行两个整数 ，表示第 个小镇和第 个小镇之间有一条路直接相连。
输出格式
对于每一组测试数据，输出一行。
如果无法选出这样 个小镇，输出 -1。否则输出 个数，表示这些小镇的编号。如果有多种合法方案，输出任意一个即可。
样例
2
2
1 1 2 2
1 2
1 3
1 4
2
2 2 1 1
1 2
1 3
1 4
1 4
1 3
说明/提示
如上图，在第一个样例中，我们可以选择 或者 。在第二个样例中，我们只能选择 两个小镇。
本题包含多组测试数据。
对于 的数据，，。
保证一组数据内所有 中，每个 恰好出现两次。
保证一组数据内所有 构成一棵树。
国庆提高/省选组比赛
- Status
- Live... (Attended)
- Rule
- IOI
- Problem
- 40
- Start at
- 2025-10-15 19:32
- End at
- 2025-11-16 0:00
- Duration
- 1104 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 85