← 返回题目列表

AtCoder · arc164_b

B. 切换行程

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

分数: 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

在此图中,无论您选择哪个顶点作为起点,您都无法通过满足条件的移动返回到起点。