Prime Tree - 9

트리는 사이클이 없는 연결 무방향 그래프이다. 정수 1, 2, ..., n이 붙은 n개의 정점으로 이루어진 트리를 생각하자. 간선 (u, v)에 대해, u의 레이블과 v의 레이블을 모두 나누는 정수 d > 1이 존재하면 이 간선을 나쁜 간선이라고 부른다. 예를 들어 아래 트리에는 나쁜 간선이 세 개 있다. (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-9.in으로 채점한다.