{"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 ≤ 10^5]）——树中顶点的数量。\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 ≤ 10^5]），表示每个顶点的颜色。\n\n如果蒂莫菲无法找到一个合适的顶点使得他不会感到厌烦，请在一行中输出 \"_NO_\"。\n\n否则，第一行输出 \"_YES_\"，第二行输出蒂莫菲应握住的顶点编号。如果有多个答案，输出任意一个即可。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 10^5]）——树中顶点的数量。接下来的 #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 ≤ 10^5]），表示每个顶点的颜色。"},{"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 $ |V| = n $, $ n \\geq 2 $.\n- Let $ c: V \\to \\mathbb{N} $ be a coloring function, where $ c(i) $ is the color of vertex $ i $.\n- For a rooted tree with root $ r $, the *subtree* of a vertex $ v \\neq r $ is the induced subgraph consisting of $ v $ and all its descendants.\n- A subtree is *annoying* if it contains vertices of more than one distinct color.\n- The entire tree (rooted at $ r $) is **not** considered a subtree for the purpose of annoyance.\n\n**Given:**\n\n- Tree $ T $ with $ n $ vertices.\n- Coloring $ c: V \\to \\{1, 2, \\dots, 10^5\\} $.\n- For a candidate root $ r \\in V $, we require:  \n  For every vertex $ v \\in V \\setminus \\{r\\} $, the subtree rooted at $ v $ is **monochromatic** (i.e., all vertices in the subtree have the same color).\n\n**Objective:**\n\nDetermine whether there exists a vertex $ r \\in V $ such that, when the tree is rooted at $ r $, **all subtrees** (of all non-root vertices) are monochromatic.\n\nIf such an $ r $ exists, output:\n```\nYES\nr\n```\nOtherwise, output:\n```\nNO\n```\n\n---\n\n**Formal Condition for Valid Root $ r $:**\n\nLet $ T_r $ denote the tree rooted at $ r $.  \nFor all $ v \\in V \\setminus \\{r\\} $, let $ S_v $ be the set of vertices in the subtree rooted at $ v $.  \nThen $ r $ is valid if and only if:\n\n$$\n\\forall v \\in V \\setminus \\{r\\}, \\quad \\forall u, w \\in S_v, \\quad c(u) = c(w)\n$$\n\nEquivalently:  \nFor every child $ v $ of $ r $, the entire connected component of $ T \\setminus \\{r\\} $ containing $ v $ must be monochromatic.  \nAnd recursively: for every descendant $ u $ of $ v $, the subtree rooted at $ u $ must also be monochromatic — but this is implied if every *direct* subtree under $ r $ is monochromatic and the coloring is consistent downward.\n\n**Note:** The condition reduces to:  \nWhen removing $ r $, each connected component (i.e., subtree of each child of $ r $) must be monochromatic.\n\nThus, the problem reduces to:\n\n> Does there exist a vertex $ r $ such that, in the forest $ T \\setminus \\{r\\} $, every connected component is monochromatic?\n\nThis is the formal mathematical statement of the problem.","simple_statement":null,"has_page_source":false}