{"raw_statement":[{"iden":"statement","content":"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$.\n\nIt is known that, from the capital (the city with the number $1$), you can reach any other city by moving along the roads.\n\nThe 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:\n\n*   it is possible to travel from the capital to any other city along the $n-1$ chosen roads,\n*   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).\n\nIn 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).\n\nThe president instructed the ministry to prepare $k$ possible options to choose $n-1$ roads so that both conditions above are met.\n\nWrite 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."},{"iden":"input","content":"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$.\n\nThe 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."},{"iden":"output","content":"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.\n\nIn 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.\n\nSince it is guaranteed that $m \\cdot k \\le 10^6$, the total length of all the $t$ lines will not exceed $10^6$.\n\nIf there are several answers, output any of them."},{"iden":"examples","content":"Input\n\n4 4 3\n1 2\n2 3\n1 4\n4 3\n\nOutput\n\n2\n1110\n1011\n\nInput\n\n4 6 3\n1 2\n2 3\n1 4\n4 3\n2 4\n1 3\n\nOutput\n\n1\n101001\n\nInput\n\n5 6 2\n1 2\n1 3\n2 4\n2 5\n3 4\n3 5\n\nOutput\n\n2\n111100\n110110"}],"translated_statement":[{"iden":"statement","content":"伯兰有 $n$ 座城市。某些城市对之间由道路连接。所有道路都是双向的。每条道路连接两个不同的城市，任意两个城市之间至多有一条道路。城市编号为 $1$ 到 $n$。\n\n已知从首都（编号为 $1$ 的城市）出发，可以通过道路到达任何其他城市。\n\n伯兰总统计划改善国家的道路网络。预算恰好足够修复 $n -1$ 条道路。总统计划选择一个包含 $n -1$ 条道路的集合，使得：\n\n换句话说，所选的 $n -1$ 条道路应保持国家的连通性，并最小化从城市 $1$ 到所有其他城市的距离之和（仅允许使用这 $n -1$ 条选定的道路）。\n\n总统指示部级部门准备 $k$ 种可能的方案，以选择满足上述两个条件的 $n -1$ 条道路。\n\n编写一个程序，找出 $k$ 种可能的道路修复方案。如果少于 $k$ 种方案，则程序应输出所有可能的有效方案。\n\n输入的第一行包含整数 $n$、$m$ 和 $k$（$2 \\leq n \\leq 2 \\cdot 10^5$，$n -1 \\leq m \\leq 2 \\cdot 10^5$，$1 \\leq k \\leq 2 \\cdot 10^5$），其中 $n$ 是国家的城市数量，$m$ 是道路数量，$k$ 是选择道路修复集合的方案数。保证 $m \\cdot k \\leq 10^6$。\n\n接下来的 $m$ 行描述道路，每行一条。每行包含两个整数 $a_i$、$b_i$（$1 \\leq a_i, b_i \\leq n$，$a_i \\ne b_i$）——表示第 $i$ 条道路连接的两个城市编号。任意两个城市之间至多有一条道路。给定的道路集合保证可以从首都到达任何城市。\n\n输出 $t$（$1 \\leq t \\leq k$）——选择道路修复集合的方案数。注意，你需要找出 $k$ 种不同的方案；如果少于 $k$ 种，则需找出所有可能的不同有效方案。\n\n接下来的 $t$ 行，每行输出一个方案。每个方案用一个长度为 $m$ 的字符串表示，其中第 $j$ 个字符为 '_1_' 表示第 $j$ 条道路被包含在该方案中，为 '_0_' 表示未被包含。道路编号应按照输入顺序。方案的输出顺序任意，所有 $t$ 行必须互不相同。\n\n由于保证 $m \\cdot k \\leq 10^6$，所有 $t$ 行的总长度不超过 $10^6$。\n\n如果有多个答案，输出任意一个即可。\n"},{"iden":"input","content":"输入的第一行包含整数 $n$、$m$ 和 $k$（$2 \\leq n \\leq 2 \\cdot 10^5$，$n -1 \\leq m \\leq 2 \\cdot 10^5$，$1 \\leq k \\leq 2 \\cdot 10^5$），其中 $n$ 是国家的城市数量，$m$ 是道路数量，$k$ 是选择道路修复集合的方案数。保证 $m \\cdot k \\leq 10^6$。接下来的 $m$ 行描述道路，每行一条。每行包含两个整数 $a_i$、$b_i$（$1 \\leq a_i, b_i \\leq n$，$a_i \\ne b_i$）——表示第 $i$ 条道路连接的两个城市编号。任意两个城市之间至多有一条道路。给定的道路集合保证可以从首都到达任何城市。"},{"iden":"output","content":"输出 $t$（$1 \\leq t \\leq k$）——选择道路修复集合的方案数。注意，你需要找出 $k$ 种不同的方案；如果少于 $k$ 种，则需找出所有可能的不同有效方案。接下来的 $t$ 行，每行输出一个方案。每个方案用一个长度为 $m$ 的字符串表示，其中第 $j$ 个字符为 '_1_' 表示第 $j$ 条道路被包含在该方案中，为 '_0_' 表示未被包含。道路编号应按照输入顺序。方案的输出顺序任意，所有 $t$ 行必须互不相同。由于保证 $m \\cdot k \\leq 10^6$，所有 $t$ 行的总长度不超过 $10^6$。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入\n4 4 3\n1 2\n2 3\n1 4\n4 3\n输出\n2\n1110\n1011\n\n输入\n4 6 3\n1 2\n2 3\n1 4\n4 3\n2 4\n1 3\n输出\n1\n101001\n\n输入\n5 6 2\n1 2\n1 3\n2 4\n2 5\n3 4\n3 5\n输出\n2\n111100\n110110"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected, connected graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $: set of cities (vertices),  \n- $ E = \\{e_1, e_2, \\dots, e_m\\} $: set of roads (edges), with $ e_j = (a_j, b_j) $,  \n- Vertex $ 1 $ is the capital.  \n\nLet $ \\mathcal{T} $ be the set of all spanning trees of $ G $ that minimize the total distance from vertex $ 1 $ to all other vertices (i.e., minimize $ \\sum_{v \\in V \\setminus \\{1\\}} \\text{dist}_T(1, v) $).\n\n**Constraints**  \n1. $ 2 \\le n \\le 2 \\cdot 10^5 $  \n2. $ n - 1 \\le m \\le 2 \\cdot 10^5 $  \n3. $ 1 \\le k \\le 2 \\cdot 10^5 $  \n4. $ m \\cdot k \\le 10^6 $  \n5. $ G $ is connected.  \n\n**Objective**  \nFind up to $ k $ distinct spanning trees $ T \\in \\mathcal{T} $, where each $ T $ minimizes:  \n$$\n\\sum_{v=2}^{n} \\text{dist}_T(1, v)\n$$  \nand output each as a binary string of length $ m $: the $ j $-th character is $ 1 $ if $ e_j \\in T $, else $ 0 $.  \n\nIf $ |\\mathcal{T}| < k $, output all elements of $ \\mathcal{T} $.","simple_statement":null,"has_page_source":false}