{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/SNCKEL17/mandarin/BLACKCOM.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/SNCKEL17/russian/BLACKCOM.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/SNCKEL17/vietnamese/BLACKCOM.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\u003cp\u003eYou are given a tree T with \u003cb\u003eN\u003c/b\u003e nodes. The nodes are numbered from 1 to \u003cb\u003eN\u003c/b\u003e, and each node is colored either white or black. You are given \u003cb\u003eQ\u003c/b\u003e queries, where each query is of the form (\u003cb\u003es\u003c/b\u003e, \u003cb\u003eb\u003c/b\u003e). You need to check if there is a connected subgraph of size exactly \u003cb\u003es\u003c/b\u003e, which contains exactly \u003cb\u003eb\u003c/b\u003e black nodes.\u003c/p\u003e\n\n\u003cp\u003eA subgraph H, of a tree T, is a graph whose vertex set V\u003csub\u003eH\u003c/sub\u003e is a subset of the nodes of the tree and the edges are exactly those edges of the tree whose both end points are in V\u003csub\u003eH\u003c/sub\u003e. A subgraph H is a connected subgraph if H is connected.\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eThe first line contains a single integer, \u003cb\u003eT\u003c/b\u003e, which denotes the number of testcases. The descriptions of the testcases follow.\u003c/li\u003e\n\u003cli\u003eThe first line of each testcase contains two integers, \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eQ\u003c/b\u003e, which denotes the number of nodes in the tree, and the number of queries, respectively.\u003c/li\u003e\n\u003cli\u003eThe i-th of the next \u003cb\u003eN\u003c/b\u003e - 1 lines contains two integers: \u003cb\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. This denotes that there is an edge between nodes \u003cb\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e in the tree.\u003c/li\u003e\n\u003cli\u003eThe next line contains \u003cb\u003eN\u003c/b\u003e integers, \u003cb\u003ec\u003csub\u003e1\u003c/sub\u003e, c\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, .., \u003cb\u003ec\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e. \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e is 0 if node i is colored white, and it is 1 if it is colored black.\u003c/li\u003e\n\u003cli\u003eThe i-th of the next \u003cb\u003eQ\u003c/b\u003e lines contains two integers: \u003cb\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. This denotes a query of the form (\u003cb\u003es\u003csub\u003ei\u003c/sub\u003e, b\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) as described above.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eFor each testcase, output a single line containing the string \"Yes\" (without quotes), if there is a connected subgraph as required by the query, or \"No\" (without quotes) otherwise.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 5\u003c/li\u003e\n\u003cli\u003e2 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 5000\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eQ\u003c/b\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eu\u003csub\u003ei\u003c/sub\u003e, v\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ 1\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003es\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n1\n9 4\n4 1\n1 5\n1 2\n3 2\n3 6\n6 7\n6 8\n9 6\n0 1 0 1 0 0 1 0 1\n3 2\n7 3\n4 0\n9 5\n\n\u003cb\u003eOutput:\u003c/b\u003e\nYes\nYes\nNo\nNo\n\u003c/pre\u003e\n\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eQuery 1\u003c/b\u003e: The subgraph containing the nodes {6, 7, 9} is a connected subgraph because (6, 7) and (6, 9) are edges in the original tree. And it has exactly two black nodes (7 and 9). So, there is at least one connected subgraph of size exactly 3 which has exactly 2 black nodes. Hence the answer is \"Yes\".\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eQuery 2\u003c/b\u003e: The subgraph containing the nodes {1, 2, 3, 4, 6, 7, 8} is a connected subgraph. And it has exactly three black nodes (2, 4 and 7). So, there is at least one connected subgraph of size exactly 7 which has exactly 3 black nodes. Hence the answer is \"Yes\".\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eQuery 3\u003c/b\u003e: There is no connected subgraph of size exactly 4 with all white nodes. Hence the answer is \"No\".\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eQuery 4\u003c/b\u003e: The only subgraph with 9 nodes is the entire tree itself. And it has 4 black nodes, and not 5. Hence the answer is \"No\".\u003c/p\u003e"}}]}