32181번 - 트트리리와 쿼리

문제

정점이 $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$

힌트