問題一覧 > 通常問題

No.2202 贅沢てりたまチキン

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 142
作問者 : H20H20 / テスター : 👑 p-adicp-adic
3 ProblemId : 9114 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-31 22:03:30

問題文

ゆきこ鉄道には $N$ 個の駅 $($ 駅 $1,$ 駅 $2, \ldots,$ 駅 $N )$ と $2$ 本の線路の組が $M$ 個あります。

$i$ 個目の組は、異なる $2$ つの駅 $A_i$ の地上と駅 $B_i$ の地下、駅 $A_i$ の地下と駅 $B_i$ の地上を双方向に結ぶように引かれている 2 本の線路からなります。

鉄道に走る線路だけを使用して各駅の地上と地下を往来することが出来るかを答えてください。

入力

$N\ M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

制約

  • $ 1 \le N \le 2\times10^{5}$
  • $ 0 \le M \le \min(2\times10^{5},\frac{N(N-1)}{2})$
  • $ 1 \le A_i, B_i \le N$
  • $ A_i \neq B_i$
  • $\{A_i,B_i\} \neq \{A_j,B_j\}$（$1 \leq i \neq j \leq N$）
  • 入力は全て整数

出力

鉄道に走る線路だけを使用して各駅の地上と地下を往来することが出来るなら Yes 、そうでないなら No と出力してください。

最後に改行してください。

サンプル

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

それぞれ以下のように地上から地下へ移動できます。逆方向を考えると地下から地上へも移動できるため、往来可能です。

駅 $1$ 地上　→　駅 $2$ 地下　→　駅 $3$ 地上　→　駅 $4$ 地下　→　駅 $2$ 地上　→　駅 $1$ 地下

駅 $2$ 地上　→　駅 $3$ 地下　→　駅 $4$ 地上　→　駅 $2$ 地下

駅 $3$ 地上　→　駅 $4$ 地下　→　駅 $2$ 地上　→　駅 $3$ 地下

駅 $4$ 地上　→　駅 $2$ 地下　→　駅 $3$ 地上　→　駅 $4$ 地下

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

どの駅についても各駅の地上と地下の往来はできません。

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

駅 $6$ が、地上と地下を往来が出来ません。

このように往来できない駅が $1$ つでもあればNoと出力してください。

サンプル4
入力
9 10
1 3
9 4
3 6
2 6
6 8
3 8
5 4
7 4
5 9
2 8
出力
Yes

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