F. Берляндия и кратчайшие пути
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии $$$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$$$-я дорога. Между каждой парой городов не более одной дороги. Заданный набор дорог таков, что в любой город можно добраться из столицы.

Выходные данные

Выведите $$$t$$$ ($$$1 \le t \le k$$$) — количество вариантов выбора набора дорог. Напомним, что вам надо найти $$$k$$$ различных вариантов, если $$$k$$$ вариантов не существует, то найти всевозможные различные варианты.

Далее выведите $$$t$$$ строк. Каждая из строк должна содержать один из вариантов. Вариант следует выводить как последовательность из $$$m$$$ символов, где $$$j$$$-й символ равен '1', если $$$j$$$-я дорога включена в вариант и равен '0', если не включена. Дороги следует нумеровать в соответствии с их порядков во входных данных. Варианты выбора можно выводить в любом порядке. Все строки выведенные $$$t$$$ строк должны быть различны.

Так как гарантируется, что $$$m \cdot k \le 10^6$$$, то суммарный размер всех выведенных $$$t$$$ строк не будет больше $$$10^6$$$.

Если ответов несколько, выведите любой из них.

Примеры
Входные данные
4 4 3
1 2
2 3
1 4
4 3
Выходные данные
2
1110
1011
Входные данные
4 6 3
1 2
2 3
1 4
4 3
2 4
1 3
Выходные данные
1
101001
Входные данные
5 6 2
1 2
1 3
2 4
2 5
3 4
3 5
Выходные данные
2
111100
110110