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$번 방문하게 되어 조건을 만족합니다.