Unter

Justas는 사람들이 자동차 이동을 함께 나눌 수 있는 앱을 만들려고 합니다. 먼저 두 집 사이의 최단 거리를 찾는 프로그램을 작성해야 합니다.

앱이 동작할 도시에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 집이 있습니다. 집들은 $N$개의 양방향 도로로 직접 연결되어 있습니다. 각 도로는 정확히 두 집을 잇고, 어떤 두 집도 최대 한 개의 도로로만 연결됩니다.

Justas는 한 집에서 다른 집으로 같은 집을 두 번 이상 지나지 않고 가는 방법이 오직 하나뿐일 때 두 집 사이의 최단 경로를 찾는 알고리즘을 이미 작성했습니다. 하지만 그런 방법이 두 가지 이상 존재하는 집 쌍에 대해서는 여러분의 도움이 필요합니다.

$Q$개의 집 쌍에 대해 최단 거리를 구하세요.

첫 번째 줄에는 집의 수 $N$과 질의의 수 $Q$가 주어집니다.

다음 $N$개의 줄에는 각각 공백으로 구분된 두 정수 $a_i$와 $b_i$가 주어지며, 이는 집 $a_i$와 $b_i$ 사이에 도로가 있음을 의미합니다.

그 다음 $Q$개의 줄에는 각각 공백으로 구분된 두 정수 $c_j$와 $d_j$가 주어집니다.

$Q$개의 줄을 출력합니다. $k$번째 줄에는 집 $c_k$와 $d_k$ 사이 최단 경로의 길이를 하나의 정수로 출력합니다. Justas는 두 집 사이의 거리를 지나야 하는 도로의 수로 계산합니다.

• $3 \le N \le 200000$
• $1 \le a_i, b_i \le N$ $(1 \le i \le N,\ a_i \ne b_i)$
• $1 \le Q \le 1000000$
• $1 \le c_j, d_j \le N$ $(1 \le j \le Q,\ c_j \ne d_j)$
• $c_j$에서 $d_j$로, 어떤 집도 두 번 이상 지나지 않는 경로가 (반드시 최단일 필요는 없이) 두 개 이상 존재합니다.
• 임의의 집에서 도로를 따라 다른 어떤 집으로도 항상 이동할 수 있습니다.