← 返回题目列表

Codeforces · 763/A

A. 蒂莫菲和一棵树

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

每年新年,蒂莫菲和他的朋友们都会砍倒一棵有 n 个顶点的树并将其带回家。之后,他们绘制所有 n 个顶点,以便第 i 个顶点的颜色为 ci。

现在是蒂莫菲的生日了,他的妈妈要求他把树移走。 Timofey 通过以下方式移除树:他将一些顶点放在手中,而所有其他顶点向下移动,以便树在所选顶点处扎根。之后蒂莫菲将树扔进了垃圾桶。

Timofey 不喜欢多种颜色混合在一起。如果子树中存在不同颜色的顶点,他就会感到烦恼。 Timofey 想要找到一个他应该握在手中的顶点,这样就不会出现让他烦恼的子树。他不将整棵树视为子树,因为他看不到根顶点的颜色。

某个顶点的子树是包含该顶点及其所有后代的子图。

你的任务是确定是否存在一个顶点,将其握在手中 Timofey 不会生气。

输入

第一行包含单个整数 n (2 ≤ n ≤ 105) — 树中的顶点数。

接下来的 n - 1 行中的每一行都包含两个整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v),表示顶点 u 和 v 之间有一条边。保证给定的图是一棵树。

下一行包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ 105),表示顶点的颜色。

输出

如果 Timofey 不能以不惹恼他的方式拿走这棵树,请在一行中打印“NO”。

否则在第一行打印“YES”。在第二行中打印 Timofey 应该握在手中的顶点的索引。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
1 2
2 3
3 4
1 2 1 1

输出 #1

YES
2

输入 #2

3
1 2
2 3
1 2 3

输出 #2

YES
2

输入 #3

4
1 2
2 3
3 4
1 2 1 2

输出 #3

NO