Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100
統計

Dingdong plant eine Reise in das Land Hamu.

Das Land Hamu besteht aus $n$ Städten und $m$ Straßen in beide Richtungen. Vor dieser Reise hat Dingdong die Stadt $i$ bereits genau $a_i$-mal besucht. Auf dieser Reise plant Dingdong, über die Stadt $s$ nach Hamu einzureisen. An jedem darauffolgenden Tag reist Dingdong über eine bestimmte Straße in eine Stadt und besucht diese Stadt einmal. Am Ende des Besuchs am letzten Tag muss sich Dingdong in der Stadt $s$ befinden und Hamu von der Stadt $s$ aus verlassen. Beachte, dass Dingdong am Tag der Einreise in das Land Hamu die Stadt $s$ nicht besucht.

Dingdong hofft, dass nach dieser Reise – zusammen mit seinen früheren Besuchen – jede Stadt in Hamu eine gerade Anzahl von Malen von ihm besucht worden ist. Dingdong hat nur begrenzt Zeit und kann während dieser Reise höchstens $5n$ Städte besuchen. Bitte hilf ihm, einen gültigen Reiseplan zu erstellen, oder teile ihm mit, falls dies unmöglich ist.

Eingabe

Die Eingabe enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 2 \times 10^5$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile drei ganze Zahlen $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), wobei $n$ die Anzahl der Städte, $m$ die Anzahl der Straßen und $s$ der Index der Startstadt ist.

Die nächste Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), die angeben, wie oft Dingdong jede Stadt bereits besucht hat.

Die nächsten $m$ Zeilen enthalten jeweils zwei ganze Zahlen $u_i, v_i$ ($1 \le u_i, v_i \le n$), die eine ungerichtete Straße zwischen Stadt $u_i$ und Stadt $v_i$ angeben. Es kann Mehrfachkanten und Selbstschleifen geben. Mit anderen Worten ist weder $u_i \neq v_i$ noch $(u_i, v_i) \neq (u_j, v_j)$ für $i \neq j$ garantiert.

Es wird garantiert, dass die Summe über alle $n$ sowie die Summe über alle $m$ über alle Testfälle hinweg jeweils $2 \times 10^5$ nicht überschreitet.

Ausgabe

Für jeden Testfall gib No in einer einzelnen Zeile aus, falls es keinen gültigen Reiseplan gibt.

Andernfalls gib zuerst Yes in einer einzelnen Zeile aus, und gib dann in der nächsten Zeile eine ganze Zahl $k$ ($0 \le k \le 5n$) aus, die die Gesamtzahl der Besuche während dieser Reise darstellt. Gib in der darauffolgenden Zeile die Indizes der besuchten Städte in der besuchten Reihenfolge aus.

Beispiele

Beispieleingabe 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

Beispielausgabe 1

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

No
Yes
2
2 1

Hinweis

Für den ersten Testfall wurden nach dem Besuch entlang der Route $1 \to 2 \to 3 \to 4 \to 1$ die Städte $1, 2, 3, 4$ jeweils $2, 2, 2, 2$-mal besucht, was die Anforderung erfüllt.

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.