시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 83 28 25 35.714%

문제

정점이 N개인 트리가 주어진다. 각 정점은 1번부터 N번까지 차례대로 번호가 부여되어 있다. i번째 간선은 Ai번 정점과 Bi번 정점을 연결하며, 가중치는 Ci다(1 ≤ i < N).

트리에서 두 정점 사이의 거리는 그 둘을 잇는 최단경로 상의 간선의 가중치의 최댓값으로 정의한다. 단, 같은 두 정점 사이의 거리는 0으로 정의한다.

트리에 사는 사람들이 Q개의 모임을 개최하려 한다. i번째 모임에는 Si 이상 Ei 이하의 번호를 가진 정점에 사는 사람들이 참석한다. 각 모임은 트리 상의 어떤 정점 v에서 이루어진다. 사람들이 모이는 정점 v를 잘 정하여, 모임에 참석하는 각 사람이 정점 v까지 이동하는 거리의 최댓값을 최소화하고자 한다.

이때 이 최솟값을 구하는 프로그램을 작성하시오.

입력

첫번째 줄에 트리의 정점 개수를 의미하는 자연수 N과 모임이 개최되는 횟수를 의미하는 자연수 Q가 사이에 공백을 두고 주어진다.

두번째 줄부터 (N-1)개의 줄에 걸쳐, 트리의 간선에 관한 정보가 주어진다. (i+1)번째 줄에는 세 개의 자연수 Ai, Bi, Ci가 사이에 공백을 두고 주어진다(1 ≤ i < N). 이는 Ai번 정점과 Bi번 정점을 연결하는 가중치 Ci의 간선이 존재함을 의미한다.

(N+1)번째 줄부터 Q개의 줄에 걸쳐, Q개의 모임에 관한 정보가 주어진다. (N+i)번째 줄에는 i번째 모임을 나타내는 두 개의 자연수 SiEi가 사이에 공백을 두고 주어진다(1 ≤ i ≤ Q).

출력

첫번째 줄부터 Q개의 줄에 걸쳐, 답을 차례대로 출력한다. i번째 줄에는 i번째 모임에 대한 답을 출력한다(1 ≤ i ≤ Q).

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 1 ≤ N ≤ 300,000
  • 1 ≤ Q ≤ 300,000
  • 1 ≤ AiN (1 ≤ i < N)
  • 1 ≤ BiN (1 ≤ i < N)
  • Ai ≠ Bi (1 ≤ i < N)
  • 1 ≤ Ci ≤ 109 (1 ≤ i < N)
  • 1 ≤ Si ≤ Ei ≤ N (1 ≤ i ≤ Q)

예제 입력 1

3 3
1 2 1
2 3 2
1 2
2 3
1 3

예제 출력 1

1
2
2