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$ は出発都市の番号です。

次の行には、Dingdong がこれまでに各都市を訪れた回数を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$($0 \le a_i \le 10^9$)が与えられます。

続く $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.