Problem Statement

You are given a tree with ~n~ vertices. The tree is rooted at ~1~.

You are also given ~q~ queries, each containing two integers ~u~ and ~v~ representing vertices of the tree. For each query you should output the lowest common ancestor of ~u~ and ~v~ using an Euler Tour.

Notice the bounds are quite small for this problem, so feel free to iterate ~O(n)~ times to find the lowest common ancestor.

NOTE: The lowest common ancestor of two vertices, ~u~ and ~v~, in a rooted tree, is the deepest node which is along the root to leaf path of both ~u~ and ~v~.

Input Format

Your first line will contain two space-separated integers ~n~ and ~q~. Your next ~n - 1~ lines will contain two space-separated integers each ~u~ and ~v~ representing an edge from ~u~ to ~v~. Your next ~q~ lines will contain two space-separated integers each, ~u~ and ~v~ representing the vertices for which you would like to find the lowest common ancestor.

Output Format

For each of the ~q~ queries, you should output the LCA for the given nodes.

Constraints

• ~1 \leq n, q \leq 10^2~
• ~1 \leq u, v \leq n~ and ~u \neq v~

Template

import sys
sys.setrecursionlimit(int(1e9))

n, q = map(int, input().split())
edges = [map(int, input().split()) for _ in range(n - 1)]
queries = [map(int, input().split()) for _ in range(q)]

# print your output

Sample Cases

Input 1

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

Output 1

1
1
2
2
4

Input 2

10 10
4 7
7 8
2 4
6 7
8 10
5 8
2 9
3 7
1 9
2 9
6 8
8 9
2 8
8 9
3 8
4 10
5 7
5 6
3 9

Output 2

9
7
9
2
9
7
4
7
7
9