Cyclic Sightseeing

/problems/sightseeing/file/statement/en/img-0001.jpg
Picture by chadmagiera
Emil loves his electric moped. He loves it so much that he rides it through rain, snow, wind and ice. Some day, he will be able to fly with it. This weekend, Emil is on a vacation in New York. He has compiled a list of cool places to visit, as well as a list of all one-way streets between these places, and now it is time for some sightseeing!

One sightseeing trip consists of $S$ places and exactly $S$ streets which connect them. He starts by travelling to one of these places by subway, with his moped on his back. Then he starts riding his moped to each place of the trip in turn, finally returning to where he started in the current trip. Then he goes back to the subway, with his moped on his back, and goes for the next trip. He does this until he has enjoyed all of the trips.

Since it’s very hard to determine if Emil can visit all of the places he wants to see in a single trip of this kind, he has instead asked you to help him split all of the $N$ places in town into a number of trips, such that each place in town is included in exactly one trip.

Given all the places Emil wants to see and the streets of the city connecting these, construct a list of trips fulfilling these conditions, or determine that it is impossible. Each trip must use at least one street, and there may be loops, i.e. streets with a start and end point in the same place.

Input

The first line of input consists of two integers $1\le N \le 100$ and $0 \le M \le 10\, 000$, the number of places Emil wants to visit and the number of roads respectively. The places are numbered $0$ to $N-1$.

The next $M$ lines consists of two integers $0 \le f, t \le N-1$, denoting that there is a one-way street from place $f$ to place $t$.

Output

Output begins with an integer $N$ on its own line, the number of trips made. Then, for every trip, output a line with the number of places included in the trip $K$, followed by $K$ lines, containing the numbers of said places in order of visit (the last place which Emil returns to should not be output twice).

If the places can’t be split into trips, Emil instead goes bowling. Then just output the string "Yeah!". If there are several solutions, output any of them.

Sample Input 1 Sample Output 1
4 4
0 1
1 0
2 3
3 2
2
2
0
1
2
2
3
Sample Input 2 Sample Output 2
4 4
0 1
1 0
2 3
3 3
Yeah!
Sample Input 3 Sample Output 3
1 1
0 0
1
1
0