할인 행사

$N$개의 도시와 $N-1$개의 도로로 이루어진 나라가 있다. 도시에는 $1$부터 $N$까지의 번호가 붙어 있고, 도로에도 $1$부터 $N-1$까지의 번호가 붙어 있다. $i$번 도로는 $A_i$번 도시와 $B_i$번 도시를 양방향으로 연결하며, 이동할 때 $W_i$의 비용이 든다. 임의의 두 도시를 골라도 둘 사이를 하나 이상의 도로로 왕복할 수 있다.

두 도시 사이의 거리는 한 도시에서 출발해 하나 이상의 도로를 거쳐 다른 도시로 갈 때 필요한 최소 비용으로 정의한다.

당신은 도로 회사의 사장이며, 명절을 맞아 할인 행사를 열려고 한다. 행사 계획은 총 $Q$개이다. $i$번째 계획에서는 $X_i$번 도시에서 출발해 $Y_i$번 도시로 가는 최단 경로에 속한 모든 도로에 할인을 적용해 비용을 0으로 만든다. 각 계획마다 두 도시 사이 거리의 최댓값을 구하라.

첫 번째 줄에 도시의 수 $N$이 주어진다. 다음 $N-1$개의 줄에는 세 정수 $A_i$, $B_i$, $W_i$가 공백으로 구분되어 주어지며, 이는 $i$번째 도로가 잇는 두 도시의 번호와 이동 비용이다.

다음 줄에는 계획의 수 $Q$가 주어진다. 다음 $Q$개의 줄에는 두 정수 $X_i$와 $Y_i$가 공백으로 구분되어 주어지며, 이는 $i$번째 계획을 나타낸다.

총 $Q$개의 줄에 답을 출력한다. $i$번째 줄에는 $i$번째 계획의 답을 출력한다.

• $2 \le N \le 100\,000$
• $1 \le A_i, B_i \le N$ ($1 \le i \le N-1$)
• $A_i \ne B_i$ ($1 \le i \le N-1$)
• $1 \le W_i \le 10^9$ ($1 \le i \le N-1$)
• 입력으로 주어지는 나라의 구조는 올바른 트리를 이룬다.
• $1 \le Q \le 100\,000$
• $1 \le X_i, Y_i \le N$ ($1 \le i \le Q$)
• $X_i \ne Y_i$ ($1 \le i \le Q$)