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 planuje podróż do kraju Hamu.

Kraj Hamu składa się z $n$ miast i $m$ dwukierunkowych dróg. Przed tą podróżą Dingdong odwiedził już miasto $i$ dokładnie $a_i$ razy. Podczas tej podróży Dingdong planuje wjechać do Hamu w mieście $s$. Każdego kolejnego dnia Dingdong przejedzie pewną drogą do jakiegoś miasta i odwiedzi je jeden raz. Na koniec wizyty ostatniego dnia Dingdong powinien znajdować się w mieście $s$ i opuścić Hamu z miasta $s$. Zauważ, że w dniu wjazdu do kraju Hamu Dingdong nie odwiedza miasta $s$.

Dingdong ma nadzieję, że po tej podróży, łącznie z jego wcześniejszymi wizytami, każde miasto w Hamu zostanie przez niego odwiedzone parzystą liczbę razy. Dingdong ma ograniczony czas i może odwiedzić co najwyżej $5n$ miast podczas tej podróży. Pomóż mu skonstruować poprawny plan podróży lub poinformuj go, że jest to niemożliwe.

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 2 \times 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera trzy liczby całkowite $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), gdzie $n$ to liczba miast, $m$ to liczba dróg, a $s$ to numer miasta początkowego.

Kolejny wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), oznaczających, ile razy Dingdong odwiedził dotąd poszczególne miasta.

Kolejne $m$ wierszy zawiera po dwie liczby całkowite $u_i, v_i$ ($1 \le u_i, v_i \le n$), oznaczające nieskierowaną drogę łączącą miasto $u_i$ oraz miasto $v_i$. Mogą występować krawędzie wielokrotne oraz pętle własne. Innymi słowy, nie jest gwarantowane, że $u_i \neq v_i$, ani że $(u_i, v_i) \neq (u_j, v_j)$ dla $i \neq j$.

Gwarantuje się, że suma wartości $n$ oraz suma wartości $m$ po wszystkich przypadkach testowych nie przekraczają odpowiednio $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego, jeśli nie istnieje poprawny plan podróży, wypisz No w pojedynczym wierszu.

W przeciwnym razie wypisz najpierw Yes w pojedynczym wierszu, a następnie w kolejnym wierszu wypisz liczbę całkowitą $k$ ($0 \le k \le 5n$), oznaczającą łączną liczbę odwiedzin podczas tej podróży. W następnym wierszu wypisz kolejno numery odwiedzanych miast.

Przykłady

Przykładowe wejście 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

Przykładowe wyjście 1

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

No
Yes
2
2 1

Uwaga

W pierwszym przypadku testowym po odwiedzeniu miast wzdłuż trasy $1 \to 2 \to 3 \to 4 \to 1$, miasta $1, 2, 3, 4$ zostały odwiedzone odpowiednio $2, 2, 2, 2$ razy, co spełnia wymagania.

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.