Switching Travel

时间限制：2s
空间限制：1024MB

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的简单连通无向图，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接 $a_i$ 与 $b_i$。每个顶点初始为白色或黑色，颜色由 $c_i\in\{0,1\}$ 给出。

你可以任选一个顶点作为起点，并重复以下移动任意多次：从当前顶点沿边移动到一个与当前顶点颜色不同的相邻顶点，随后立刻翻转移动前所在顶点的颜色。

请判断能否在至少移动一次后回到起点。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含两个整数 $a_i,b_i$，表示一条无向边。

最后一行包含 $N$ 个整数 $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

样例输入 2

5 6
1 2
2 3
3 4
4 5
1 4
2 5
0 1 0 1 0

样例输出 2

No

数据范围

对于所有数据，$2\le N\le2\times10^5$，$N-1\le M\le\min(2\times10^5,N(N-1)/2)$；图简单且连通，$c_i\in\{0,1\}$。