Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 2048 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Piggy (yang di waktu luangnya mengelola Komisi Protokol Konektivitas Antarbintang) sedang menghadapi teka-teki perangkat keras yang rumit. Jaringan komunikasi terbaru, yang terdiri atas $n$ stasiun relai yang dihubungkan oleh $(n - 1)$ tautan serat optik membentuk struktur pohon, akhirnya siap untuk diterapkan. Namun, sistem tersebut harus dinyalakan dengan sangat hati-hati.

Proses aktivasi melibatkan penembakan pulsa laser di sepanjang lintasan tertentu. Sebuah lintasan didefinisikan sebagai rute sederhana unik di antara dua stasiun. Karena risiko bencana "Interferensi Arus Balik Kuantum" — sebuah fenomena yang membuat para pengacara komisi terjaga sepanjang malam — protokol berikut harus dipatuhi secara ketat:

  • Lintasan transmisi harus dibangun satu demi satu.
  • Untuk mencegah lonjakan daya, setiap lintasan yang baru dibangun boleh berbagi paling banyak satu stasiun dengan himpunan stasiun yang sudah diaktifkan oleh lintasan mana pun sebelumnya.

Secara formal, misalkan $S$ adalah himpunan stasiun yang saat ini sudah aktif. Untuk setiap lintasan baru $P$ yang terdiri atas himpunan stasiun $V(P)$, syarat $|V(P) \cap S| \le 1$ harus terpenuhi. Begitu sebuah lintasan berhasil ditembakkan, semua stasiun di sepanjang lintasan tersebut dianggap menjadi bagian dari himpunan aktif $S$.

Misi Anda, jika Anda memilih untuk menerimanya, adalah menentukan jumlah minimum pulsa laser yang diperlukan untuk mengaktifkan setiap stasiun di seluruh jaringan dan memberikan satu barisan lintasan semacam itu demi memuaskan departemen hukum.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Ilustrasi dari dua kasus uji contoh pertama. Perhatikan bahwa pada Kasus 2, pulsa kedua hanya berbagi stasiun $2$ dengan pulsa pertama, sehingga memenuhi aturan non-interferensi.

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$ ($2 \le n \le 3 \times 10^5$), banyaknya stasiun dalam jaringan.

Untuk $(n - 1)$ baris berikutnya, baris ke-$i$ berisi dua bilangan bulat $u_i$ dan $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), yang mendeskripsikan tautan serat optik dua arah antara stasiun $u_i$ dan stasiun $v_i$.

Dijamin bahwa tautan-tautan tersebut membentuk sebuah pohon dan jumlah $n$ di seluruh kasus uji tidak melebihi $3 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan jumlah lintasan minimum $k$ pada baris pertama. Setelah itu, keluarkan $k$ baris, yang masing-masing berisi dua bilangan bulat $a_i$ dan $b_i$, yang merepresentasikan titik-titik ujung dari lintasan ke-$i$ dalam barisan. Perhatikan bahwa $a_i$ boleh sama dengan $b_i$ jika lintasan tersebut hanya terdiri atas satu stasiun.

Jika terdapat beberapa barisan optimal, barisan mana pun yang secara ketat mematuhi protokol non-interferensi akan diterima.

Contoh

Masukan

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

Keluaran

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.