GSCOMM - Community
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
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 |