問題一覧 > 通常問題

No.1610 She Loves Me, She Loves Me Not, ...

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : 👑 ygussanyygussany / テスター : kanra824kanra824 tatyamtatyam
0 ProblemId : 6382 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-21 18:19:57

問題文

F.F. 君は花占いが好きです. 普通の花占いに飽きた F.F. 君は,グラフで花占いをしようと考えました. 具体的には,以下の操作を可能な限り繰り返します.

操作: ちょうど $1$ 本の辺が接続するような頂点を任意に $1$ つ選び,接続する辺とともにグラフから取り除く.

グラフを見た F.F. 君は,実際に花占いをするのが面倒になってしまいました. F.F. 君が見たグラフが与えられるので,花占いの結果を Yes にできるかどうかを教えてあげてください. ここで,花占いの結果が Yes であるとは,上記の操作を奇数回行った直後に操作が不可能になることを指します.

入力

$N\ \ M$
$A_1\ \ B_1$
$A_2\ \ B_2$
$\hspace{5mm} \vdots$
$A_M\ \ B_M$

  • $1 \le N \le 5000$
  • $0 \le M \le 5000$
  • $1 \le A_i, B_i \le N,\ A_i \neq B_i \ \ (1 \le i \le M)$
  • $\{A_i, B_i\} \neq \{A_j, B_j\} \ \ (1 \le i < j \le M)$
  • 入力は全て整数である.
  • 与えられるグラフは単純無向グラフである.すなわち,辺に向きは定義されず,自己ループや平行辺を持たない.
  • 頂点には $1, 2, \dots, N$ の番号が付いている.
  • 辺には $1, 2, \dots, M$ の番号が付いている.
  • 辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結ぶ.

出力

奇数回目の操作を行った直後に操作が不可能になるような操作手順が存在するなら Yes を,そうでなければ No を出力してください.

サンプル

サンプル 1
入力
4 3
1 2
1 3
1 4
出力
Yes

最初,各頂点に接続する辺の数は順に $3, 1, 1, 1$ です. まず頂点 $2$ を取り除き,次に頂点 $3$ を取り除き,最後に頂点 $4$ を取り除くと,残った頂点 $1$ に接続する辺が無くなるため,ここで操作が終了します. 操作回数は $3$ 回で奇数なので,Yes を出力します.

サンプル 2
入力
3 3
1 2
2 3
3 1
出力
No

$1$ 回も操作できないこともあります.

サンプル 3
入力
5 3
1 2
2 3
4 5
出力
Yes

与えられるグラフは連結とは限りません.

サンプル4
入力
8 7
1 2
2 3
4 3
1 3
5 6
8 7
6 7
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。