019 - 橋の一筆書き

問題

ベル君は橋と川と一筆書きがすき。

橋と川が沢山ある街の写真を見つけては一筆書きができるか試す趣味がある。

ベル君の見つけた街の写真の中には橋や川が多すぎて一筆書きできるのか見当が付かないようなものも含まれている。

答えがでない一筆書きを永遠と試し続けるベル君に救いの手を差し伸べたい。

一筆書きできるかどうかだけは教えてあげようと思う。

以下に示すのがベル君の考える一筆書きのルールである。

  1. 一度通った橋は渡らない
  2. 全ての橋を渡る
  3. 街同士を繋げる橋が複数ある場合、それぞれの橋は区別する
  4. 孤立する街は存在しない
  5. 橋はどちらの街から渡っても構わない

街の数(2≦n≦10⁵)、橋の数(n-1≦m≦10⁸),どの街同士をつなぐ橋なのか(1≦p_i,q_i≦n)が入力される。

一筆書きができるときは"OK"、できない場合は"NA"を出力する。

入力

n m
p0 q0
p1 q1
...
pm-1 qm-1

出力

一筆書きができればOK
できなければNAを出力せよ。
出力の最後に改行を入れること

制約

全ての入出力ケースについて以下を満たす

• 2≦n≦10⁵
• n-1≦m≦10⁸
• 1≦p_i,q_i≦n

入出力例

入力例1

4 7
1 2
1 3
1 4
2 4
3 4
3 4
2 1

出力例1

OK

解説

3つ目の街をスタートとして、

3→1→4→3→4→2→1→2

の順であれば一筆書きで全ての橋を渡ることが可能である。

入力例2

4 7
1 2
1 3
1 4
2 4
3 1
3 4
2 1

出力例2

NA

解説

一筆書きで全ての橋を渡ることはできない。

参考

ケーニヒスベルクの橋