Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 1024 MB Toplam puan: 100
İstatistikler

Dingdong prévoit de voyager dans le pays de Hamu.

Le pays de Hamu se compose de $n$ villes et de $m$ routes bidirectionnelles. Avant ce voyage, Dingdong a déjà visité la ville $i$ exactement $a_i$ fois. Au cours de ce voyage, Dingdong prévoit d'entrer à Hamu par la ville $s$. Chaque jour suivant, Dingdong empruntera une certaine route vers une ville et visitera cette ville une fois. À la fin de la visite du dernier jour, Dingdong doit se trouver dans la ville $s$ et quitter Hamu depuis la ville $s$. Notez que le jour de son entrée dans le pays de Hamu, Dingdong ne visite pas la ville $s$.

Dingdong espère qu'après ce voyage, en comptant ses visites précédentes, chaque ville de Hamu aura été visitée par lui un nombre pair de fois. Dingdong dispose d'un temps limité et peut visiter au plus $5n$ villes au cours de ce voyage. Veuillez l'aider à construire un plan de voyage valide, ou lui dire si c'est impossible.

Entrée

L'entrée contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 2 \times 10^5$), le nombre de cas de test.

Pour chaque cas de test, la première ligne contient trois entiers $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), où $n$ est le nombre de villes, $m$ est le nombre de routes et $s$ est l'indice de la ville de départ.

La ligne suivante contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), le nombre de fois que Dingdong a déjà visité chaque ville.

Les $m$ lignes suivantes contiennent chacune deux entiers $u_i, v_i$ ($1 \le u_i, v_i \le n$), indiquant une route non orientée reliant la ville $u_i$ et la ville $v_i$. Il peut y avoir des arêtes multiples et des boucles. En d'autres termes, il n'est pas garanti que $u_i \neq v_i$, et il n'est pas garanti que $(u_i, v_i) \neq (u_j, v_j)$ pour $i \neq j$.

Il est garanti que la somme de $n$ et la somme de $m$ sur l'ensemble des cas de test ne dépassent pas $2 \times 10^5$, respectivement.

Sortie

Pour chaque cas de test, s'il n'existe aucun plan de voyage valide, affichez No sur une seule ligne.

Sinon, affichez d'abord Yes sur une seule ligne, puis un entier $k$ ($0 \le k \le 5n$) sur la ligne suivante, représentant le nombre total de visites au cours de ce voyage. Sur la ligne d'après, affichez dans l'ordre les indices des villes visitées.

Exemples

Exemple d'entrée 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

Exemple de sortie 1

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

No
Yes
2
2 1

Note

Pour le premier cas de test, après avoir suivi l'itinéraire $1 \to 2 \to 3 \to 4 \to 1$, les villes $1, 2, 3, 4$ ont été visitées respectivement $2, 2, 2, 2$ fois, ce qui satisfait l'exigence.

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.