CF570D Tree Requests

Roman planted a tree consisting of $ n $ vertices. Each vertex contains a lowercase English letter. Vertex $ 1 $ is the root of the tree, each of the $ n-1 $ remaining vertices has a parent in the tree. Vertex is connected with its parent by an edge. The parent of vertex $ i $ is vertex $ p_{i} $ , the parent index is always less than the index of the vertex (i.e., $ p_{i}<i $ ). The depth of the vertex is the number of nodes on the path from the root to $ v $ along the edges. In particular, the depth of the root is equal to $ 1 $ . We say that vertex $ u $ is in the subtree of vertex $ v $ , if we can get from $ u $ to $ v $ , moving from the vertex to the parent. In particular, vertex $ v $ is in its subtree. Roma gives you $ m $ queries, the $ i $ -th of which consists of two numbers $ v_{i} $ , $ h_{i} $ . Let's consider the vertices in the subtree $ v_{i} $ located at depth $ h_{i} $ . Determine whether you can use the letters written at these vertices to make a string that is a palindrome. The letters that are written in the vertexes, can be rearranged in any order to make a palindrome, but all letters should be used.

N/A

N/A

String $ s $ is a palindrome if reads the same from left to right and from right to left. In particular, an empty string is a palindrome. Clarification for the sample test. In the first query there exists only a vertex 1 satisfying all the conditions, we can form a palindrome "z". In the second query vertices 5 and 6 satisfy condititions, they contain letters "с" and "d" respectively. It is impossible to form a palindrome of them. In the third query there exist no vertices at depth 1 and in subtree of 4. We may form an empty palindrome. In the fourth query there exist no vertices in subtree of 6 at depth 1. We may form an empty palindrome. In the fifth query there vertices 2, 3 and 4 satisfying all conditions above, they contain letters "a", "c" and "c". We may form a palindrome "cac".