Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100
Estadísticas

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.