Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 1024 MB Total points: 100
Statistics

Dingdong planea viajar al país de Hamu.

El país de Hamu consta de $n$ ciudades y $m$ carreteras bidireccionales. Antes de este viaje, Dingdong ya ha visitado la ciudad $i$ exactamente $a_i$ veces. Durante este viaje, Dingdong planea entrar a Hamu por la ciudad $s$. En cada día subsiguiente, Dingdong viajará por cierta carretera hasta una ciudad y visitará esa ciudad una vez. Al final de la visita del último día, Dingdong debe estar en la ciudad $s$ y salir de Hamu desde la ciudad $s$. Ten en cuenta que el día en que entra al país de Hamu, Dingdong no visita la ciudad $s$.

Dingdong espera que después de este viaje, sumado a sus visitas anteriores, cada ciudad de Hamu haya sido visitada por él un número par de veces. Dingdong tiene tiempo limitado y puede visitar como máximo $5n$ ciudades durante este viaje. Por favor, ayúdalo a construir un plan de viaje válido, o dile si es imposible.

Entrada

La entrada contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 2 \times 10^5$), el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene tres enteros $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), donde $n$ es el número de ciudades, $m$ es el número de carreteras y $s$ es el índice de la ciudad inicial.

La siguiente línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), el número de veces que Dingdong ha visitado cada ciudad.

Las siguientes $m$ líneas contienen cada una dos enteros $u_i, v_i$ ($1 \le u_i, v_i \le n$), que indican una carretera no dirigida que conecta la ciudad $u_i$ y la ciudad $v_i$. Puede haber aristas múltiples y bucles. En otras palabras, no se garantiza que $u_i \neq v_i$, ni se garantiza que $(u_i, v_i) \neq (u_j, v_j)$ para $i \neq j$.

Se garantiza que la suma de $n$ y la suma de $m$ en todos los casos de prueba no superan $2 \times 10^5$, respectivamente.

Salida

Para cada caso de prueba, si no existe un plan de viaje válido, imprime No en una sola línea.

En caso contrario, imprime primero Yes en una sola línea y luego un entero $k$ ($0 \le k \le 5n$) en la línea siguiente, que representa el número total de visitas durante este viaje. En la línea siguiente, imprime en orden los índices de las ciudades visitadas.

Ejemplos

Entrada de ejemplo 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

Salida de ejemplo 1

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

No
Yes
2
2 1

Nota

Para el primer caso de prueba, tras visitar siguiendo la ruta $1 \to 2 \to 3 \to 4 \to 1$, las ciudades $1, 2, 3, 4$ han sido visitadas $2, 2, 2, 2$ veces respectivamente, cumpliendo el requisito.

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.