트트리리와 쿼리

정점이 $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$에 대해 다음 쿼리를 처리하는 프로그램을 작성하시오.

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

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

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

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

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