Prime Tree - 10

트리는 사이클이 없는 연결 무방향 그래프이다. 정수 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)가 주어진다.

한 파일에 들어 있는 모든 트리는 정점 수가 같다.

첫 번째 테스트 케이스는 위 문제 설명에 나와 있다. 레이블을 다시 붙이면 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-10.in으로 채점한다.