프라임 트리 - 4

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