P13583 [NWRRC 2023] Colorful Village

彩色村庄是一个著名的旅游胜地。村里有 $2n$ 座房屋，编号从 $1$ 到 $2n$。每座房屋都有 $n$ 种颜色中的一种，颜色编号从 $1$ 到 $n$。巧合的是，每种颜色恰好有两座房屋被涂成该颜色。 彩色村庄有 $2n-1$ 条双向道路。每条道路连接两座不同的房屋，并且通过这些道路可以从任意一座房屋到达任意另一座房屋。 Catherine 正计划前往彩色村庄旅游。由于时间有限，她希望选择一个包含 $n$ 座房屋的集合 $S$ 进行参观，且每种颜色恰好选一座房屋。然而，由于 Catherine 还需要在房屋之间移动，所选择的房屋集合必须是连通的。换句话说，集合 $S$ 中的任意两座房屋都可以仅通过集合 $S$ 内的房屋和道路互相到达。 请帮助 Catherine 找到一个满足条件的连通房屋集合 $S$，包含 $n$ 座房屋且每种颜色各选一座，或者报告不存在这样的集合。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。 第二行包含 $2n$ 个整数 $c_1, c_2, \ldots, c_{2n}$，表示彩色村庄中每座房屋的颜色（$1 \le c_i \le n$）。每个 $1$ 到 $n$ 的整数恰好出现两次。 接下来的 $2n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条道路连接的两座房屋（$1 \le u_i, v_i \le 2n$；$u_i \ne v_i$）。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，如果不存在满足条件的房屋集合，输出一行 $-1$。 否则，输出 $n$ 个不同的整数 $s_1, s_2, \ldots, s_n$，表示一个满足条件的连通房屋集合 $S$，每种颜色各选一座（$1 \le s_i \le 2n$）。如果有多种方案，可以输出任意一种。

由 ChatGPT 4.1 翻译