Prime Tree - 8

트리는 사이클이 없는 연결 무방향 그래프이다. 정수 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-8.in으로 채점한다.