Informatica Online Judge

  MAGYE [2285 / 08ED]

Time Limit(Test case) : 3333 (ms)
Number of users who solved : 5   Total Tried : 5


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[35th 김세빈]

Background

모두가 알다시피, 마계는 n개의 척박한 행성들로 이루어져 있다. 또한 서로 다른 두 행성 사이를 연결하는 포탈들이 n - 1개 존재하는데, 어떠한 행성에서 출발하더라도 다른 모든 행성들까지 포탈들만을 사용하여 오갈 수 있다. 즉, 마계는 행성들을 정점으로 하고, 포탈들을 간선으로 하는 트리 형태이다.

i번째 날, 행성 B_i에서 암석을 관찰하고 있던 마왕 고동은 여느 날과 같이, 행성 A_i의 염전에서 일하고 있던 앵딱이에게 다음과 같은 내용의 명령을 내렸다.

"최대한 빨리 튀어와. 아, 올 때 C_i 사오는거 잊지 말고"

마계의 행성들은 매우 척박하여, 하나의 행성에서는 한 가지 종류의 물건밖에 판매하지 않는다.

앵딱이는 행성 A_i에서 B_i로 최단경로로 이동하면서, 물건 C_i를 판매하는 행성을 발견하면 그곳에서 물건을 구매한다.

물론 그러한 행성이 여러 개라면 처음으로 방문하는 행성에서 물건을 구매하게 될 것이다. 고동은 합리적인 명령만 내리기 때문에, 행성 A_i에서 B_i로 가는 최단경로 상에는 반드시 C_i를 판매하는 행성이 하나 이상 존재한다.

i번째 날, 앵딱이가 어떤 행성에서 물건을 사게 될지 구하시오.

Input

첫 번째 줄에 마계를 이루는 행성의 수 n과 날짜의 수 q가 주어진다.
두 번째 줄부터 n번째 줄까지, i + 1번째 줄에는 두 개의 정수 U_i와 V_i가 주어진다. 이는 i번째 포탈의 정보이며, 행성 U_i와 V_i를 연결하는 포탈이 존재하여 이 둘 사이를 양방향으로 오갈 수 있다는 의미이다.
n + 1번째 줄부터 2n번째 줄까지, n + i번째 줄에는 i번째 행성에서 판매하는 물건의 종류 K_i가 주어진다.
2n + 1번째 줄부터 2n + q번째 줄까지, 2n + i번째 줄에는 세 개의 정수 A_i, B_i, C_i가 주어진다. 이는 i번째 날에 대한 정보이며, 앵딱이가 출발하는 장소가 A_i, 고동이 있는 장소가 B_i, 고동이 주문한 물건이 C_i임을 의미한다.

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

1 <= n <= 10^5
1 <= q <= 10^5
1 <= U_i, V_i <= n, U_i != V_i
1 <= K_i <= 10^9
1 <= A_i, B_i <= n
1 <= C_i <= 10^9

Output

첫 번째 줄부터 q번째 줄까지, i번째 줄에는 i번째 날 앵딱이가 물건을 사게 되는 행성의 번호를 출력한다

IO Example

Input 1

6 5
1 2
2 3
3 4
4 5
4 6
1
3
2
3
4
1
1 5 3
5 1 3
2 6 2
5 6 4
6 2 1

Output 1

2
4
3
5
6

Input 2

5 5
1 2
2 3
3 4
4 5
1
2
1
3
2
1 3 1
2 4 1
3 5 1
2 5 3
3 5 2

Output 2

1
3
3
4
5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]