Problem G: The Open Day

Once per year, your University plans the visit of high school students in a single day. Each department at the University proposes a set of events. Someone from the central services will have to schedule these events in a large open space. Events can be scheduled simultaneously as long as no high school student has signed for two of them.

At 14:00, the prime minister plans to visit some of the events that are running at that time. For this reason, the rector of the University would like to schedule as many events as possible for that timeslot.

This looks a hard problem for the central services. So, they decided to call you asking for your help.


The central services told you the number N of events that can be scheduled at 14:00, and which M pairs of events cannot run simultaneously because they have high school students in common. Your task is to write a program that computes the maximum number of events that can run simultaneously without having students in common.


Each test case starts with two positive integers: N and M. Then, M lines follow. Each line contains the index of two events that cannot run simultaneously because they have at least one student in common. The indices of the events are from 0 to N−1.


A single line containing the maximum number of events that can run simultaneously.


1 < N ≤ 30Number of events
1 < M ≤ 435Number of pairs of events that cannot run simultaneously

Input example 1

6 6
0 1
0 2
0 3
0 4
0 5
1 5

Output example 1


Input example 2

8 4
3 1
1 4
0 2
1 0

Output example 2



MIUP'2012, 20 de Outubro, DCC/FCUP

This document was translated from LATEX by HEVEA.