#324 LCA

문제

정점이 $1$ 번부터 $N$ 번까지 번호가 붙은 트리가 주어진다. 트리는 $1$ 번 정점을 루트로 한다. 각 질의 $(u,v)$ 에 대해 $u$ 와 $v$ 의 가장 낮은 공통 조상을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $u_1\ v_1$ $u_{2}$

각 질의의 답을 한 줄에 하나씩 출력한다.

#	Score	Constraints
1	20	$N,Q \leq 500$
2	80	추가적인 제약조건이 없다.

Input

Output