伯兰有 $$$n$$$ 个城市。有些城市之间有道路相连。所有道路都是双向的。每条道路连接两个不同的城市。一对城市之间至多有一条道路。城市编号从 $$$1$$$ 到 $$$n$$$。
众所周知,从首都(编号为$$$1$$$的城市),沿着道路行驶可以到达任何其他城市。
贝尔兰总统计划改善该国的公路网。预算足以修复 $$$n-1$$$ 道路。总统计划选择一组 $$$n-1$$$ 道路,以便:
- 可以沿着$$$n-1$$$选择的道路从首都前往任何其他城市,
- 如果 $$$d_i$$$ 是从首都到城市 $$$i$$$ 所需的道路数量,仅沿着 $$$n-1$$$ 选定的道路移动,则 $$$d_1 + d_2 + \dots + d_n$$$ 被最小化(即尽可能最小)。
换句话说,$$$n-1$$$ 道路组应保留国家/地区的连通性,并且从城市 $$$1$$$ 到所有城市的距离总和应最小化(您只能使用 $$$n-1$$$ 所选道路)。
总统指示该部准备 $$$k$$$ 可能的选项来选择 $$$n-1$$$ 道路,以便满足上述两个条件。
编写一个程序,找到 $$$k$$$ 可能的方法来选择要修复的道路。如果路径少于$$$k$$$,那么程序应该输出所有可能的有效路径来选择道路。
输入
输入的第一行包含整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 2\cdot10^5, n-1 \le m \le 2\cdot10^5, 1 \le k \le 2\cdot10^5$$$),其中 $$$n$$$ 是城市的数量$$$m$$$ 是道路数量,$$$k$$$ 是选择一组道路进行修复的选项数量。保证 $$$m \cdot k \le 10^6$$$。
以下 $$$m$$$ 行描述道路,每行一条道路。每行包含两个整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) — 第 $$$i$$$ 条道路连接的城市编号。一对城市之间至多有一条道路。给定的道路可以让您从首都到达任何城市。
输出
Print $$$t$$$ ($$$1 \le t \le k$$$) — 选择一组道路进行修复的方法数。回想一下,您需要找到 $$$k$$$ 不同的选项;如果它们的数量少于 $$$k$$$,那么您需要找到所有可能的不同有效选项。
在接下来的 $$$t$$$ 行中,打印选项,每行一个。将选项打印为 $$$m$$$ 字符的字符串,其中如果选项中包含第 $$$j$$$ 条道路,则第 $$$j$$$ 个字符等于“1”;如果不包含该道路,则第 $$$j$$$ 个字符等于“0”。道路应根据输入中的顺序进行编号。可以按任何顺序打印选项。所有 $$$t$$$ 行应该不同。
由于保证$$$m \cdot k \le 10^6$$$,所以所有$$$t$$$行的总长度不会超过$$$10^6$$$。
如果有多个答案,则输出其中任何一个。
示例
输入 #1
4 4 3 1 2 2 3 1 4 4 3
输出 #1
2 1110 1011
输入 #2
4 6 3 1 2 2 3 1 4 4 3 2 4 1 3
输出 #2
1 101001
输入 #3
5 6 2 1 2 1 3 2 4 2 5 3 4 3 5
输出 #3
2 111100 110110