← 返回题目列表

AtCoder · pakencamp_2024_day3_1_n

N. 增加路径

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在顶部 编号为 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)
  • 给定的图很简单
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

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

出力例 1

3
1