트트리리와 쿼리

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