В Берляндии \(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\) вариантов не существует, то программа должна вывести всевозможные подходящие варианты.
Выходные данные
Выведите \(t\) (\(1 \le t \le k\)) — количество вариантов выбора набора дорог. Напомним, что вам надо найти \(k\) различных вариантов, если \(k\) вариантов не существует, то найти всевозможные различные варианты.
Далее выведите \(t\) строк. Каждая из строк должна содержать один из вариантов. Вариант следует выводить как последовательность из \(m\) символов, где \(j\)-й символ равен '1', если \(j\)-я дорога включена в вариант и равен '0', если не включена. Дороги следует нумеровать в соответствии с их порядков во входных данных. Варианты выбора можно выводить в любом порядке. Все строки выведенные \(t\) строк должны быть различны.
Так как гарантируется, что \(m \cdot k \le 10^6\), то суммарный размер всех выведенных \(t\) строк не будет больше \(10^6\).
Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 3
1 2
2 3
1 4
4 3
|
2
1110
1011
|
|
2
|
4 6 3
1 2
2 3
1 4
4 3
2 4
1 3
|
1
101001
|
|
3
|
5 6 2
1 2
1 3
2 4
2 5
3 4
3 5
|
2
111100
110110
|