Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100
Estadísticas

Dingdong planlegger å reise til landet Hamu.

Landet Hamu består av $n$ byer og $m$ toveis veier. Før denne reisen har Dingdong allerede besøkt by $i$ nøyaktig $a_i$ ganger. Under denne reisen planlegger Dingdong å reise inn i Hamu ved by $s$. På hver påfølgende dag vil Dingdong reise langs en bestemt vei til en by og besøke denne byen én gang. På slutten av den siste dagens besøk skal Dingdong befinne seg i by $s$ og forlate Hamu fra by $s$. Merk at på dagen han reiser inn i landet Hamu, besøker ikke Dingdong by $s$.

Dingdong håper at hver by i Hamu etter denne reisen, kombinert med hans tidligere besøk, vil ha blitt besøkt av ham et partall antall ganger. Dingdong har begrenset tid og kan besøke høyst $5n$ byer i løpet av denne reisen. Vennligst hjelp ham med å lage en gyldig reiseplan, eller fortell ham om det er umulig.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 2 \times 10^5$), antall testtilfeller.

For hvert testtilfelle inneholder den første linjen tre heltall $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), der $n$ er antall byer, $m$ er antall veier og $s$ er indeksen til startbyen.

Neste linje inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), antall ganger Dingdong tidligere har besøkt hver by.

De neste $m$ linjene inneholder hver to heltall $u_i, v_i$ ($1 \le u_i, v_i \le n$), som angir en urettet vei som forbinder by $u_i$ og by $v_i$. Det kan være flere kanter mellom samme byer og løkker. Med andre ord er det ikke garantert at $u_i \neq v_i$, og det er ikke garantert at $(u_i, v_i) \neq (u_j, v_j)$ for $i \neq j$.

Det er garantert at summen av $n$ og summen av $m$ over alle testtilfeller ikke overstiger henholdsvis $2 \times 10^5$.

Utdata

For hvert testtilfelle, hvis det ikke finnes noen gyldig reiseplan, skriv ut No på en enkelt linje.

Ellers skriv først ut Yes på en enkelt linje, og skriv deretter ut et heltall $k$ ($0 \le k \le 5n$) på neste linje, som representerer det totale antallet besøk i løpet av denne reisen. På den påfølgende linjen skriver du ut indeksene til byene som besøkes i rekkefølge.

Eksempler

Eksempelinndata 1

5
4 4 1
1 1 1 1
1 2
2 3
3 4
4 1
5 7 1
9 4 3 11 7
1 2
2 5
2 4
3 4
2 3
1 3
4 5
2 2 2
114 514
1 2
1 2
5 0 1
114 514 19 19 810
2 1 1
3 5
1 2

Eksempelutdata 1

Yes
4
2 3 4 1
Yes
6
2 4 5 2 3 1
Yes
0

No
Yes
2
2 1

Merk

For det første testtilfellet, etter å ha besøkt langs ruten $1 \to 2 \to 3 \to 4 \to 1$, har byene $1, 2, 3, 4$ blitt besøkt henholdsvis $2, 2, 2, 2$ ganger, noe som oppfyller kravet.

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.