Prime Tree - 5

트리는 사이클이 없는 연결 무방향 그래프이다. 정수 1, 2, ..., n이 붙어 있는 n개 정점의 트리를 생각하자. 정점 u의 레이블과 정점 v의 레이블을 모두 나누는 정수 d > 1이 존재하면 간선 (u, v)를 나쁜 간선이라고 부른다. 예를 들어 아래 트리에는 나쁜 간선이 세 개 있다. (6, 4)는 둘 다 2로 나누어지고, (2, 6)도 둘 다 2로 나누어지며, (3, 6)은 둘 다 3으로 나누어진다.

나쁜 간선의 수가 최대한 적어지도록 정점에 레이블을 다시 붙이는 것이 목표이다. 예를 들어 위 트리의 정점에 다음과 같이 레이블을 다시 붙이면 나쁜 간선은 (3, 6) 하나만 남는다.

나쁜 간선이 적을수록 더 많은 점수를 받는다.

이 문제는 출력 전용 문제이다. 프로그램을 로컬에서 실행하고 입력 파일별로 답안 파일만 제출해야 한다.

각 입력 파일에는 여러 테스트 케이스가 들어 있다.

입력 파일의 첫 줄에는 이 입력 파일에 들어 있는 테스트 케이스의 수가 주어진다.

테스트 케이스 설명의 첫 줄에는 트리의 정점 수를 나타내는 정수 n이 하나 주어진다.

다음 n − 1개 줄에는 간선으로 연결된 두 정점 u와 v (1 ≤ u, v ≤ n)가 주어진다.

한 파일에 들어 있는 모든 트리는 정점 수가 같다.

각 테스트 케이스마다 정점 1, 2, . . . , n에 붙인 레이블, 즉 1부터 n까지의 서로 다른 정수 n개를 정확히 한 줄에 출력한다.

첫 번째 테스트 케이스는 위 문제 설명에 나와 있다. 레이블을 다시 붙인 뒤에는 6과 3이 모두 3으로 나누어지므로 나쁜 간선 (6, 3)이 하나 있다.

두 번째 테스트 케이스에는 간선 (5, 1), (5, 2), (5, 3), (5, 4), (5, 6)이 있다. 이 중 나쁜 간선은 없다.

입력 파일에는 간선이 10개 있고 답안에는 나쁜 간선이 1개 있다. 따라서 M = 10, X = 1, R = 0.1이다. 점수 표에 따르면 이 답안은 5점을 받는다.

테스트는 다음과 같이 구성되어 있다.

• 입력 파일 1에는 정점이 7개인 트리 세 개가 들어 있으며, 아래에 왼쪽부터 차례로 나와 있다.

• 입력 파일 2와 3에는 각각 정점이 10개, 30개인 무작위 트리 100개가 들어 있다.
• 입력 파일 4부터 8까지에는 특별한 구조를 가진 여러 무작위 트리(예: 잎이 많은 트리, 이진 트리 등)가 들어 있다. 여러 종류의 트리 분포는 모든 입력에서 거의 같다.
• 입력 파일 9와 10에는 각각 정점이 50 000개, 100 000개인 무작위 트리가 들어 있다.

처음에는 모든 입력 파일에 있는 모든 트리의 정점 레이블이 무작위이다.

압축 파일의 data-5.in으로 채점한다.