Universal Cup Judging System

Universal Cup

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

Dingdong berencana melakukan perjalanan ke negara Hamu.

Negara Hamu terdiri dari $n$ kota dan $m$ jalan dua arah. Sebelum perjalanan ini, Dingdong telah mengunjungi kota $i$ tepat sebanyak $a_i$ kali. Selama perjalanan ini, Dingdong berencana masuk ke Hamu melalui kota $s$. Pada setiap hari berikutnya, Dingdong akan melakukan perjalanan melewati suatu jalan menuju sebuah kota dan mengunjungi kota tersebut satu kali. Pada akhir kunjungan hari terakhir, Dingdong harus berada di kota $s$ dan meninggalkan Hamu dari kota $s$. Perhatikan bahwa pada hari masuk ke negara Hamu, Dingdong tidak mengunjungi kota $s$.

Dingdong berharap setelah perjalanan ini, digabungkan dengan kunjungan-kunjungan sebelumnya, setiap kota di Hamu telah ia kunjungi sebanyak genap kali. Dingdong memiliki waktu terbatas dan hanya dapat mengunjungi paling banyak $5n$ kota selama perjalanan ini. Bantulah ia menyusun rencana perjalanan yang valid, atau beri tahu ia jika hal tersebut tidak mungkin.

Masukan

Masukan terdiri dari beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 2 \times 10^5$), yaitu banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi tiga bilangan bulat $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), dengan $n$ adalah banyaknya kota, $m$ adalah banyaknya jalan, dan $s$ adalah indeks kota awal.

Baris berikutnya berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), yaitu banyaknya kunjungan yang telah dilakukan Dingdong ke masing-masing kota.

Sebanyak $m$ baris berikutnya masing-masing berisi dua bilangan bulat $u_i, v_i$ ($1 \le u_i, v_i \le n$), yang menyatakan jalan tak berarah yang menghubungkan kota $u_i$ dan kota $v_i$. Dapat terdapat sisi ganda maupun gelung (self-loop). Dengan kata lain, tidak dijamin bahwa $u_i \neq v_i$, dan tidak dijamin bahwa $(u_i, v_i) \neq (u_j, v_j)$ untuk $i \neq j$.

Dijamin bahwa jumlah $n$ dan jumlah $m$ di seluruh kasus uji masing-masing tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, jika tidak ada rencana perjalanan yang valid, cetak No dalam satu baris.

Jika ada, cetak Yes terlebih dahulu dalam satu baris, kemudian cetak sebuah bilangan bulat $k$ ($0 \le k \le 5n$) pada baris berikutnya yang menyatakan total kunjungan selama perjalanan ini. Pada baris selanjutnya, cetak indeks kota-kota yang dikunjungi secara berurutan.

Contoh

Contoh Masukan 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

Contoh Keluaran 1

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

No
Yes
2
2 1

Catatan

Untuk kasus uji pertama, setelah berkunjung mengikuti rute $1 \to 2 \to 3 \to 4 \to 1$, kota $1, 2, 3, 4$ masing-masing telah dikunjungi sebanyak $2, 2, 2, 2$ kali, sehingga memenuhi syarat.

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.