AT_pakencamp_2024_day3_1_n Increasing Path

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图 $G$，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。将 $1$ 到 $N$ 的整数分别赋给图 $G$ 的各个顶点的方法共有 $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$

对于每组测试数据，请输出一行答案。

- $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$） - 给出的图均为简单图 - 所有输入均为整数。 由 ChatGPT 5 翻译