도시

JOI 왕국에는 여러 도시가 있다. 도로망은 다음 조건을 만족한다.

• (조건 1) 도시에는 0부터 N − 1까지 번호가 붙어 있다. 여기서 N은 JOI 왕국의 도시 수이다.
• (조건 2) 도시들은 N − 1개의 도로로 연결되어 있다. 각 도로는 양방향으로 지날 수 있다. 여러 도로를 거치면 모든 도시에서 다른 모든 도시로 이동할 수 있다.
• (조건 3) 도시 0에서 출발해 18개 이하의 도로를 지나면 모든 도시로 이동할 수 있다.

매일 JOI 왕국에서는 많은 사람이 도시 0에서 다른 도시로 출발한다. 목적지가 두 개인 사람이 많아서, 다음과 같은 질문을 하기도 한다. 서로 다른 두 도시 X, Y에 대해 (0), (1), (2) 중 어느 것이 성립하는가?

• (0) 도시 0에서 도시 X로 이동할 때 반드시 도시 Y를 지난다.
• (1) 도시 0에서 도시 Y로 이동할 때 반드시 도시 X를 지난다.
• (2) (0)도 (1)도 아니다.

위 상황에서 (0), (1), (2) 중 정확히 하나만 성립한다. X = 0일 때는 Y의 값과 무관하게 (1)이 성립한다고 본다. 마찬가지로 Y = 0일 때는 X의 값과 무관하게 (0)이 성립한다고 본다.

JOI 왕국의 도로망과 마찬가지로 다른 나라에서도 위 조건 1–3이 성립한다는 것이 알려져 있다. JOI 왕국 사람들은 다른 나라에서도 쓸 수 있도록 다음 두 기계를 개발하려고 한다.

• (기계 1) 도시 수 N과 도로망 정보가 주어지면 각 도시에 코드를 부여한다. 코드는 0 이상 260 − 1 이하의 정수이다.
• (기계 2) 기계 1이 부여한 서로 다른 두 도시 X, Y의 코드가 주어지면 질문에 답한다.

코드로 큰 정수를 부여하면 다루기 어렵다. 코드로 더 작은 값을 부여하도록 기계를 개발하려고 한다.

기계 2를 사용할 때는 도시 수 N과 도로망 정보가 기계에 직접 주어지지 않는다는 점에 유의하라.

위와 같은 두 기계를 개발하기 위해 다음 두 프로그램을 작성하라.

• JOI 왕국의 도시 수 N과 도로망 정보가 주어지면 각 도시에 코드를 부여하는 프로그램을 작성하라.
• 첫 번째 프로그램이 부여한 서로 다른 두 도시의 코드가 주어지면 그 도시들에 대한 질문에 답하는 프로그램을 작성하라.

샘플 그레이더는 표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에는 공백으로 구분된 두 정수 N, Q가 주어진다. 이는 도시가 N개이고 질의가 Q개 주어진다는 뜻이다.
• 다음 N − 1개 줄 중 (i + 1)번째 줄(0 ≤ i ≤ N − 2)에는 공백으로 구분된 두 정수 Ai, Bi가 주어진다. 이는 도시 Ai와 도시 Bi를 직접 연결하는 도로가 있다는 뜻이다.
• 다음 Q개 줄 중 j번째 줄(1 ≤ j ≤ Q)에는 공백으로 구분된 세 정수 Xj, Yj, Ej가 주어진다. 이는 j번째 질의에서 X = Xj, Y = Yj라는 뜻이며, 이 질의의 답이 Ej와 다르면 샘플 그레이더는 프로그램을 Wrong Answer로 판정한다.

프로그램이 정상적으로 종료되면 샘플 그레이더는 표준 출력에 다음 정보를 출력한다. (따옴표는 실제로 출력하지 않는다.)

• 프로그램이 정답으로 판정되면 샘플 그레이더는 도시에 부여된 코드의 최댓값을 “Accepted : max_code=123456.” 형식으로 출력한다.
• 프로그램이 Wrong Answer로 판정되면 샘플 그레이더는 그 종류를 “Wrong Answer [1].” 형식으로 출력한다.

프로그램이 여러 종류의 Wrong Answer로 판정되면 샘플 그레이더는 그중 하나만 보고한다.

• 2 ≤ N ≤ 250 000.
• 1 ≤ Q ≤ 250 000.
• 0 ≤ Ai ≤ N − 1 (0 ≤ i ≤ N − 2).
• 0 ≤ Bi ≤ N − 1 (0 ≤ i ≤ N − 2).
• Ai ≠ Bi (0 ≤ i ≤ N − 2).
• 도시 0에서 출발해 18개 이하의 도로를 지나면 모든 도시로 이동할 수 있다.
• 0 ≤ Xj ≤ N − 1 (1 ≤ j ≤ Q).
• 0 ≤ Yj ≤ N − 1 (1 ≤ j ≤ Q).
• Xj ≠ Yj (1 ≤ j ≤ Q).