P17122 [ICPC 2025 Shanghai R] Hamu

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

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$ 为起始城市的编号。 接下来一行包含 $n$ 个整数 $a_1, a_2, \cdots, 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 \ne v_i$，也**不**保证对于 $i \ne j$ 有 $(u_i, v_i) \ne (u_j, v_j)$。 保证所有测试用例的 $n$ 之和与 $m$ 之和分别不超过 $2 \times 10^5$。

对于每组测试用例，如果不存在可行的旅行计划，则输出一行 `No`。 否则，首先输出一行 `Yes`，然后在接下来的一行输出一个整数 $k$ ($0 \le k \le 5n$)，表示本次旅行中访问城市的总次数。再接下来的一行，按顺序输出访问的城市的编号。

对于第一个测试用例，按照路线 $1 \to 2 \to 3 \to 4 \to 1$ 访问后，城市 $1, 2, 3, 4$ 分别被访问了 $2, 2, 2, 2$ 次，满足要求。 翻译由 DeepSeek V4 Pro 完成