問題文

NN個の都市とMM個の道があり、道iiAiA_iBiB_iを結んでいます。  

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

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

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

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

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

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

制約

1N161 \leq N \leq 16

1MN×(N1)21 \leq M \leq \frac{N×(N-1)}{2}

1Ai,BiN1 \leq A_i,B_i \leq N

AiBiA_i≠B_i

Ai=AjA_i=A_jの時、BiBjB_i≠B_j

入力

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

NN MM

A1A_1 B1B_1

A2A_2 B2B_2

::

AMA_M BMB_M

出力

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

入力例1

5 4
1 2
2 3
4 5
1 3

出力例1

1

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

入力例2

2 1
1 2

出力例2

0

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

Submit


Go (1.21)