No.583 鉄道同好会

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.583 鉄道同好会

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 186
作問者 :

nmnmnmnmnmnmnm / テスター :

はむこ

4 ProblemId : 1464 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-08-12 02:44:51

問題文

鉄道同好会のメンバーはyukicoder線のすべての特別列車に乗車を計画しています。

yukicoder線とは？

・西から東に走る分岐の無い一本の路線です。
・西から東へ $0$ 駅、 $1$ 駅、 $2$ 駅、・・・、 $N - 1$ 駅の順で $N$ 個の駅が存在します。
・yukicoder線には $M$ 個の特別列車が存在します。
・特別列車は $S a$ 駅から $S b$ 駅もしくは $S b$ 駅から $S a$ 駅まで乗ることができます。( $0 \leq S a < S b \leq N - 1$ )
・特別列車は途中下車することはできません。

鉄道同好会のメンバーの計画は？

・鉄道同好会のメンバーはyukicoder線の任意の駅に集合します。
・次に鉄道同好会のメンバーは特別列車のみで駅で乗り継ぎをし移動します。
・鉄道同好会のメンバーはある特別列車に片道どちらかに乗れば満足し、片道より多くその特別列車には乗りません。
・鉄道同好会のメンバーはyukicoder線に存在するすべての特別列車に乗ります。
・最後に鉄道同好会のメンバーはyukicoder線の任意の駅で解散します。

鉄道同好会の計画が達成できるか判定しましょう。

入力

 $N$   $M$ 
 $S a_{0}$   $S b_{0}$ 
 $S a_{1}$   $S b_{1}$ 
 $⋮$ 
 $S a_{M - 1}$   $S b_{M - 1}$

$N$ はyukicoder線の駅の数。 $N$ は正の整数。 $2 \leq N \leq 500$ 。
$M$ はyukicoder線の特別列車の数。 $M$ は正の整数。 $1 \leq M \leq \frac{N \times (N - 1)}{2}$ 。
$S a_{i}$ 、 $S b_{i}$ は $i$ 番目の特別列車の乗車可能な駅。共に整数。 $0 \leq S a_{i} < S b_{i} \leq N - 1$ 。
すべての $S a_{i}$ 、 $S b_{i}$ の組み合わせは異なる。

出力

計画が達成できるなら"YES"を、達成できないなら"NO"を1行で出力せよ。
最後に改行してください。

サンプル

サンプル1

入力

5 2
0 4
3 4

出力

YES

yukicoder線には5つの駅と2つの特別列車があります。
0番目の特別列車は0駅から4駅を往復します。
1番目の特別列車は3駅から4駅を往復します。

鉄道同好会のメンバーはまず0駅に集合します。
次に0番目の特別列車で4駅まで移動します。
次に1番目の特別列車で3駅まで移動します。
最後に鉄道同好会のメンバーは3駅で解散します。
鉄道同好会のメンバーは計画を達成できます。
3駅で集合して0駅で解散する方法でも達成できますね。

なお、鉄道同好会のメンバーは4駅で集合すべきではありません。
4駅でいずれかの特別列車に片道乗ると満足してしまい引き返せなくなります。
すると、もう一方の特別列車に乗ることができません。

サンプル2

入力

5 2
0 2
3 4

出力

NO

yukicoder線には5つの駅と2つの特別列車があります。
0番目の特別列車は0駅から2駅を往復します。
1番目の特別列車は3駅から4駅を往復します。
鉄道同好会のメンバーはどうやっても特別列車を使って2駅から3駅の間を移動できません。
よって、すべての特別列車に乗ることはできません。
鉄道同好会のメンバーは計画を達成できません。

サンプル3

入力

出力

NO

できないようです。

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