#P17922. Lighthouse

Lighthouse

Lighthouse

题目描述

给定一个有 nn 个顶点、mm 条边的无向简单连通图。图中每条边至多属于一个简单环,即图是一棵边仙人掌。两个简单环不同,当且仅当它们的边集不同。

可以在一些顶点上放置灯塔。两个顶点的距离定义为它们之间最短路径的边数。一座灯塔可以照亮与其所在顶点距离不超过 kk 的所有顶点,包括它所在的顶点。

求照亮所有顶点至少需要放置多少座灯塔。

输入格式

第一行一个整数 TT,表示测试数据组数。每组数据:

第一行三个整数 n,m,kn,m,k。

接下来 mm 行,每行两个整数 u,vu,v,表示一条无向边。

输出格式

每组数据输出一行一个整数,表示灯塔数的最小值。

数据范围

  • 1≤T≤1051\le T\le10^5。
  • 2≤n≤2×1052\le n\le2\times10^5,n−1≤m≤2×105n-1\le m\le2\times10^5,1≤k≤n1\le k\le n。
  • 1≤u,v≤n1\le u,v\le n,u≠vu\ne v。
  • 图连通,没有重边、自环,每条边至多属于一个简单环。
  • 所有测试数据的 n+mn+m 之和不超过 2×1052\times10^5。

样例

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

第三组在顶点 22 放置一座灯塔即可照亮整个图。