Prime Tree - 1

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