Elevated Rails

Brandon과 Geoffry는 기차를 좋아합니다. 두 사람은 $n$개의 기차역을 잇는 선로망을 만드는 임무를 맡았습니다. 각 역은 세 섬 중 하나에 있으며, 각 섬에는 최소 한 개의 역이 있습니다.

Brandon은 같은 섬에 있는 역들을 연결해 두었습니다. 그 결과 같은 섬의 두 역 사이에는 같은 역을 두 번 지나지 않고 기차로 갈 수 있는 길이 정확히 하나 있습니다. 그러나 서로 다른 섬의 역끼리는 아직 기차로 갈 수 없습니다.

Geoffry는 Brandon의 선로망에 대해 여러 질문을 합니다. 각 질문은 서로 다른 섬에 있는 두 역을 고르고, Brandon이 연결을 정확히 두 개 더 추가해 모든 역이 서로 도달할 수 있게 되었을 때, 두 역 사이의 경로에 나타날 수 있는 역의 최대 개수를 묻습니다. Brandon은 신호 장치 작업으로 바빠서 섬들을 잇는 일을 생각할 여유가 없으므로, Geoffry의 질문에 답하는 일은 모두 여러분에게 맡깁니다.

첫 줄에는 역의 개수 $n$과 질문의 개수 $q$가 주어집니다 ($3 \le n \le 10^5$, $1 \le q \le 2 \cdot 10^5$).

이어지는 $n - 3$개의 줄에는 각각 두 정수 $x$와 $y$가 주어집니다 ($1 \le x < y \le n$). 이는 역 $x$와 역 $y$가 양방향으로 쓸 수 있는 선로로 연결되어 있다는 뜻입니다.

현재 선로 연결은 위의 조건을 만족합니다. 두 역이 서로 도달할 수 있는 경우는 같은 섬에 있을 때뿐이며, 같은 섬의 두 역 사이에는 어떤 역도 반복하지 않는 경로가 하나뿐입니다.

이어지는 $q$개의 줄에는 각각 두 정수 $a$와 $b$가 주어집니다. 이는 역 $a$와 역 $b$ 사이의 경로에 나타날 수 있는 역의 최대 개수를 묻는 질문입니다. 역 $a$와 역 $b$는 서로 다른 섬에 있다고 보장됩니다.

각 질문은 서로 독립적입니다.

$q$개의 줄을 출력합니다. 각 질문마다 한 줄에 답 하나를 출력합니다. 답은 하나의 정수이며, 역 $a$와 역 $b$ 사이의 경로에 나타날 수 있는 역의 최대 개수입니다.