B - Switching Travel Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

頂点に 1 から N までの番号がついた N 頂点の単純、連結な無向グラフがあります。 このグラフには M 本の辺があり、 i 番目の辺は 2 頂点 a_i , b_i を結んでいます。

また、各頂点は白または黒の色を持ち、最初の状態が c_i で与えられます。 c_i は 0 または 1 であり、c_i=0 であれば頂点 i は初め白色であり、c_i=1 であれば頂点 i は初め黒色です。

あなたはこのグラフ上で、好きな頂点を 1 つ選んで出発点とし、

  • 今いる頂点と辺で結ばれた頂点のうち、今いる頂点と異なる色の頂点に移動する。その直後に、移動元の頂点の色を反転する（元の色が白なら黒に、黒なら白に変える）。

という動作を好きな回数繰り返します。

1 回以上の動作を行ったうえで、再び出発点に戻ってくることは可能でしょうか。

制約

  • 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 または 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

出力

1 回以上の動作を行ったうえで再び出発点に戻ってくることが可能な場合は 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

このグラフでは、どの頂点を出発点に選んでも、条件を満たすような移動を行って出発点に戻ってくることができません。

Score : 500 points

Problem Statement

There is a simple connected undirected graph with N vertices numbered from 1 to N. This graph has M edges, and the i-th edge connects two vertices a_i and b_i.

Each vertex has a color, either white or black, and the initial state is given by c_i. c_i is either 0 or 1, where c_i=0 means that vertex i is initially white, and c_i=1 means that vertex i is initially black.

On this graph, you can choose any vertex as your starting point and repeat the following operation as many times as you like.

  • Move to a vertex of a different color connected by an edge from the current vertex. Immediately after moving, reverse the color of the vertex you moved from (change to black if it was white, and vice versa).

Is it possible to return to the starting point after performing the operation at least once?

Constraints

  • 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)
  • The given graph is simple and connected.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M
c_1 c_2 \ldots c_N

Output

If it is possible to return to the starting point after performing the operation at least once, print Yes; otherwise, print No.

Sample Input 1

4 4
1 2
2 3
3 4
4 2
0 1 0 1

Sample Output 1

Yes

For example, consider starting from vertex 1. In the first operation, move to vertex 2 and change the color of the vertex 1 from white to black. This change in the graph is shown in the figure below (the vertex circled is the current vertex).

Then, if you move to vertices 3, 4, and 2 in order, the colors of vertices 1,2,3,4 will then be black, white, black, and white, respectively. Therefore, you can move to vertex 1 in the next operation, returning to the starting point.

Sample Input 2

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

Sample Output 2

No

In this graph, no matter which vertex you choose as the starting point, you cannot return to the starting point by making moves that satisfy the conditions.