Cho một đồ thị vô hướng đơn liên thông gồm $N$ đỉnh và $M$ cạnh.

Các đỉnh của đồ thị được đánh số bằng các số nguyên liên tiếp từ $1$ đến $N$, và các cạnh được đánh số bằng các số nguyên liên tiếp từ $1$ đến $M$. Cạnh $i$ nối đỉnh $u_i$ và đỉnh $v_i$.

Đồ thị này có một tính chất đặc biệt sau: với mọi cạnh $i$ ($1 \le i \le M$), tồn tại một đường đi nối $u_i$ và $v_i$ mà không chứa cạnh này. Chúng ta gọi đường đi như vậy là một đường vòng (bypass path) của cạnh $i$. Có thể có nhiều hơn một đường vòng cho cùng một cạnh.

Chúng ta sẽ tô màu các cạnh bằng các màu được đánh số bằng các số nguyên liên tiếp từ $1$ đến $M$, gán chính xác một màu cho mỗi cạnh. Một số màu có thể không được sử dụng, các màu khác có thể được sử dụng nhiều lần.

Cách tô màu các cạnh được gọi là thú vị (interesting) nếu các tính chất sau thỏa mãn:

• Nếu hai cạnh có chung một đỉnh, màu của chúng phải khác nhau.
• Với mỗi cạnh, tồn tại một đường vòng đặc biệt: một đường vòng chứa các cạnh được tô bằng không quá 8 màu khác nhau.

Nhiệm vụ của bạn là tìm một cách tô màu thú vị và, với mỗi cạnh trong số $M$ cạnh, in ra bất kỳ tập hợp màu nào có thể được sử dụng để tạo thành một đường vòng đặc biệt cho cạnh đó.

Có thể chứng minh rằng, với các ràng buộc trên, luôn tồn tại ít nhất một cách tô màu thú vị.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $N$ và $M$ ($3 \le N \le 5555$, $3 \le M \le \min(N(N - 1)/2, 9999)$).

$M$ dòng tiếp theo, dòng thứ $i$ mô tả cạnh thứ $i$ và chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i < v_i \le N$).

Bạn có thể giả định rằng mỗi cặp $(u, v)$ xuất hiện trong danh sách tối đa một lần, đồ thị đã cho là liên thông và sau khi loại bỏ bất kỳ cạnh $(u, v)$ nào, vẫn tồn tại một đường vòng nối $u$ và $v$.

Dữ liệu ra

In ra bất kỳ cách tô màu thú vị nào theo định dạng sau.

Trên dòng đầu tiên, in ra $M$ số nguyên. Số nguyên thứ $i$ trong số này, $C_i$, phải là màu của cạnh thứ $i$ ($1 \le C_i \le M$).

Sau đó in ra $M$ dòng. Dòng thứ $i$ mô tả tập hợp màu của đường vòng đặc biệt cho cạnh $i$. Dòng này phải bắt đầu bằng số nguyên $k_i$ ($1 \le k_i \le 8$): số lượng màu trong danh sách. Theo sau đó là $k_i$ số nguyên phân biệt đôi một nằm trong khoảng từ $1$ đến $M$: danh sách các màu. Các màu có thể được in theo bất kỳ thứ tự nào. Phải tồn tại một đường vòng đặc biệt giữa $u_i$ và $v_i$ mà không sử dụng bất kỳ màu nào ngoài các màu trong danh sách. Lưu ý rằng điều này có nghĩa là danh sách các màu không nhất thiết phải là tối thiểu, và thậm chí có thể có một đường đi chỉ sử dụng một phần của danh sách: chương trình kiểm tra chỉ đảm bảo rằng các màu được liệt kê là đủ.

Ví dụ

Dữ liệu vào 1

10 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
1 4

Dữ liệu ra 1

1 2 3 4 5 6 7 8 9 10 5
3 2 3 5
3 1 3 5
3 1 2 5
6 5 6 7 8 9 10
7 4 5 6 7 8 9 10
6 4 5 7 8 9 10
6 4 5 6 8 9 10
6 4 5 6 7 9 10
6 4 5 6 7 8 10
8 4 5 6 7 8 9 1 2
3 1 2 3

Ghi chú

Trong ví dụ, có hai đường vòng cho cạnh đầu tiên. Đường vòng dài hơn chứa 9 màu (từ 2 đến 10), vì vậy nó không phải là đường vòng đặc biệt. Đường vòng ngắn hơn bao gồm các cạnh 2, 3 và 11 (các màu 2, 3 và 5), vì vậy nó là đường vòng đặc biệt.