QOJ.ac

QOJ

Süre Sınırı: 1.5 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓

#14720. 77G 網絡

İstatistikler

喵之國嘅地圖可以睇成一棵有 $n$ 個節點同 $n - 1$ 條邊嘅有根樹,其中節點代表城市,邊代表連接兩座城市嘅道路。首都位於樹根,即係節點 $1$。

而家喵之國想喺一啲城市安裝全新嘅 77G 網絡基站。為咗確保每條道路都有足夠嘅網絡質素,每條道路嘅兩個端點城市入面至少要有一個安裝基站。不過,由於未知嘅技術問題,網絡系統有 $m$ 個故障。故障 $i$ 可以描述如下:如果喺城市 $x_i$ 安裝咗基站,咁喺 $x_i$ 嘅子樹入面,所有同 $x_i$ 距離恰好係 $y_i$ 嘅城市都唔可以安裝基站;否則,基站之間會互相干擾並變得無法使用。

請幫喵之國揀一啲城市,令到喺呢啲城市安裝基站可以滿足以上所有要求。如果唔存在合法方案,請輸出 No。

輸入格式

每個測試檔案包含多組測試用例。第一行包含測試用例嘅數量 $T$($1 \le T \le 10^3$)。接下來係各組測試用例嘅描述。

每組測試用例嘅第一行包含一個整數 $n$($2 \le n \le 2 \times 10^5$),代表城市嘅數量。

第二行包含 $n - 1$ 個整數 $f_2, f_3, \dots, f_n$($1 \le f_i < i$),其中 $f_i$ 代表城市 $i$ 嘅父節點。

第三行包含一個整數 $m$($0 \le m \le 2 \times 10^5$),代表故障嘅數量。

接下來嘅 $m$ 行,每行包含兩個整數 $x_i$ 同 $y_i$($1 \le x_i, y_i \le n$),代表第 $i$ 個故障。可能會存在兩個完全一樣嘅故障。

對於每個測試檔案,保證所有測試用例入面 $n$ 嘅總和唔超過 $2 \times 10^5$,而且所有測試用例入面 $m$ 嘅總和唔超過 $2 \times 10^5$。

輸出格式

對於每組測試用例,如果唔存在合法方案,輸出單獨一行 No。

否則,輸出三行嚟代表你嘅方案:

  • 喺第一行輸出 Yes。
  • 喺第二行輸出一個整數 $c$,代表你揀嘅城市數量。
  • 喺第三行輸出 $c$ 個唔同嘅整數,代表你揀嘅城市。

如果有多個合法方案,你可以輸出任意一個。輸出方案嗰陣,你可以按任意順序輸出呢 $c$ 座城市。

範例

範例輸入 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

範例輸出 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.