Discount Event

$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$개의 줄 중 $i$번째 줄에는 세 정수 $A_i$, $B_i$, $W_i$가 공백으로 구분되어 주어진다. 이들은 $i$번째 도로가 연결하는 두 도시의 번호와 도로의 이동 비용을 나타낸다.

다음 줄에 계획의 수를 나타내는 정수 $Q$가 주어진다.

다음 $Q$개의 줄 중 $i$번째 줄에는 두 정수 $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\neq 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\neq Y_i$ ($1\le i\le Q$)