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.