CF1006E Military Problem

In this problem you will have to help Berland army with organizing their command delivery system. There are $ n $ officers in Berland army. The first officer is the commander of the army, and he does not have any superiors. Every other officer has exactly one direct superior. If officer $ a $ is the direct superior of officer $ b $ , then we also can say that officer $ b $ is a direct subordinate of officer $ a $ . Officer $ x $ is considered to be a subordinate (direct or indirect) of officer $ y $ if one of the following conditions holds: - officer $ y $ is the direct superior of officer $ x $ ; - the direct superior of officer $ x $ is a subordinate of officer $ y $ . For example, on the picture below the subordinates of the officer $ 3 $ are: $ 5, 6, 7, 8, 9 $ . The structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army. Formally, let's represent Berland army as a tree consisting of $ n $ vertices, in which vertex $ u $ corresponds to officer $ u $ . The parent of vertex $ u $ corresponds to the direct superior of officer $ u $ . The root (which has index $ 1 $ ) corresponds to the commander of the army. Berland War Ministry has ordered you to give answers on $ q $ queries, the $ i $ -th query is given as $ (u_i, k_i) $ , where $ u_i $ is some officer, and $ k_i $ is a positive integer. To process the $ i $ -th query imagine how a command from $ u_i $ spreads to the subordinates of $ u_i $ . Typical DFS (depth first search) algorithm is used here. Suppose the current officer is $ a $ and he spreads a command. Officer $ a $ chooses $ b $ — one of his direct subordinates (i.e. a child in the tree) who has not received this command yet. If there are many such direct subordinates, then $ a $ chooses the one having minimal index. Officer $ a $ gives a command to officer $ b $ . Afterwards, $ b $ uses exactly the same algorithm to spread the command to its subtree. After $ b $ finishes spreading the command, officer $ a $ chooses the next direct subordinate again (using the same strategy). When officer $ a $ cannot choose any direct subordinate who still hasn't received this command, officer $ a $ finishes spreading the command. Let's look at the following example: If officer $ 1 $ spreads a command, officers receive it in the following order: $ [1, 2, 3, 5 ,6, 8, 7, 9, 4] $ . If officer $ 3 $ spreads a command, officers receive it in the following order: $ [3, 5, 6, 8, 7, 9] $ . If officer $ 7 $ spreads a command, officers receive it in the following order: $ [7, 9] $ . If officer $ 9 $ spreads a command, officers receive it in the following order: $ [9] $ . To answer the $ i $ -th query $ (u_i, k_i) $ , construct a sequence which describes the order in which officers will receive the command if the $ u_i $ -th officer spreads it. Return the $ k_i $ -th element of the constructed list or -1 if there are fewer than $ k_i $ elements in it. You should process queries independently. A query doesn't affect the following queries.

The first line of the input contains two integers $ n $ and $ q $ ( $ 2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5 $ ) — the number of officers in Berland army and the number of queries. The second line of the input contains $ n - 1 $ integers $ p_2, p_3, \dots, p_n $ ( $ 1 \le p_i < i $ ), where $ p_i $ is the index of the direct superior of the officer having the index $ i $ . The commander has index $ 1 $ and doesn't have any superiors. The next $ q $ lines describe the queries. The $ i $ -th query is given as a pair ( $ u_i, k_i $ ) ( $ 1 \le u_i, k_i \le n $ ), where $ u_i $ is the index of the officer which starts spreading a command, and $ k_i $ is the index of the required officer in the command spreading sequence.

Print $ q $ numbers, where the $ i $ -th number is the officer at the position $ k_i $ in the list which describes the order in which officers will receive the command if it starts spreading from officer $ u_i $ . Print "-1" if the number of officers which receive the command is less than $ k_i $ . You should process queries independently. They do not affect each other.