The goblin kingdom is strictly hierarchical: goblin ~0~ is the king, and every other goblin has exactly one superior. Indra is still infiltrating their ranks, and as his fairy godmother you need to answer questions about who sits above whom.

Each query asks: if Indra is goblin ~v~, who is the ~k~-th superior above him? The ~1~-st superior is his direct boss, the ~2~-nd superior is that boss's boss, and so on. If he does not have ~k~ superiors above him, report that the climb fails.

Input

The first line contains two integers ~n~ and ~q~: the number of goblins and the number of queries.

The next ~n-1~ lines each contain two integers ~a~ and ~b~, meaning that goblin ~a~ is the superior of goblin ~b~.

Finally, the next ~q~ lines each contain two integers ~v~ and ~k~, representing one query.

Output

For each query, output a single integer on its own line: the ~k~-th superior of goblin ~v~, or -1 if no such superior exists.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le q \le 10^5~
• ~0 \le a, b, v \le n-1~
• ~1 \le k \le 10^9~
• The superiors form a tree rooted at goblin ~0~

Example 1

Input

5 4
0 1
0 2
1 3
1 4
3 1
3 2
4 3
0 1

Output

1
0
-1
-1

Explanation

• Goblin ~3~'s first superior is ~1~.
• Goblin ~3~'s second superior is ~0~ (the king).
• Goblin ~4~ has only two superiors (~1~ then ~0~), so a climb of ~3~ fails.
• Goblin ~0~ has no superiors at all.