Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 2048 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

피기(여가 시간에 성간 연결 프로토콜 위원회를 관리함)는 까다로운 하드웨어 난제에 직면해 있습니다. $n$개의 중계소가 $(n - 1)$개의 광섬유 링크로 연결되어 트리 구조를 이루는 최신 통신망이 마침내 배치를 앞두고 있습니다. 하지만 이 시스템은 극도로 신중하게 전원을 켜야 합니다.

활성화 과정은 특정 경로를 따라 레이저 펄스를 발사하는 방식으로 진행됩니다. 경로란 두 중계소 사이의 유일한 단순 경로로 정의됩니다. 위원회의 변호사들이 밤잠을 설치게 만드는 현상인 "양자 역류 간섭(Quantum Backflow Interference)"의 치명적인 위험 때문에, 다음 프로토콜을 엄격히 준수해야 합니다:

  • 전송 경로는 하나씩 차례대로 구축해야 합니다.
  • 전력 급증을 방지하기 위해, 새로 구축하는 각 경로는 이전 경로들에 의해 이미 활성화된 중계소 집합과 최대 하나의 중계소만 공유할 수 있습니다.

형식적으로, 현재 활성화된 중계소들의 집합을 $S$라 합시다. 중계소 집합 $V(P)$로 이루어진 새로운 경로 $P$에 대하여 $|V(P) \cap S| \le 1$ 조건이 성립해야 합니다. 한 경로에 성공적으로 펄스가 발사되면, 그 경로 위의 모든 중계소는 활성화된 집합 $S$에 포함된 것으로 간주됩니다.

여러분의 임무는 전체 네트워크의 모든 중계소를 활성화하는 데 필요한 레이저 펄스의 최소 횟수를 구하고, 법무팀을 만족시킬 수 있는 그러한 경로들의 수열을 하나 제시하는 것입니다.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
처음 두 예제 테스트 케이스의 그림입니다. Case 2에서 두 번째 펄스는 첫 번째 펄스와 중계소 $2$만 공유하므로 비간섭 규칙을 만족함에 유의하세요.

입력

입력은 여러 개의 테스트 케이스로 구성됩니다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 각 테스트 케이스에 대하여:

첫째 줄에 통신망의 중계소 개수를 나타내는 정수 $n$ ($2 \le n \le 3 \times 10^5$)이 주어집니다.

다음 $(n - 1)$개의 줄 중 $i$번째 줄에는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)가 주어지며, 이는 중계소 $u_i$와 중계소 $v_i$ 사이의 양방향 광섬유 링크를 나타냅니다.

주어지는 링크들은 트리를 이루며, 모든 테스트 케이스에서 $n$의 합은 $3 \times 10^5$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 첫째 줄에 경로의 최소 개수 $k$를 출력합니다. 이어서 $k$개의 줄에 걸쳐, 각 줄에 수열의 $i$번째 경로의 양 끝점을 나타내는 두 정수 $a_i$와 $b_i$를 출력합니다. 경로가 단일 중계소로 이루어진 경우 $a_i$와 $b_i$가 같을 수 있습니다.

최적의 수열이 여러 개 존재한다면, 비간섭 프로토콜을 엄격히 따르는 것 중 아무것이나 출력해도 됩니다.

예제

입력

3
3
1 2
2 3
5
1 2
2 3
2 4
2 5
7
1 2
1 3
2 4
2 5
3 6
3 7

출력

1
1 3
2
4 5
1 3
3
7 7
1 6
4 5

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.