AT_pakencamp_2024_day3_1_n Increasing Path

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

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

各テストケースについて、改行区切りで答えを出力せよ。

### Constraints - $ 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 $ ) - 与えられるグラフは単純 - 入力は全て整数