#P17922. Lighthouse
Lighthouse
Lighthouse
题目描述
给定一个有 个顶点、 条边的无向简单连通图。图中每条边至多属于一个简单环,即图是一棵边仙人掌。两个简单环不同,当且仅当它们的边集不同。
可以在一些顶点上放置灯塔。两个顶点的距离定义为它们之间最短路径的边数。一座灯塔可以照亮与其所在顶点距离不超过 的所有顶点,包括它所在的顶点。
求照亮所有顶点至少需要放置多少座灯塔。
输入格式
第一行一个整数 ,表示测试数据组数。每组数据:
第一行三个整数 。
接下来 行,每行两个整数 ,表示一条无向边。
输出格式
每组数据输出一行一个整数,表示灯塔数的最小值。
数据范围
- 。
- ,,。
- ,。
- 图连通,没有重边、自环,每条边至多属于一个简单环。
- 所有测试数据的 之和不超过 。
样例
3
5 4 1
1 2
1 3
3 4
1 5
5 5 1
1 2
2 3
3 4
4 5
5 1
8 8 2
1 2
2 3
3 4
4 5
5 1
1 6
2 7
3 8
2
2
1
第三组在顶点 放置一座灯塔即可照亮整个图。