Prime Tree - 7

트리는 사이클이 없는 연결 무방향 그래프이다. 정수 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) 하나인데, 6과 3이 모두 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-7.in으로 채점한다.