Universal Cup Judging System

Universal Cup

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

Dingdong 計劃去 Hamu 國旅行。

Hamu 國由 $n$ 個城市同 $m$ 條雙向道路組成。喺今次旅行之前,Dingdong 已經去過城市 $i$ 啱啱好 $a_i$ 次。喺今次旅行入面,Dingdong 計劃由城市 $s$ 入境 Hamu 國。喺之後嘅每一日,Dingdong 都會沿住某一條路去一個城市並且遊覽嗰個城市一次。喺最後一日嘅遊覽結束嗰陣,Dingdong 應該身處城市 $s$,然後由城市 $s$ 離開 Hamu 國。請注意,喺入境 Hamu 國嗰一日,Dingdong 並唔會遊覽城市 $s$。

Dingdong 希望喺今次旅行之後,夾埋佢之前嘅遊覽紀錄,Hamu 國嘅每一個城市都被佢遊覽咗雙數次。Dingdong 嘅時間有限,喺今次旅行入面最多只可以遊覽 $5n$ 個城市。請幫佢構造一個可行嘅旅行計劃,或者話畀佢聽係咪無可能。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $T$($1 \le T \le 2 \times 10^5$),代表測試資料嘅組數。

對於每組測試資料,第一行包含三個整數 $n, m, s$($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$),其中 $n$ 係城市數量,$m$ 係道路數量,$s$ 係起點城市嘅編號。

下一行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$($0 \le a_i \le 10^9$),代表 Dingdong 之前去過每個城市嘅次數。

接住落嚟嘅 $m$ 行,每行包含兩個整數 $u_i, v_i$($1 \le u_i, v_i \le n$),代表一條連接城市 $u_i$ 同城市 $v_i$ 嘅無向道路。可能存在重邊同自環。換句話講,唔保證 $u_i \neq v_i$,亦都唔保證對於 $i \neq j$ 有 $(u_i, v_i) \neq (u_j, v_j)$。

保證所有測試資料入面 $n$ 嘅總和同埋 $m$ 嘅總和分別唔超過 $2 \times 10^5$。

輸出格式

對於每組測試資料,如果唔存在可行嘅旅行計劃,請單獨輸出一行 No。

否則,首先單獨輸出一行 Yes,然後喺下一行輸出一個整數 $k$($0 \le k \le 5n$),代表今次旅行入面嘅總遊覽次數。喺跟住落嚟嗰一行,按順序輸出所遊覽嘅城市編號。

範例

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

範例輸出 1

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

No
Yes
2
2 1

提示

對於第一組測試資料,沿住路線 $1 \to 2 \to 3 \to 4 \to 1$ 遊覽之後,城市 $1, 2, 3, 4$ 分別被遊覽咗 $2, 2, 2, 2$ 次,符合要求。

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.