Trong thành phố, ông cảnh sát trưởng mới muốn giảm bớt số lượng cảnh sát tuần tra an ninh các tuyến phố. Thành phố có ~m~ tuyến phố hai chiều và ~n~ giao lộ đánh số từ ~1~ đến ~n~. Một tuyến phố nối hai giao lộ khác nhau.

Mỗi cảnh sát được giao việc tuần tra trên một cung đường gồm một dãy các giao lộ sao cho:

• Hai giao lộ liên tiếp được nối với nhau bởi một tuyến phố.
• Từ một giao lộ bất kỳ trong cung đường đó, cảnh sát có thể đi qua các giao lộ trong cung đường đó và có thể quay trở lại giao lộ xuất phát.
• Hai cung đường của hai cảnh sát khác nhau ít nhất phải có một tuyến phố khác nhau.
• Mỗi cảnh sát chỉ tuần tra trên một cung đường mà họ được giao.

Yêu cầu: Với quy định trên, hãy tìm số lượng cảnh sát lớn nhất có thể đảm nhiệm và các cung đường tuần tra theo yêu cầu.

Input

Vào từ file văn bản POLICE.INP:

• Dòng đầu gồm hai số nguyên dương ~n~, ~m~ với ~1 < n \leq 2000~, ~1 \leq m \leq 5000~.
• ~m~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~a~, ~b~ với ~1 \leq a, b \leq n~ mô tả tuyến phố nối hai giao lộ ~a~ và ~b~.

Output

Ghi ra file văn bản POLICE.OUT:

• Dòng đầu ghi số nguyên dương ~p~ là số cảnh sát lớn nhất có thể đảm nhiệm việc tuần tra các cung đường trong thành phố.
• ~p~ dòng tiếp theo, mỗi dòng ghi một cung đường gồm một dãy các giao lộ tạo nên cung đường đó.

Example input 1

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

Example output 1

4
1 2 3 1
1 2 3 4 1
2 3 4 2
5 6 7 5