Universal Cup Judging System

Universal Cup

시간 제한: 1.0 s 메모리 제한: 1024 MB 총점: 100
통계

Dingdong은 Hamu 나라로 여행을 떠날 계획입니다.

Hamu 나라는 $n$개의 도시와 $m$개의 양방향 도로로 이루어져 있습니다. 이번 여행 전에 Dingdong은 이미 도시 $i$를 정확히 $a_i$번 방문했습니다. 이번 여행에서 Dingdong은 도시 $s$를 통해 Hamu 나라에 입국할 계획입니다. 그다음 날부터 매일 Dingdong은 어떤 도로를 따라 한 도시로 이동하여 그 도시를 한 번 방문합니다. 마지막 날의 방문이 끝났을 때, Dingdong은 도시 $s$에 있어야 하며 도시 $s$에서 Hamu 나라를 떠나야 합니다. 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$는 시작 도시의 번호입니다.

다음 줄에는 Dingdong이 각 도시를 이전에 방문했던 횟수를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)이 주어집니다.

그다음 $m$개의 줄에는 각각 두 정수 $u_i, v_i$ ($1 \le u_i, v_i \le n$)가 주어지며, 이는 도시 $u_i$와 도시 $v_i$를 잇는 무방향 도로를 나타냅니다. 중복 간선과 자기 루프가 있을 수 있습니다. 즉, $u_i \neq v_i$임이 보장되지 않으며, $i \neq j$일 때 $(u_i, v_i) \neq (u_j, v_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.