CF453C Little Pony and Summer Sun Celebration

暮光闪闪得知邪恶的 Nightmare Moon 在被囚禁在月球上一千年后，将于即将到来的夏日阳光庆典期间回归。她试图警告她的导师塞莱斯蒂娅公主，但公主并未理会她，反而让她前往小马镇检查庆典的准备情况。 暮光闪闪想追踪 Nightmare Moon 的行踪，但她并不知道具体路径。她唯一知道的是 Nightmare Moon 在每个地点经过的次数的奇偶性。你能帮助暮光闪闪还原出任一条与这些信息一致的路径吗？ 小马镇可以表示为一张无向图（顶点表示地点，边表示地点之间的道路），没有自环和重边。路径可以从任意地点开始和结束（也可以为空路径），每个地点可以被访问多次。路径中经过的地点数不得超过 $4n$。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$0 \leq m \leq 10^5$），分别表示小马镇中的地点数和道路数。接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$），表示一条连接地点 $u_i$ 和 $v_i$ 的道路。 下一行包含 $n$ 个整数，$x_1, x_2, ..., x_n$（$0 \leq x_i \leq 1$），表示每个地点需要被访问的奇偶性。如果 $x_i=0$，则第 $i$ 个地点需要被访问偶数次，否则需要被访问奇数次。

第一行输出被访问的地点数 $k$（$0 \leq k \leq 4n$）。第二行输出 $k$ 个整数，表示路径中各个地点按顺序的编号。如果 $x_i=0$，则第 $i$ 个地点在路径中出现的次数为偶数，否则为奇数。请注意，图中没有自环，因此路径中任何两个相邻的地点必须不同。 如果不存在这样的路径，输出 $-1$。如果有多种方案，输出任意一种均可。

由 ChatGPT 5 翻译