Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 1024 MB Points totaux : 100
Statistiques

Диндон планирует отправиться в путешествие по стране Хаму.

Страна Хаму состоит из $n$ городов и $m$ двусторонних дорог. До этой поездки Диндон уже посетил город $i$ ровно $a_i$ раз. Во время этой поездки Диндон планирует въехать в Хаму через город $s$. В каждый последующий день Диндон будет переезжать по некоторой дороге в какой-то город и посещать этот город один раз. В конце последнего дня путешествия Диндон должен оказаться в городе $s$ и покинуть Хаму из города $s$. Обратите внимание, что в день въезда в страну Хаму Диндон не посещает город $s$.

Диндон надеется, что после этой поездки, с учётом его предыдущих визитов, каждый город в Хаму будет посещён им чётное число раз. Время Диндона ограничено, поэтому за эту поездку он может посетить не более $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$) — количество раз, которое Диндон уже посещал каждый город.

Следующие $m$ строк содержат по два целых числа $u_i, v_i$ ($1 \le u_i, v_i \le n$), обозначающих неориентированную дорогу, соединяющую город $u_i$ и город $v_i$. Могут присутствовать кратные рёбра и петли. Иными словами, не гарантируется, что $u_i \neq v_i$, и не гарантируется, что $(u_i, v_i) \neq (u_j, v_j)$ при $i \neq 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.