この問題は 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$ 行で出力してください。
3 3 1 2 2 3 3 1
YES
6 7 1 2 2 3 4 3 4 5 5 6 6 4 3 6
YES
7 10 4 2 4 7 4 6 2 7 2 5 2 1 5 6 1 3 6 3 4 3
NO
4 4 1 2 3 2 4 3 2 4
YES
8 9 5 1 3 8 1 2 4 8 4 7 7 5 6 5 3 2 4 2
YES