Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100
الإحصائيات

Dingdong dự định đi du lịch đến đất nước Hamu.

Đất nước Hamu bao gồm $n$ thành phố và $m$ con đường hai chiều. Trước chuyến đi này, Dingdong đã ghé thăm thành phố $i$ đúng $a_i$ lần. Trong chuyến đi này, Dingdong dự định nhập cảnh vào Hamu tại thành phố $s$. Vào mỗi ngày tiếp theo, Dingdong sẽ đi dọc theo một con đường nào đó đến một thành phố và ghé thăm thành phố đó một lần. Khi kết thúc chuyến thăm của ngày cuối cùng, Dingdong phải ở tại thành phố $s$ và rời khỏi Hamu từ thành phố $s$. Lưu ý rằng vào ngày nhập cảnh vào đất nước Hamu, Dingdong không ghé thăm thành phố $s$.

Dingdong hy vọng rằng sau chuyến đi này, cộng với những lần ghé thăm trước đó, mọi thành phố ở Hamu đều sẽ được anh ghé thăm một số chẵn lần. Dingdong có thời gian hạn chế và chỉ có thể ghé thăm tối đa $5n$ thành phố trong chuyến đi này. Hãy giúp anh ấy xây dựng một kế hoạch du lịch hợp lệ, hoặc cho anh ấy biết nếu điều đó là không thể.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 2 \times 10^5$), là số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa ba số nguyên $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$), trong đó $n$ là số thành phố, $m$ là số con đường, $s$ là chỉ số của thành phố xuất phát.

Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$), là số lần Dingdong đã ghé thăm mỗi thành phố trước đó.

Trong $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le n$), biểu thị một con đường vô hướng nối thành phố $u_i$ và thành phố $v_i$. Có thể có đa cạnh và khuyên. Nói cách khác, không đảm bảo rằng $u_i \neq v_i$, và cũng không đảm bảo rằng $(u_i, v_i) \neq (u_j, v_j)$ với $i \neq j$.

Đảm bảo rằng tổng của $n$ và tổng của $m$ trên tất cả các bộ test lần lượt không vượt quá $2 \times 10^5$.

Kết quả

Với mỗi bộ test, nếu không có kế hoạch du lịch hợp lệ, hãy in ra No trên một dòng.

Ngược lại, trước tiên hãy in ra Yes trên một dòng, sau đó in một số nguyên $k$ ($0 \le k \le 5n$) ở dòng tiếp theo, biểu thị tổng số lần ghé thăm trong chuyến đi này. Ở dòng tiếp theo nữa, hãy in ra chỉ số của các thành phố được ghé thăm theo đúng thứ tự.

Ví dụ

Dữ liệu vào mẫu 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

Kết quả mẫu 1

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

No
Yes
2
2 1

Ghi chú

Ở bộ test đầu tiên, sau khi đi thăm theo lộ trình $1 \to 2 \to 3 \to 4 \to 1$, các thành phố $1, 2, 3, 4$ lần lượt được ghé thăm $2, 2, 2, 2$ lần, thỏa mãn yêu cầu.

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.