ENEM - Enemies

no tags 

Gangs are a big problem for every metropolis. Individuals that are member of some gang usually make enemies. When enemies meet each other they always want to fight, which makes the city a dangerous place to live. These gang members are also known as fighters. The local Police Department received anonymous information about a huge meeting between fighters at the central park, but the police chief, as always, wants to know if it is worth to send some of his men there. He knows that a fighter will fight one of his enemies only if all of them are in front of him. If one of the fighters doesn’t want to fight, then the meeting will be canceled. Moreover, each fighter can fight just one enemy at a time, and during this fight his other enemies wait, because they all want to beat him alone. He also knows that one police officer is enough in order to prevent two fighters from start a fight. Given these conditions and the enemy’s relationships of the fighters that will be at the central park, your job is to tell the chief if the meeting will happen or will be canceled. If it is going to happen, then the chief wants to know the minimum number of policemen he needs to send in order to prevent the fights at any moment of the meeting.

Input

Each test case is described using several lines. The first line contains two integers F (1 ≤ F ≤ 60) and R (1 ≤ R ≤ 1770) representing the number of fighters at the meeting and the number of enemy relationships, respectively. The fighters are identified by different integers from 0 to F - 1. Each of the next R lines contains two integers A and B representing an enemy relationship between the fighters A and B. You can consider that each enemy relationship will appear once in each test case and that if a fighter A is enemy of a fighter B then B is also enemy of A. The last test case is followed by a line containing F = 0 and R = 0.

Output

For each test, output in a line the minimum number of policemen necessary in order to prevent the fights or output ‘The meeting will be canceled’ if the meeting is going to be canceled.

Example

Input:
4 4
0 2
0 3
1 2
1 3
6 7
0 2
0 3
0 4
0 5
1 2
1 3
1 4
3 3
0 1
1 2
2 0
0 0

Output:
2
2
The meeting will be canceled

hide comments
Archit Mittal: 2012-08-29 13:55:24

can somebody plz explain 3rd test case

:D: 2012-02-12 12:14:29

What does it mean that all enemies are in front of a fighter? That you can order them in such a way or does all the enemies numbers are all smaller or all bigger. Maybe something different?

:D: 2012-02-11 13:11:34

Input could use some spaces :)

Dona Margarida: 2012-02-10 17:20:23

What will happen if someone has no enemies?


Added by:Paulo Costa
Date:2012-02-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFS