Berland và k cây đường đi ngắn nhất

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh đánh số từ $1$ đến $n$ và $m$ cạnh. Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh, không có cạnh nối một đỉnh với chính nó.

Cần chọn ra đúng $n-1$ cạnh sao cho:

• Tập cạnh được chọn vẫn giữ đồ thị liên thông (tức tạo thành cây khung);
• Gọi $d_i$ là số cạnh trên đường đi từ đỉnh $1$ đến đỉnh $i$ trong cây được chọn, tổng $d_1+d_2+\dots +d_n$ phải nhỏ nhất có thể.

Hãy in ra $min(k,T)$ phương án khác nhau thoả mãn yêu cầu trên, trong đó $T$ là tổng số phương án hợp lệ.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$, $b_i$ mô tả một cạnh nối đỉnh $a_i$ và $b_i$. Các cạnh được đánh số từ $1$ đến $m$ theo thứ tự nhập vào.

Dữ liệu ra

• Dòng đầu in $t=min(k,T)$.
• $t$ dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài $m$. Ký tự thứ $j$ bằng 1 nếu cạnh thứ $j$ được chọn trong phương án đó, ngược lại bằng 0. Mỗi xâu phải có đúng $n-1$ ký tự 1. Các xâu phải đôi một khác nhau. Thứ tự in các phương án tuỳ ý. Nếu có nhiều cách chọn $t$ phương án, in ra bất kỳ cách nào.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $n-1\le m\le 2·{10}^5$
• $1\le k\le 2·{10}^5$
• $m·k\le {10}^6$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$
• Giữa hai đỉnh có nhiều nhất một cạnh. Đồ thị ban đầu liên thông.

Ví dụ