← 返回题目列表

Codeforces · 453/C

C. 小马驹和夏日阳光庆典

中文机器翻译题面 查看原题

暮光闪闪获悉邪恶的梦魇之月将在即将到来的夏日太阳庆典期间在月球上被囚禁一千年后回归。她试图警告她的导师塞拉斯蒂娅公主,但公主没有理睬她,而是派她去小马镇检查庆祝活动的准备情况。

暮光闪闪想要追踪梦魇之月的踪迹。可惜,她并不知道具体的路。她所知道的是梦魇之月到过每个地方的次数的平价。你能帮助暮光闪闪恢复任何与此信息一致的路径吗?

Ponyville 可以表示为无向图(顶点是地点,边是地点之间的道路),没有自环和多边。路径可以在任何地方开始和结束(也可以是空的)。每个地方都可以多次参观。该路径不得访问超过 4n 个地点。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105) — Ponyville 中的地点数量和道路数量。接下来的 m 行每行包含两个整数 ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi),这些整数描述了 ui 和 vi 之间的一条道路。

下一行包含 n 个整数:x1, x2, ..., xn (0 ≤ xi ≤ 1) — 每个位置必须访问的次数的奇偶校验。如果 xi = 0,则第 i 个地点必须被访问偶数次,否则必须被访问奇数次。

输出

输出第一行中访问过的地点 k 的数量 (0 ≤ k ≤ 4n)。然后输出 k 个整数——路径顺序中的位数。如果 xi = 0,则第 i 个位置必须在路径中出现偶数次,否则第 i 个位置必须在路径中出现奇数次。请注意,给定的道路系统没有自环,因此路径中的任何两个相邻位置必须是不同的。

如果没有所需的路径,则输出-1。如果有多个可能的路径,则可以输出其中任何一个。

示例

输入 #1

3 2
1 2
2 3
1 1 1

输出 #1

3
1 2 3

输入 #2

5 7
1 2
1 3
1 4
1 5
3 4
3 5
4 5
0 1 0 1 0

输出 #2

10
2 1 3 4 5 4 5 4 3 1

输入 #3

2 0
0 0

输出 #3

0