In Byteotia, there are $n$ cities connected by bidirectional roads, along which numerous villages are located. King Bajtazar has decided to create a network of bus lines serving the cities and villages. Each line can start and end in any city and pass through any number of cities. Cities on a route may be repeated. However, no line may traverse the same road more than once.
To provide transport for all residents while minimizing investment costs, King Bajtazar has decided that every road must be traversed by exactly one bus line, and that the number of bus lines must be minimal.
Task
Write a program that:
- reads the description of the road network,
- designs a bus line network satisfying the given requirements,
- outputs the result.
Input
The first line contains two integers $n$ and $m$ separated by a single space, $2 \le n \le 10\,000$, $n-1 \le m \le 200\,000$; $n$ is the number of cities, and $m$ is the number of roads. The cities are numbered from $1$ to $n$. The next $m$ lines contain the description of the road network. Each of these lines contains two integers $a$ and $b$ separated by a single space, $1 \le a < b \le n$ — the numbers of the cities connected by a road. Each road is given in the input exactly once. You may assume that any two cities are connected by at most one road (though there may be multiple paths connecting two cities) and that it is possible to travel between any two cities.
Output
The first line should contain the number $c$, equal to the minimum number of bus lines. The next $c$ lines should contain the descriptions of the lines: the $(i+1)$-th line should contain the number $l_i$ equal to the number of cities on the route of the $i$-th line, followed by $l_i$ numbers of these cities, given in the order the line visits them. The numbers in the lines should be separated by single spaces. If a line starts and ends in the same city, its number should appear at the beginning and at the end of the route description.
Examples
Input 1
4 6 1 2 2 4 2 3 1 3 3 4 1 4
Output 1
2 6 2 1 3 2 4 3 2 1 4