0161. Strong Defence

Имя входного файла:	defence.in
Имя выходного файла:	defence.out
Ограничение по времени:	2 s
Ограничение по памяти:	32 megabytes

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.

Input file

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 file

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.

Examples:

defence.in	defence.out
4 4 1 4 1 2 1 3 2 4 3 4	2 2 1 2 2 3 4

Источник: Petrozavodsk Summer 2003. Final Contest, Saturday, August 30
Автор: Andrew Stankevich

Обсудить       Отправить решение



Версия для печати