Universal Cup Judging System

Universal Cup

時間限制: 1.0 s 記憶體限制: 1024 MB 總分: 100
统计

Dingdong planerar att resa till landet Hamu.

Landet Hamu består av $n$ städer och $m$ dubbelriktade vägar. Före denna resa har Dingdong redan besökt stad $i$ exakt $a_i$ gånger. Under denna resa planerar Dingdong att resa in i Hamu vid stad $s$. Under varje efterföljande dag kommer Dingdong att resa längs en viss väg till en stad och besöka den staden en gång. I slutet av den sista dagens besök ska Dingdong befinna sig i stad $s$ och lämna Hamu från stad $s$. Observera att på dagen då Dingdong reser in i landet Hamu besöker han inte stad $s$.

Dingdong hoppas att varje stad i Hamu efter denna resa, sammanräknat med hans tidigare besök, ska ha besökts av honom ett jämnt antal gånger. Dingdong har begränsad tid och kan besöka högst $5n$ städer under denna resa. Hjälp honom att konstruera en giltig resplan, eller tala om för honom om det är omöjligt.

Indata

Indatan innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 2 \times 10^5$), antalet testfall.

För varje testfall innehåller den första raden tre heltal $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), där $n$ är antalet städer, $m$ är antalet vägar och $s$ är indexet för startstaden.

Nästa rad innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), antalet gånger Dingdong redan har besökt respektive stad.

De följande $m$ raderna innehåller var och en två heltal $u_i, v_i$ ($1 \le u_i, v_i \le n$), vilket anger en oriktad väg som förbinder stad $u_i$ och stad $v_i$. Det kan förekomma multipla kanter och öglor. Med andra ord garanteras det inte att $u_i \neq v_i$, och det garanteras inte heller att $(u_i, v_i) \neq (u_j, v_j)$ för $i \neq j$.

Det garanteras att summan av $n$ och summan av $m$ över alla testfall inte överstiger $2 \times 10^5$ vardera.

Utdata

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

Annars, skriv först ut Yes på en egen rad, och skriv sedan på nästa rad ut ett heltal $k$ ($0 \le k \le 5n$), som representerar det totala antalet besök under denna resa. På följande rad skriver du i ordning ut indexen för de besökta städerna.

Exempel

Exempelindata 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

Exempelutdata 1

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

No
Yes
2
2 1

Förklaring

För det första testfallet har städerna $1, 2, 3, 4$ efter besök längs rutten $1 \to 2 \to 3 \to 4 \to 1$ besökts $2, 2, 2, 2$ gånger respektive, vilket uppfyller 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.