Giải bài trực tuyến

Tết năm nay, gia đình sherry quyết định sẽ có 1 chuyến dã ngoại. Họ ra ngoại ô thành phố nơi có không khí trong lành, những dòng sông xanh biếc và những cánh đồng lúa xanh trải dài vô tận.

Ở ngoại ô có N vùng, 1 số vùng nối nhau bởi những đồng lúa, con sông, hoặc là con đường. Gia đình sherry đi dã ngoại bằng ô tô nên họ chỉ đi trên các con đường. Ở ngoại ô có M con đường, sherry sẽ đi qua tất cả chúng để có thể ngắm cảnh thanh bình nơi thôn quê.

Để hành trình thêm phần thú vị, sherry muốn chia hành trình của mình thành 1 số phần, mỗi hành trình gồm 1 số con đường, và không có bất kì 2 con đường nào trùng nhau ở 2 hành trình phân biệt. Chuyến dã ngoại sẽ thật thú vị nếu sherry có thể chia thành 1 số ít hành trình nhất ^^

Input

Dòng thứ nhất ghi hai số nguyên dương N, M.

Trong M dòng tiếp theo, mỗi dòng ghi 2 số nguyên là 2 đầu mút của mỗi con đường.

Output

Dòng thứ nhất ghi số nguyên dương K là số hành trình.

Trong K dòng tiếp theo, mỗi dòng ghi H là số vùng đi qua trên hành trình. Tiếp theo ghi một hành trình của xe tự hành qua nhóm đường tương ứng từ đỉnh bắt đầu, qua các đỉnh trung gian đến đỉnh kết thúc của hành trình.

Example

Input:
4 2
1 2
4 3

Output:
2
2 1 2
2 3 4

Giới hạn:
1 ≤ N ≤ 10000
1 ≤ M ≤ 20000
Thời gian: 1s/test