← 返回题目列表

Codeforces · 1005/F

F. Berland 和最短路径

中文机器翻译题面 查看原题

伯兰有 $$$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