Universal Cup Judging System

Universal Cup

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

يخطط Dingdong للسفر إلى دولة Hamu.

تتكون دولة Hamu من $n$ مدن و $m$ طرق ثنائية الاتجاه. قبل هذه الرحلة، زار Dingdong المدينة $i$ بالضبط $a_i$ من المرات. خلال هذه الرحلة، يخطط Dingdong لدخول Hamu عبر المدينة $s$. وفي كل يوم تالٍ، سيسافر Dingdong عبر طريق معين إلى إحدى المدن ويزور تلك المدينة مرة واحدة. وفي نهاية زيارة اليوم الأخير، يجب أن يكون Dingdong في المدينة $s$ ويغادر Hamu من المدينة $s$. لاحظ أنه في يوم دخول دولة Hamu، لا يزور Dingdong المدينة $s$.

يأمل Dingdong أنه بعد هذه الرحلة، بالإضافة إلى زياراته السابقة، ستكون كل مدينة في Hamu قد زارها عدداً زوجياً من المرات. وقت Dingdong محدود ويمكنه زيارة ما لا يزيد عن $5n$ مدينة خلال هذه الرحلة. يرجى مساعدته في بناء خطة رحلة صالحة، أو إخباره إذا كان ذلك مستحيلاً.

الإدخال

يحتوي الإدخال على عدة حالات اختبار. السطر الأول من الإدخال يحتوي على عدد صحيح $T$ ($1 \le T \le 2 \times 10^5$)، وهو عدد حالات الاختبار.

لكل حالة اختبار، يحتوي السطر الأول على ثلاثة أعداد صحيحة $n, m, s$ ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5, 1 \le s \le n$)، حيث $n$ هو عدد المدن، و $m$ هو عدد الطرق، و $s$ هو رقم مدينة البداية.

يحتوي السطر التالي على $n$ أعداد صحيحة $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)، وهي عدد المرات التي زار فيها Dingdong كل مدينة سابقاً.

تحتوي الأسطر الـ $m$ التالية في كل منها على عددين صحيحين $u_i, v_i$ ($1 \le u_i, v_i \le n$)، للإشارة إلى طريق غير موجه يربط بين المدينة $u_i$ والمدينة $v_i$. يمكن أن توجد حواف متعددة وحلقات ذاتية. بمعنى آخر، ليس من المضمون أن $u_i \neq v_i$، وليس من المضمون أن $(u_i, v_i) \neq (u_j, v_j)$ عندما $i \neq j$.

من المضمون أن مجموع $n$ ومجموع $m$ عبر جميع حالات الاختبار لا يتجاوزان $2 \times 10^5$ على التوالي.

الإخراج

لكل حالة اختبار، إذا لم تكن هناك خطة رحلة صالحة، اطبع No في سطر مستقل.

وإلا، اطبع أولاً Yes في سطر مستقل، ثم اطبع عدداً صحيحاً $k$ ($0 \le k \le 5n$) في السطر التالي يمثل إجمالي عدد الزيارات خلال هذه الرحلة. وفي السطر الذي يليه، اطبع أرقام المدن التي تمت زيارتها بالترتيب.

أمثلة

مثال الإدخال 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

مثال الإخراج 1

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

No
Yes
2
2 1

ملاحظة

بالنسبة لحالة الاختبار الأولى، بعد الزيارة على طول المسار $1 \to 2 \to 3 \to 4 \to 1$، تكون المدن $1, 2, 3, 4$ قد زيرت $2, 2, 2, 2$ مرات على التوالي، وهو ما يحقق المطلوب.

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.