分数: 500 点
问题陈述
有一个简单的连通无向图 N 顶点编号自 1 to N。 该图有 M 边缘,以及 i第一条边连接两个顶点 a_i 和 b_i.
每个顶点都有一种颜色,白色或黑色,初始状态由下式给出 c_i. c_i 是 0 or 1,其中 c_i=0 表示顶点 i 最初是白色的,并且 c_i=1 表示顶点 i 最初是黑色的。
在此图上,您可以选择任何顶点作为起点,并根据需要多次重复以下操作。
- 移动到由当前顶点的边连接的不同颜色的顶点。移动后,立即反转您移动的顶点的颜色(如果是白色,则更改为黑色,反之亦然)。
至少执行一次操作后是否可以返回起点?
约束
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq \mathrm{min} \lbrace 2 \times 10^5,N(N-1)/2 \rbrace
- 1 \leq a_i, b_i \leq N (1 \leq i \leq M)
- c_i=0 or c_i=1 (1 \leq i \leq N)
- 给定的图很简单且连通。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 \vdots a_M b_M c_1 c_2 \ldots c_N
输出
如果至少执行一次操作后可以返回起点,则打印 Yes;否则,打印 No.
示例输入 1
4 4 1 2 2 3 3 4 4 2 0 1 0 1
示例输出 1
Yes
例如,考虑从顶点开始 1。 在第一个操作中,移动到顶点 2 并更改顶点的颜色 1 从白到黑。图形的这种变化如下图所示(圈出的顶点是当前顶点)。
然后,如果移动到顶点 3, 4,和 2 按顺序,顶点的颜色 1,2,3,4 将分别为黑色、白色、黑色和白色。 因此,您可以移动到顶点 1 在下一步操作中,返回起始点。

示例输入 2
5 6 1 2 2 3 3 4 4 5 1 4 2 5 0 1 0 1 0
示例输出 2
No
在此图中,无论您选择哪个顶点作为起点,您都无法通过满足条件的移动返回到起点。