트트리리와 쿼리

정점이 $N$개이고 무방향 간선으로 이루어진 트리 $T$가 주어진다. 이때 $E_i = (a_i, b_i)$는 트리 $T$에서 $i$번째 간선이 $a_i$번 정점과 $b_i$번 정점을 잇고 있다는 뜻이다.

트리 $T$를 가지고 트트리리 $S$를 정의한다.

• 트리 $T$와 동일한 $N - 1$개의 트리 $t_1, t_2, t_3, \cdots, t_{N-1}$가 있다.
• 정수쌍 $(c_i, d_i)$가 $N - 1$개 있다. 이때 $c_i$, $d_i$는 트리 $t_i$에 속한 서로 다른 두 정점이다.
• 트리 $T$에서 $E_i$를 제거한 후 아래 과정을 진행한다.
  • 트리 $T$의 $a_i$번 정점과 트리 $t_i$의 $c_i$번 정점을 잇는 간선을 추가한다.
  • 트리 $T$의 $b_i$번 정점과 트리 $t_i$의 $d_i$번 정점을 잇는 간선을 추가한다.
  • 트리 $t_i$의 모든 정점의 번호에 $N \times i$를 더한다.

위 과정을 모두 진행한 후 만들어진 트리가 트트리리 $S$이다. 트트리리 $S$에서 다음 쿼리를 처리하는 프로그램을 작성하시오.

• $u$ $v$: 정점 $u$에서 정점 $v$까지의 거리를 출력한다.

첫 번째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N - 1$개의 줄에 걸쳐 트리 $T$의 간선 정보가 주어진다. 그중 $i$번째 줄은 $E_i$에 대한 정보이며 $a_i$과 $b_i$가 공백으로 구분되어 주어진다.

그다음 줄부터 $N - 1$개의 줄에 걸쳐 정수쌍의 정보가 주어진다. 그중 $i$번째 줄은 $(c_i, d_i)$에 대한 정보이며 $c_i$과 $d_i$가 공백으로 구분되어 주어진다.

그다음 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다.

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

• $2 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le a_i, b_i, c_i, d_i \le N$
• $a_i \neq b_i$
• $c_i \neq d_i$
• $1 \le i \le N - 1$
• $1 \le u, v \le N^2$