#P18144. Lalo's Lawyer Lost
Lalo's Lawyer Lost
Lalo's Lawyer Lost
Jesus, it's always the desert.
——James McGill, Better Call Saul
在帮 Lalo 交保释金时,Saul 和 Mike 在沙漠里迷路了。在沙漠中,他们发现了一株仙人掌:一个 个点的连通无向图,满足每条边至多出现在一个简单环中。
已知 是偶数。出于某种原因,Mike 和 Saul 想要解决下面这个问题:
定义 为仙人掌中节点 与 之间的最短距离。把全部 个节点划分成 个点对 ,使每个节点恰好出现在一个点对中,并最大化
请求出这个最大值。
输入格式
第一行一个整数 (),表示测试组数。
每组测试:
- 第一行两个整数 (,, 为偶数);
- 接下来 行,每行两个整数 (,),表示一条边。
保证这些边构成一株仙人掌。所有测试的 之和不超过 , 之和不超过 。
输出格式
对每组测试输出一个整数,表示最大的距离和。
样例
输入:
3
4 3
1 2
2 3
3 4
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 8
8 3
输出:
4
7
11