問題文

$N$個の都市と$M$個の道があり、道$i$は$A_i$と$B_i$を結んでいます。　　

トラック運転手のわたそう君は、ランダムな都市からスタートしてこのすべての都市に物資を届けたいです。　　

ただし、わたそう君は新米のドライバーなため、進行方向から見て一番左の道にしか進めません。　　

また、行き止まりになってしまったらもと来た道を一回戻ります。また、常に進行方向を向いているものとします。　　

また、事前に会社に頼んで道を壊してもらったり、作ってもらったりできます。　　

わたそう君が物資を届けるために道をできるだけかけないようにして確実にすべての場所に荷物を届けたいとき、最小で何個道を壊す必要があるでしょうか。

なお、わたそう君は一番最初はどこへ移動か決まっていないものとし、どの順番で道がつながっているかはわからないものとします。

制約

$1 \leq N \leq 16$

$1 \leq M \leq \frac{N×(N-1)}{2}$

$1 \leq A_i,B_i \leq N$

$A_i≠B_i$

$A_i=A_j$の時、$B_i≠B_j$

入力

入力は以下のように標準入力から与えられる。

出力

標準出力に、壊すべき道の数を一行に出力せよ。

入力例1

5 4
1 2
2 3
4 5
1 3

出力例1

1

3本目と5本目に道を作るとき、1本目を壊すことで全員に配ることができ、これが最小です。

入力例2

2 1
1 2

出力例2

0

そのままでも、運べる場合もあります。