题目描述

臭臭龙国有 $n$ 个城市，以及 $m$ 条连接城市的双向道路，每条道路连接两个不同的城市 $u,v$。通过这 $m$ 条道路，每个城市均可以到达另外任何一个城市。由于臭臭龙国的交通系统无法处理过于复杂的道路网络，所以对于每条道路，都至多存在一个道路形成的环路包含这条道路。即，道路形成的图是一个边仙人掌。

定义两个城市的距离为从一个城市移动到另一个城市所需要经过的最小道路数量。

臭臭龙国最新研发出的信号塔的覆盖半径为 $k$。信号塔只能部署在一个城市中。若一个信号塔部署在城市 $u$，那么所有与 $u$ 的距离不超过 $k$ 的城市均可以被这个信号塔覆盖。臭臭龙王的目标自然是用若干信号塔使得所有的城市都至少被一个信号塔覆盖，并且为了最小化成本，臭臭龙王希望使用的信号塔数量最少。

请你求出最少需要的信号塔数量，以及一种合法的信号塔部署方案。请注意，不完整地回答所有问题也有可能获得部分分数，具体请看“评分方式”部分。

输入格式

本题包含多组数据。 输入文件的第一行包含一个正整数 $T$ 表示数据组数。接下来对于每组数据：

第一行包含三个整数 $n,m,k$。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条连接城市 $u$ 和城市 $v$ 的道路。

输出格式

你可以在如下两种输出格式中选择一种输出：

• 对于每组数据，输出一行包含一个整数，表示最少需要的信号塔数量。选择这种输出格式无法获得测试点满分，但是可能获得部分分数。
• 对于每组数据，输出两行。第一行包含一个整数，表示最少需要的信号塔数量。第二行包含一个长度为 $n$ 的字符串，第 $i$ 个字符表示城市 $i$ 中是否部署了信号塔，若字符为 1 表示部署了信号塔，若字符为 0 表示没有部署信号塔。你输出的字符串中不应该包含 0 和 1 以外的其他字符。

样例 1 输入

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

样例 1 输出

2
10100
2
10100
1
01000000

附加样例

见选手目录下的对应文件。

评分方式

单个测试点按照如下方式评分：

• 若信号塔数量正确，并且信号塔部署方案符合题目要求，那么该测试点得满分。
• 若信号塔数量正确，但是信号塔部署方案不符合题目要求，或者信号塔部署方案使用的信号塔与输出的信号塔数量不符，或者没有给出信号塔部署方案即选择了第一种输出格式，那么该测试点得到 $\lfloor0.7s\rfloor$ 分，其中 $s$ 表示该测试点的满分。
• 若信号塔数量错误，那么该测试点不得分。

数据范围

对于所有测试数据保证：

• $1\le T\le10^5$；
• $2\le n\le4\times10^6$；
• $n-1\le m\le4\times10^6$；
• $\sum n,\sum m\le4\times10^6$；
• $1\le k\le n$；
• $1\le u,v\le n$，$u\ne v$，同一组数据中无序数对 $(u,v)$ 互不相同（即输入的图没有重边或自环）；
• 输入的图满足每条边至多出现在一个环中。

本题采用捆绑测试。 单个子任务中选手的得分等于该子任务中所有测试点得分的最小值。

特殊性质 A：保证 $T,n,m\le10$。

特殊性质 B：保证 $m=n-1$，$v=u+1$。

特殊性质 C：保证 $m=n-1$。

特殊性质 D：保证 $m=n$。

特殊性质 E：保证 $k\le3$。

提示

本题输入输出量较大，请注意使用较快的输入输出方式。

在下发文件中提供了示例校验器 checker.cpp，你可以使用如下命令编译校验器：

g++ checker.cpp -o checker -std=c++14 -O2

并使用如下命令来检验你的输出：

./checker tower.in tower.out tower.ans

示例校验器会按照题目的评分方式说明自动识别两种输出格式，并给出不得分判决、满分判决或者部分得分判决。答案文件应该总是按照第一种输出格式存储。下发文件中的样例答案文件只包含第一种输出格式的答案。

@下发文件