Berland 有 n 座城市。一些城市通过道路连接。所有道路都是双向的。每条道路连接两个不同的城市。一对城市之间至多有一条道路。城市从 1 到 n 编号。

众所周知，从首都（编号为 1 的城市），您可以沿着道路移动并到达任何其他城市。

Berland 的总统计划改善该国的道路网。预算足以修复 n-1 道路。总统计划选择 n-1 条道路，要求：

• 从首都出发沿着这 n-1 条道路走可以到达其他所有的城市。
• 如果 d_i 表示首都到 i 号城市所需经过的路的条数，沿着选择的 n-1 条路走所得的 d_1+d_2+・・・+d_n 应是最小的。

换句话说，这 n-1 条道路的应该保持国家的连通性，并且使从城市 1 到所有城市的距离的总和最小（你只能使用被选择的 n-1 道路）。

总统命令有关部门准备 k 个可能的选择，选择的 n-1 条道路同时满足以上两个条件。

编写一个程序，找到 k 种可能的方法来选择道路进行维修。如果少于 k 种选法，则程序应输出所有可能的有效方式来选择道路。

输入的第一行包含整数 n,m,k. (2 \leq n \le 2 \cdot 10^5, n-1 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5 ), n 是这个国家的城市数，m 是道路数，并且 k 是选 n-1 条道路修复的方案数。 数据保证 m \cdot k \leq 10^6.

接下来的 m 行描述路的情况，每条路的描述占一行。每行包括两个整数 a_i,b_i (1 \leq a_i,b_i\leq n,a_i \neq b_i)—— 第 i 条道路连接的两座城市的编号。一对城市最多有一条路连接。给定的路足以使你从首都出发到达任意城市。

输出 t (1 \leq t \leq k)— 可选择的方案数量。记得你需要找到 k 种不同的可行解，如果解的个数少于 k 种，你需要输出所有可行解。

在接下来的 t 行中，输出道路选择情况，一种一行。用 m 个字符的字符串输出选择情况，其中，第 j 个字符表示第 j 条道路是否被选中，若是则用 1 表示，若不是则用 0 表示。路应该按照它们输入的顺序编号。各种选择情况的输出没有指定顺序。t 行的所有输出应该不同。

因为题目保证 m \cdot k\leq 10^6,t 行输出的总长不超过 10^6.

如果有很多组答案，任意输出它们中的一些即可。