問題文

頂点に 1 から N の番号が振られた N 頂点 M 辺の単純無向グラフ G が与えられます。i 番目の辺は頂点 A_i と頂点 B_i を結びます。G の各頂点に 1 から N までの整数を 1 つずつ割り振る方法は N! 通りありますが、それらのうち以下の値が最小となるものについて、その値を求めてください。

• G 上のパスであって、パス上の頂点に割り当てられた整数を順に並べたものが単調増加になるもののうち、最大の頂点数

制約

• 1 \leq T \leq 5
• 1 \leq N \leq 20
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
• A_i \neq B_i (1 \leq i \leq M)
• \{ A_i,B_i \} \neq \{ A_j,B_j \} (i \neq j)
• 与えられるグラフは単純
• 入力は全て整数

入力例 1

2
5 7
1 2
1 3
1 5
2 4
3 4
3 5
4 5
20 0

出力例 1

3
1