Two goblins want to file a joint petition, but kingdom law is unforgiving: they must present it to their closest shared superior. That superior is the lowest goblin who sits above both of them in the hierarchy (or one of them, if one already outranks the other). The king (goblin ~0~) is above everyone.

As Indra's fairy godmother, you must answer ~q~ kinship queries: given goblins ~a~ and ~b~, who is their closest shared superior?

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 ~a~ and ~b~, representing one query.

Output

For each query, output a single integer on its own line: the closest shared superior of goblins ~a~ and ~b~.

Constraints

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

Example 1

Input

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

Output

1
0
0
4

Explanation

• Goblins ~3~ and ~4~ meet at ~1~.
• Goblins ~3~ and ~2~ meet at the king ~0~.
• Goblins ~0~ and ~3~ meet at ~0~ (the king already outranks ~3~).
• A goblin's closest shared superior with themselves is themselves.