QOJ.ac

QOJ

時間限制: 1.5 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓

#14720. 77G-nätverk

统计

Kartan över Meowland kan betraktas som ett rotat träd med $n$ noder och $n - 1$ kanter, där noder representerar städer och en kant representerar en väg som förbinder två städer. Huvudstaden ligger i roten, nod $1$.

Nu vill Meowland installera helt nya basstationer för 77G-nätverk i vissa städer. För att säkerställa att varje väg har tillräcklig nätverkskvalitet måste minst en av ändpunktsstäderna för varje väg ha en basstation. På grund av okända tekniska problem har nätverkssystemet dock $m$ fel. Fel $i$ kan beskrivas på följande sätt: om en basstation installeras i stad $x_i$, kan inga basstationer installeras i någon av städerna i delträdet till $x_i$ vars avstånd till $x_i$ är exakt $y_i$; annars kommer stationerna att störa varandra och bli obrukbara.

Hjälp Meowland att välja några städer så att installationen av basstationer i dessa städer uppfyller alla ovanstående krav. Om ingen giltig lösning existerar, skriv ut No.

Indata

Varje testfil innehåller flera testfall. Den första raden innehåller antalet testfall $T$ ($1 \le T \le 10^3$). Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($2 \le n \le 2 \times 10^5$), som anger antalet städer.

Den andra raden innehåller $n - 1$ heltal $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$), där $f_i$ anger föräldern till stad $i$.

Den tredje raden innehåller ett heltal $m$ ($0 \le m \le 2 \times 10^5$), som anger antalet fel.

Var och en av de följande $m$ raderna innehåller två heltal $x_i$ och $y_i$ ($1 \le x_i, y_i \le n$), som anger det $i$-te felet. Det kan förekomma två identiska fel.

För varje testfil garanteras att summan av $n$ över alla testfall inte överstiger $2 \times 10^5$, och att summan av $m$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, om det inte finns någon giltig lösning, skriv ut en rad No.

Annars, skriv ut tre rader som representerar din lösning:

  • På den första raden skriver du ut Yes.
  • På den andra raden skriver du ut ett heltal $c$, som anger antalet städer du väljer.
  • På den tredje raden skriver du ut $c$ distinkta heltal, som anger de städer du väljer.

Om det finns flera giltiga lösningar kan du skriva ut vilken som helst av dem. När du skriver ut lösningen får du ange de $c$ städerna i valfri ordning.

Exempel

Exempelindata 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

Exempelutdata 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.