F. 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. ## Input 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. ## Output 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. [samples]