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$ 次,符合要求。