The mayor of ACMburg decided to reorganize the work of the city
public transport. There are N bus stops in ACMburg, and
some of them are connected by roads. If two bus stop are
connected by a road, then a bus may go without additional stops
from the first stop to the second stop as well as from the second
stop to the first stop. No two stops are connected by more than
one road, and no road connects a stop with itself.
A bus must stop at every stop along its route.
After the reform, there are only circular routes with at least
three different stops, and on each route the stops do not repeat.
Any two routes differ in at least one road. For the convenience
of citizens, there are as many different routes (satisfying the
above conditions) as possible. The routes are numbered from 1 to
K. On each route there is exactly one bus, and the buses
are numbered according to their routes.
According to the mayor's regulation, inspectors must examine
passengers' tickets according to a certain schedule, which
must be arranged by city officials. The schedule must be
in the form of a table with columns corresponding to bus routes
and rows corresponding to time moments at which checks are
If there is a number X in a cell [T, I],
then the bus I stops for a ticket check at the stop
X at the moment T. There may be empty cells in the
table. During a day, each bus must undergo a check at each stop
exactly once, i.e., the number of nonempty cells in each column
equals the number of stops on the corresponding route.
Two buses cannot be checked at the same stop simultaneously.
And, of course , a bus cannot be at two different stops at
the same moment.
It is required to find the minimal number of lines in this table.
The first line contains the numbers of stops and roads in the
city: N and M (3 ≤ N ≤ 14).
In the next M lines there are pairs of stops
connected by roads.
Output the minimal number of lines in the schedule.
Problem Author: Alexander Ipatov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006