A community consists of N (2 ≤ N ≤ 16) people, numbered from 1 to N will choose K people. However, there are M (1 ≤ M ≤ 120) hate relation between a pair of people. Among those K people who are chosen, there must not be any two people that hates each other.

Count the maximum possible value of K, the maximum number of people that can be chosen.

Input

The first line consist of two integers N and M separated by a space.

The next M lines consist of two integers a and b each between 1 and N. These integers are guaranteed to be different. This means person a hates person b and vice versa.

Output

The maximum possible value of K

Example

Input:
5 2
1 2
2 3

Output:
4