Strong Defence

Time Limit: 1 Second Memory Limit: 32768 KB
Special Judge

The Chief of the Galactic Empire has recently received some bad news from his spies. The Dark Lord is preparing to attack the Empire. His fleet of spaceships is ready for the first hyperjump.

It is well known that travelling in space is very simple. You just start from some star and make a series of hyperjumps to other stars. You can only jump from one star to another if they are connected with a special hyperjump tunnel, which is bidirectional, thus allowing to make a jump from one star that it connects to another. Of course, the tunnels are designed in such a way that there is the way to get from each star to any other one.

However, there is the way to block the hyperjump to do this one must put a special battleship in the corresponding hypertunnel.

Of course, the Chief would like to block all hyperpaths from the star where the headquaters of the Dark Lord are located to the star where the capital of the Galactic Empire is. The resources of the Empire are almost unbounded, so it is easy to create as many battleships as needed. Unfortunately, there is one problem.

Each hyperjump blocking battleship must have a special crystal on board which allows him to stay in the hyperspace. There is a number of types of such crystals. The problem is that there is the way to destroy all battleships carrying some particular type of crystal.

Although it is known, that for each crystal type there is the way to destroy battleships powered by this crystal, there is hope that not all of those are known to Dark Lord engineers. So the Chief would like to use blocking ships in such a way that the following conditions are satisfied:

for each crystal type, if all ships with other crystal types are destroyed, battle ships with this crystal type block hypertunnels in such a way, that there is no path from Dark Lord's star to Empire Capital star;
the number of different crystal types used in ships is maximal possible;
no two ships block the same hypertunnel.

You may consider that there is the unlimited number of crystal types available and crystals of each type available.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

The first line of the input file contains N - the number of stars in the Galaxy(2 <= N <= 400), M - the number of tunnels, S and T - numbers of stars where Dark Lord headquaters and Empire Capital are located respectively (S != T).

Next M lines contain two integer numbers each the numbers of the stars the corresponding tunnel connects. No tunnel connects a star to itself, no two stars are connected with more than one tunnel.

Output

First output L - the number of crystal types used. After that output L lines, for each crystal type output first K_i - the number of battleships with this crystal used, and then K_i numbers, identifying the hypertunnels blocked by the corresponding battleship. The tunnels are numbered starting from 1, as they are given in the input file.

Sample Input

Sample Output

2
2 1 2
2 3 4

Submit

Source: Andrew Stankevich's Contest #3