D: DAG トリオ / DAG Trio

この問題は G: DAG Trio (Hard) と制約のみが異なる同じ設定の問題です。

プロローグ

弟は最近「だぐとりお」が欲しいとしきりに呟いています。 心配になった兄が調べたところ、弟のクラスでは $k$-DAG (有向グラフであって、ある $k$ 個の辺を削除すると、辺の向きを無視したときの連結成分数を $k$ にでき、かつそれら全てが DAG である) が流行っており、 3-DAG を特に DAG トリオと呼ぶことを突き止めました。 弟に尊敬されたい兄は、与えられたグラフが DAG トリオかどうかを判別するプログラムを作成することにしました。

問題文

$N$ 頂点 $M$ 辺の有向グラフが与えられます。 各頂点には $1$ から $N$ まで番号が振られています。 各有向辺には $1$ から $M$ まで番号が振られています。 有向辺 $i$ は頂点 $a_i$ から $b_i$ に向かいます。 グラフは連結かつ単純です (辺の向きを無視すると、任意の 2 点間に道があり自己ループと多重辺がありません)。 与えられたグラフが DAG トリオならば ”YES”、そうでないなら ”NO” を出力してください。

入力

$N \ M$
$a_1 \ b_1$
$a_2 \ b_2$
$\vdots$
$a_M \ b_M$

制約

$3 \le N \le 500$
$\max(3, N−1) \le M \le 1000$
$1 \le a_i, b_i \le N$
グラフは辺の向きを無視したときに連結である。
各 $i$ に対して$a_i \neq b_i$
異なる $i, j$ に対して $\{a_i, b_i\} \neq \{a_j, b_j\}$

出力

”YES”　または ”NO” を $1$ 行で出力してください。

サンプル

サンプル入力1

3 3
1 2
2 3
3 1

サンプル出力1

YES

サンプル入力2

6 7
1 2
2 3
4 3
4 5
5 6
6 4
3 6

サンプル出力2

YES

サンプル入力3

7 10
4 2
4 7
4 6
2 7
2 5
2 1
5 6
1 3
6 3
4 3

サンプル出力3

NO

サンプル入力4

4 4
1 2
3 2
4 3
2 4

サンプル出力4

YES

サンプル入力5

8 9
5 1
3 8
1 2
4 8
4 7
7 5
6 5
3 2
4 2

サンプル出力5

YES

Note

Commentary

 

---