给你一棵由 $$$2n$$$ 个顶点组成的树。回想一下,树是一个没有环的连通无向图。每个顶点上写有一个从 $$$1$$$ 到 $$$n$$$ 的整数。从 $$$1$$$ 到 $$$n$$$ 的每个值都写在两个不同的顶点上。每个顶点还有一个成本 - 顶点 $$$i$$$ 的成本为 $$$2^i$$$。
您需要选择树的顶点子集,以便:
- 子集已连接;也就是说,从子集中的每个顶点,只需经过子集中的顶点就可以到达子集中的每个其他顶点;
- 从 $$$1$$$ 到 $$$n$$$ 的每个值都写入子集中的至少一个顶点。
在所有这样的子集中,你需要找到其中顶点总成本最小的一个。请注意,您不需要最小化子集中的顶点数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \le a_i \le n$$$)。从 $$$1$$$ 到 $$$n$$$ 的每个值恰好出现两次。
接下来的 $$$2n-1$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le 2n$$$) - 树的边缘。这些边形成一棵有效的树。
输出
在第一行中,打印单个整数 $$$k$$$ — 子集中的顶点数。
在第二行中,打印 $$$k$$$ 从 $$$1$$$ 到 $$$2n$$$ 的不同整数 — 所选子集中顶点的索引。可以以任意顺序打印顶点。
示例
输入 #1
3 1 1 3 2 3 2 4 2 1 6 6 2 6 3 2 5
输出 #1
3 2 4 5
输入 #2
3 2 3 1 3 2 1 6 4 2 4 5 2 3 6 3 1
输出 #2
4 1 3 4 6
输入 #3
6 5 2 3 4 6 4 2 5 6 1 1 3 10 8 2 10 12 7 4 10 5 9 6 2 1 9 3 4 12 6 11 5 4 5
输出 #3
6 2 3 4 5 8 10
注意
图像显示了前两个示例的答案。括号中的数字是写在顶点上的值。
在第一个示例中,存在有效子集,例如:$$$[2, 4, 5]$$$(成本为 $$$2^2 + 2^4 + 2^5 = 52$$$)、$$$[2, 4, 5, 6]$$$(成本为 $$$116$$$)、$$$[1, 6, 3]$$$(成本为$$$74$$$),$$$[2,6,3]$$$(成本为$$$76$$$),等等。
在第二个示例中,子集 $$$[4, 6, 3, 1]$$$ 的成本为 $$$90$$$。