Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TOUR2509 - Dã ngoại

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

Được gửi lên bởi:special_one
Ngày:2009-02-12
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2010-02-17 15:05:52 Hy Trường Sơn
ps ơi cho mọi người thêm một test ví dụ kho khó nữa được không, mình thử check mãi mà vẫn chưa biết sai ở đâu
2010-02-17 14:52:50 Hy Trường Sơn
bài này đa đồ thị hay đơn đồ thị ps ơi, đề thiếu rõ ràng quá *_*
2010-02-17 14:19:11 Hy Trường Sơn
ps ơi, nếu đồ thị k có cạnh nào thì in ra k=0 có phải không?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.