소수 트리 - 6

트리는 사이클이 없는 연결 무방향 그래프이다. 정수 1, 2, ..., n이 붙은 n개의 정점을 가진 트리를 생각하자. 어떤 정수 d > 1이 있어서 u의 레이블과 v의 레이블이 모두 d로 나누어떨어지면 간선 (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-6.in으로 채점한다.