← 返回题目列表

Codeforces · 1211/G

G. 国王之路

中文机器翻译题面 查看原题

Treeland 有 $$$n$$$ 个城市和 $$$n-1$$$ 双向道路。每条道路连接一对不同的城市。您可以从任何城市开车前往任何其他城市,只需沿着道路行驶即可。城市编号从 $$$1$$$ 到 $$$n$$$。是的,当然,您在这个描述中认出了一棵无向树。

每个城市只有一面旗帜,第 $$$i$$$ 个城市的旗帜颜色为 $$$c_i$$$。不同城市的旗帜颜色可能相同。

如果国王沿着路线 $$$[u_1, u_2, u_3, \dots, u_k]$$$ 旅行,那么这意味着他从城市 $$$u_1$$$ 出发,然后移动到城市 $$$u_2$$$ ($$$u_2$$$ 通过公路与 $$$u_1$$$ 连接),然后从 $$$u_2$$$ 出发到 $$$u_3$$$($$$u_3$$$ 通过公路连接到 $$$u_2$$$),依此类推,直到到达 $$$u_k$$$ 市。在这条路线上,国王可能会多次访问同一座城市。换句话说,路线 $$$[u_1, u_2, u_3, \dots, u_k]$$$ 不一定包含不同的城市。从图论的角度来说,国王从 $$$u_1$$$ 沿着某个路径 $$$[u_1, u_2, u_3, \dots, u_k]$$$ 移动到 $$$u_k$$$,这不一定很简单(对于所有 $$$j$$$ 从 $$$1$$$ 到 $$$k-1$$$ 城市 $$$u_j$$$ 和$$$u_{j+1}$$$ 有公路连接)。

当国王从一个城市移动到另一个城市时,城市首领交换旗帜以表示他们的友谊。

沿着路线 $$$[1, 4, 2, 6]$$$ 移动国王的示例。顶点的颜色与该顶点处标志的颜色相匹配。

出于美观原因,国王希望城市 $$$i$$$ 的旗帜颜色等于 $$$d_i$$$,对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$。确定国王是否可以选择某条路线并沿着该路线行驶,以便每个城市的旗帜颜色等于所需的颜色 $$$d_i$$$。请注意,国王只能选择(并驾驶)一条路线。如果是,请找到国王的最短路线。

如果旗帜的初始颜色已经符合国王的要求(即 $$$c_i=d_i$$$ 对于所有 $$$i$$$),则认为国王制定了一条长度为 $$$k=0$$$ 的路线。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 要解决的测试用例的数量。以下为案例。

每个案例都以包含整数 $$$n$$$ 的行开始 ($$$2 \le n \le 2\cdot10^5$$$) — Treeland 中的城市数量。

下面是一行 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$),其中 $$$c_i$$$ 表示国王旅程之前第 $$$i$$$ 个顶点的旗帜颜色。

下面是一行 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^6$$$),其中 $$$d_i$$$ 表示国王旅程完成后第 $$$i$$$ 个顶点所需的旗帜颜色。

此外,在 $$$n-1$$$ 行中,列出了 Treeland 的道路。每条道路由包含两个整数的行给出 $$$x_j, y_j$$$ ($$$1 \le x_j, y_j \le n$$$) — 由第 $$$j$$$ 条道路连接的城市数量。

保证从每个城市都可以通过公路到达任何其他城市(换句话说,城市和道路系统形成一棵无向树)。

一次测试中所有案例的所有 $$$n$$$ 值的总和不超过 $$$2\cdot10^5$$$。

输出

按照输入数据中出现的顺序打印所有案例的答案。

每个答案必须以包含“是”(在肯定答案的情况下)或“否”(在所需路由不存在的情况下)的行开头。如果是肯定答案,下面的行必须包含一个整数$$$k$$$——国王的最短路线中的城市数量。下一行应包含所需的路线 $$$u_1, u_2, \dots, u_k$$$ ($$$1 \le u_i \le n$$$)。如果 $$$k=0$$$ 则可以跳过该行。

示例

输入 #1

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

输出 #1

Yes
4
1 4 2 6

输入 #2

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

输出 #2

Yes
5
1 2 3 4 5

输入 #3

3
4
10 20 10 20
20 10 20 10
1 2
1 3
1 4
2
1000000 1000000
1000000 1000000
1 2
10
4 2 2 4 2 4 1 2 3 4
4 2 4 4 3 2 1 2 4 2
5 8
6 9
10 5
1 10
7 10
3 4
5 9
3 10
2 4

输出 #3

No
Yes
0
Yes
5
3 10 5 9 6