{"raw_statement":[{"iden":"statement","content":"Each New Year Timofey and his friends cut down a tree of _n_ vertices and bring it home. After that they paint all the _n_ its vertices, so that the _i_\\-th vertex gets color _c__i_.\n\nNow it's time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.\n\nTimofey doesn't like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex.\n\nA subtree of some vertex is a subgraph containing that vertex and all its descendants.\n\nYour task is to determine if there is a vertex, taking which in hands Timofey wouldn't be annoyed."},{"iden":"input","content":"The first line contains single integer _n_ (2 ≤ _n_ ≤ 105) — the number of vertices in the tree.\n\nEach of the next _n_ - 1 lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_), denoting there is an edge between vertices _u_ and _v_. It is guaranteed that the given graph is a tree.\n\nThe next line contains _n_ integers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ 105), denoting the colors of the vertices."},{"iden":"output","content":"Print \"_NO_\" in a single line, if Timofey can't take the tree in such a way that it doesn't annoy him.\n\nOtherwise print \"_YES_\" in the first line. In the second line print the index of the vertex which Timofey should take in hands. If there are multiple answers, print any of them."},{"iden":"examples","content":"Input\n\n4\n1 2\n2 3\n3 4\n1 2 1 1\n\nOutput\n\nYES\n2\n\nInput\n\n3\n1 2\n2 3\n1 2 3\n\nOutput\n\nYES\n2\n\nInput\n\n4\n1 2\n2 3\n3 4\n1 2 1 2\n\nOutput\n\nNO"}],"translated_statement":[{"iden":"statement","content":"每年新年，蒂莫菲和他的朋友们会砍倒一棵有 #cf_span[n] 个顶点的树并带回家。之后，他们将这 #cf_span[n] 个顶点全部涂色，使得第 #cf_span[i] 个顶点获得颜色 #cf_span[ci]。\n\n现在到了蒂莫菲的生日，他的母亲让他把树移走。蒂莫菲移除树的方式如下：他用手握住某个顶点，其余所有顶点会向下移动，使得树以所选顶点为根。之后，蒂莫菲将树扔进垃圾桶。\n\n蒂莫菲不喜欢多种颜色混杂在一起。如果一个子树中包含不同颜色的顶点，他会感到厌烦。蒂莫菲希望找到一个顶点，他用手握住它后，不会有任何让他厌烦的子树。他不将整棵树视为一个子树，因为他看不到根顶点的颜色。\n\n某个顶点的子树是指包含该顶点及其所有后代的子图。\n\n你的任务是判断是否存在一个顶点，蒂莫菲握住它后就不会感到厌烦。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 树的顶点数。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n], #cf_span[u ≠ v])，表示顶点 #cf_span[u] 和 #cf_span[v] 之间有一条边。保证给定的图是一棵树。\n\n下一行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn] (#cf_span[1 ≤ ci ≤ 105])，表示各个顶点的颜色。\n\n如果蒂莫菲无法找到一个合适的顶点使得他不感到厌烦，请在一行中输出 \"_NO_\"。\n\n否则，第一行输出 \"_YES_\"，第二行输出蒂莫菲应握住的顶点编号。如果有多个答案，输出任意一个即可。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 树的顶点数。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n], #cf_span[u ≠ v])，表示顶点 #cf_span[u] 和 #cf_span[v] 之间有一条边。保证给定的图是一棵树。下一行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn] (#cf_span[1 ≤ ci ≤ 105])，表示各个顶点的颜色。"},{"iden":"output","content":"如果蒂莫菲无法找到一个合适的顶点使得他不感到厌烦，请在一行中输出 \"_NO_\"。否则，第一行输出 \"_YES_\"，第二行输出蒂莫菲应握住的顶点编号。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入41 22 33 41 2 1 1输出YES2输入31 22 31 2 3输出YES2输入41 22 33 41 2 1 2输出NO"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ T = (V, E) $ be a tree with $ n $ vertices, $ V = \\{1, 2, \\dots, n\\} $.\n- Let $ c: V \\to \\mathbb{N} $ be a coloring function, where $ c_i $ is the color of vertex $ i $.\n\n**Given:**\n\n- The tree $ T $ is undirected and connected.\n- For any vertex $ v \\in V $, when $ v $ is chosen as the root, the tree becomes rooted at $ v $.\n- A *subtree* of a vertex $ u \\neq v $ (i.e., any non-root vertex) is the subgraph induced by $ u $ and all its descendants under the rooting at $ v $.\n- A subtree is *annoying* if it contains at least two vertices of different colors.\n- Timofey is *not annoyed* if **no subtree** (of any non-root vertex) is annoying.\n\n**Objective:**\n\nDetermine whether there exists a vertex $ r \\in V $ such that, when $ r $ is chosen as the root, **every subtree** (i.e., the subtree rooted at every child of $ r $, and recursively all their descendants) is **monochromatic** (all vertices in the subtree have the same color).\n\n**Formal Condition for Valid Root $ r $:**\n\nLet $ r \\in V $ be a candidate root. For every child $ u $ of $ r $ in the rooted tree $ T_r $, the entire connected component (subtree) rooted at $ u $ must be monochromatic.\n\nEquivalently:  \nFor every edge $ (r, u) \\in E $, the connected component of $ T \\setminus \\{r\\} $ containing $ u $ must be monochromatic.\n\n**Note:** The root $ r $ itself is ignored in the monochromaticity check (its color is not part of any subtree).\n\n**Output:**\n\n- If such an $ r $ exists, output:\n  ```\n  YES\n  r\n  ```\n- Otherwise, output:\n  ```\n  NO\n  ```\n\n**Mathematical Restatement:**\n\nDoes there exist a vertex $ r \\in V $ such that for every connected component $ C $ of $ T - r $, all vertices in $ C $ have the same color?\n\nThat is:\n\n$$\n\\exists r \\in V \\text{ such that } \\forall \\text{ connected components } C \\text{ of } T - r, \\quad \\exists \\, k_C \\in \\mathbb{N} \\text{ such that } \\forall v \\in C, \\, c(v) = k_C\n$$","simple_statement":null,"has_page_source":false}