30690번 - 선로 조립

문제

모르고리즘 동방에는 기차 선로를 조립해 볼 수 있는 장난감이 있다. 민규는 1ドル$부터 $N$까지의 번호가 붙은 $N$개의 기차역을 $N-1$개의 선로들로 연결하였고, $i$번째 선로는 $u_i$번 역과 $v_i$번 역을 연결한다. 어떤 기차역에서도 선로를 통해 다른 기차역으로 도달하는 길이 존재한다. 서로 다른 두 역 사이에는 최대 1ドル$개의 선로가 존재한다.

민규는 다음 작업을 $Q$번 반복한다.

• $j$번째 작업에서, $p_j$번 역과 $q_j$번 역을 연결하는 선로를 뺀다.
• 뺀 선로를 원하는 서로 다른 두 역 사이에 놓는다. 두 역이 이미 한 개 이상의 선로로 연결되어 있으면 선로를 놓을 수 없으며, 선로가 원래 있던 자리에 다시 놓을 수 있다.
• 새롭게 완성된 선로에서 원하는 출발 역과 도착 역을 한 번 골라 기차를 출발 역에 놓고 도착 역까지 움직인다. 이때 한 번 지난 역을 다시 지날 수 없다.
• 뺀 선로를 원래 자리로 되돌려 놓는다.

민규는 오랫동안 장난감을 갖고 놀고 싶기 때문에, 각 작업에서 선로를 적절한 위치에 놓고 출발 및 도착 역을 적절히 골라 기차가 지나는 선로의 개수를 최대화하려고 한다. $Q$개의 작업에서 민규가 뺀 선로가 주어질 때, 기차가 지나는 선로의 개수를 최대화해 보자.

입력

입력은 다음과 같이 주어진다.

첫째 줄에 기차역의 개수 $N$과 작업의 횟수 $Q$가 공백으로 구분되어 주어진다.

이어 $N-1$줄에 걸쳐 선로의 정보가 주어진다. 각 줄에는 선로가 연결하는 두 역의 번호 $u_i,ドル $v_i$가 공백으로 구분되어 주어진다.

이어 $Q$줄에 걸쳐 각 작업의 정보가 주어진다. 각 줄에는 민규가 뺀 선로가 연결하는 두 역의 번호 $p_j,ドル $q_j$가 공백으로 구분되어 주어진다.

출력

$Q$줄에 걸쳐 각 작업마다 기차가 지나는 선로 개수의 최댓값을 한 줄에 하나씩 출력한다.

제한

• 2ドル \le N \le 200,000円$
• 1ドル \le Q \le 200,000円$
• 1ドル \le u_i \lt v_i \le N$
• 1ドル \le p_j \lt q_j \le N$
• $p_j$번 역과 $q_j$번 역을 연결하는 선로는 존재한다.

노트

실제 모르고리즘 동방에는 기차 장난감이 없다.