GSCOMM - Community

A community consists of N (2 ≤ N ≤ 16) people, numbered from 1 to N will choose K peopleHowever, there are M (1 ≤ M ≤ 120) hate relation between a pair of people. Among those 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 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

Added by:jonathanirvings
Date:2015-12-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Classical

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.