QOJ.ac

QOJ

Limite de temps : 1.5 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓

#14720. Jaringan 77G

Statistiques

Peta Meowland dapat dianggap sebagai pohon berakar dengan $n$ simpul dan $n - 1$ sisi, dengan simpul menyatakan kota dan sisi menyatakan jalan yang menghubungkan dua kota. Ibu kota berada di akar, yaitu simpul $1$.

Sekarang Meowland ingin memasang stasiun pemancar jaringan 77G baru di beberapa kota. Untuk memastikan bahwa setiap jalan memiliki kualitas jaringan yang memadai, setidaknya salah satu dari kota ujung pada setiap jalan harus memiliki stasiun pemancar. Namun, karena masalah teknis yang tidak diketahui, sistem jaringan memiliki $m$ gangguan. Gangguan $i$ dapat dijelaskan sebagai berikut: jika sebuah stasiun pemancar dipasang di kota $x_i$, maka semua kota di dalam upapohon dari $x_i$ yang jaraknya ke $x_i$ tepat sebesar $y_i$ tidak dapat dipasangi stasiun pemancar; jika tidak, stasiun-stasiun tersebut akan saling mengganggu dan menjadi tidak dapat digunakan.

Bantulah Meowland memilih beberapa kota sehingga pemasangan stasiun pemancar di kota-kota tersebut memenuhi semua persyaratan di atas. Jika tidak ada skema yang valid, keluarkan No.

Masukan

Setiap berkas uji berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $T$ ($1 \le T \le 10^3$). Deskripsi dari kasus-kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($2 \le n \le 2 \times 10^5$), yang menyatakan banyaknya kota.

Baris kedua berisi $n - 1$ bilangan bulat $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$), dengan $f_i$ menyatakan induk dari kota $i$.

Baris ketiga berisi sebuah bilangan bulat $m$ ($0 \le m \le 2 \times 10^5$), yang menyatakan banyaknya gangguan.

Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $x_i$ dan $y_i$ ($1 \le x_i, y_i \le n$), yang menyatakan gangguan ke-$i$. Mungkin terdapat dua gangguan yang identik.

Untuk setiap berkas uji, dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$, dan jumlah dari $m$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, jika tidak ada skema yang valid, keluarkan sebuah baris No.

Selain itu, keluarkan tiga baris yang menyatakan skema Anda:

  • Pada baris pertama keluarkan Yes.
  • Pada baris kedua keluarkan sebuah bilangan bulat $c$, yang menyatakan banyaknya kota yang Anda pilih.
  • Pada baris ketiga keluarkan $c$ bilangan bulat berbeda, yang menyatakan kota-kota yang Anda pilih.

Jika terdapat beberapa skema yang valid, Anda boleh mengeluarkan yang mana saja. Saat mengeluarkan skema, Anda boleh mengeluarkan $c$ kota tersebut dalam urutan apa pun.

Contoh

Contoh Masukan 1

3
6
1 1 2 2 4
2
1 3
2 1
6
1 1 2 2 4
6
1 1
1 2
1 3
2 1
2 2
2 1
8
1 1 3 1 1 2 4
10
1 2
3 2
1 3
5 1
6 1
3 2
4 1
3 2
5 1
3 1

Contoh Keluaran 1

Yes
4
5 3 4 1
No
No

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.