CF1005F.Berland and the Shortest Paths

There are $n$ cities in Berland. Some pairs of cities are connected by roads. All roads are bidirectional. Each road connects two different cities. There is at most one road between a pair of cities. The cities are numbered from $1$ to $n$.

It is known that, from the capital (the city with the number $1$), you can reach any other city by moving along the roads.

The President of Berland plans to improve the country's road network. The budget is enough to repair exactly $n-1$ roads. The President plans to choose a set of $n-1$ roads such that:

• it is possible to travel from the capital to any other city along the $n-1$ chosen roads,
• if $d_i$ is the number of roads needed to travel from the capital to city $i$, moving only along the $n-1$ chosen roads, then $d_1 + d_2 + \dots + d_n$ is minimized (i.e. as minimal as possible).

In other words, the set of $n-1$ roads should preserve the connectivity of the country, and the sum of distances from city $1$ to all cities should be minimized (where you can only use the $n-1$ chosen roads).

The president instructed the ministry to prepare $k$ possible options to choose $n-1$ roads so that both conditions above are met.

Write a program that will find $k$ possible ways to choose roads for repair. If there are fewer than $k$ ways, then the program should output all possible valid ways to choose roads.

伯兰有 $n$ 座城市。某些城市对之间由道路连接。所有道路均为双向的，且每条道路连接两个不同的城市；任意一对城市之间至多存在一条道路。这些城市编号为 $1$ 到 $n$。

已知：从首都（编号为 $1$ 的城市）出发，仅沿道路移动，可到达其余任意一座城市。

伯兰总统计划改善该国的道路网络。预算恰好足够修复 $n-1$ 条道路。总统计划从中选出 $n-1$ 条道路，使得：

• 仅利用这 $n-1$ 条被选中的道路，仍能从首都到达其余任意一座城市；
• 若记 $d_i$ 为仅沿这 $n-1$ 条被选中的道路、从首都到城市 $i$ 所需经过的道路数，则总和 $d_1 + d_2 + \dots + d_n$ 尽可能小（即取最小值）。

换言之，所选的 $n-1$ 条道路必须保持全国连通性，且在仅允许使用这些道路的前提下，首都（城市 $1$）到所有城市的距离之和应最小。

总统已指示相关部门准备 $k$ 种满足上述两个条件的、选择 $n-1$ 条道路进行修复的可行方案。

请编写一个程序，找出 $k$ 种满足条件的道路选择方案。若可行方案总数少于 $k$ 种，则输出全部可行方案。

The first line of the input contains integers $n$, $m$ and $k$ ($2 \le n \le 2\cdot10^5, n-1 \le m \le 2\cdot10^5, 1 \le k \le 2\cdot10^5$), where $n$ is the number of cities in the country, $m$ is the number of roads and $k$ is the number of options to choose a set of roads for repair. It is guaranteed that $m \cdot k \le 10^6$.

The following $m$ lines describe the roads, one road per line. Each line contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$) — the numbers of the cities that the $i$-th road connects. There is at most one road between a pair of cities. The given set of roads is such that you can reach any city from the capital.

输入的第一行包含三个整数 $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$) — the number of ways to choose a set of roads for repair. Recall that you need to find $k$ different options; if there are fewer than $k$ of them, then you need to find all possible different valid options.

In the following $t$ lines, print the options, one per line. Print an option as a string of $m$ characters where the $j$-th character is equal to '1' if the $j$-th road is included in the option, and is equal to '0' if the road is not included. The roads should be numbered according to their order in the input. The options can be printed in any order. All the $t$ lines should be different.

Since it is guaranteed that $m \cdot k \le 10^6$, the total length of all the $t$ lines will not exceed $10^6$.

If there are several answers, output any of them.

输出 $t$（$1 \le t \le k$）—— 即选择待修复道路集合的方案数。注意，你需要找出 $k$ 个互不相同的方案；若合法方案总数少于 $k$，则需输出所有可能的、互不相同的合法方案。

接下来 $t$ 行中，每行输出一个方案。每个方案表示为一个长度为 $m$ 的字符串，其中第 $j$ 个字符为 '1' 表示第 $j$ 条道路被选入该方案，为 '0' 表示未被选入。道路编号按其在输入中的顺序确定。各方案的输出顺序任意，但所输出的 $t$ 行字符串必须互不相同。

由于题目保证 $m \cdot k \le 10^6$，因此所有 $t$ 行字符串的总长度不会超过 $10^6$。

若存在多个合法答案，输出任意一个即可。