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 performed. 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.