PRTYNGHT - Party Night

no tags 

Today is the town’s celebration day, on which tradition dictates that all townspeople go partying. Each of them should attend a party at one of the pubs, and dance and drink to the point of intoxication. Later on, once all the parties have come to an end, after-parties start being thrown at other pubs, and every villager then goes to one. In order for the villagers to make as many acquaintances as possible, no two of them attend the same two parties.

Needless to say, such practice causes everyone to have a severe blackout regarding the events of the night, but people are still curious to know what happened. Unfortunately, all they seem to be able to remember is who coincided with them at some point, but they have serious trouble identifying when or where. And as their memory of even this piece of information may be shaky (to say the least), they need help in figuring out whether all their recollections are consistent or if, on the contrary, some of the townspeople must have made a mistake (either by failing to remember someone else who was there, or by incorrectly thinking they met someone they didn’t). Can you help them?

For example, in a town of 4 people, if we are told that villagers 0, 1 and 2 all met one another, and villagers 2 and 3 met as well, the data is consistent because there might have been parties P0 and P1, and after-parties A0, A1 and A2, such that person 0 went to P0 and A0, person 1 to P0 and A1, person 2 to P0 and A2, and person 3 to P1 and A2; this arrangement satisfies all required conditions. However, if persons 0 and 3 claimed to have met too, the data would become inconsistent.

Input

The input file will contain several test cases. Each of them begins with a line containing two integers: 1 ≤ n ≤ 100, the number of villagers; and 0 ≤ m ≤ 1000. m lines follow, each containing a pair of integers i and j, 0 ≤ i, j < n, ij, meaning that persons numbered i and j remember having been together in a pub. No pair of people will appear twice.

Different test cases will be separated by a blank line. A line with n = m = 0 signals the end of the input.

Output

For each test case, print “YES” if there is a configuration of parties, after-parties, and villagers attending them under the conditions described, such that the pairs of people who met each other are exactly those in the input data. Print “NO” otherwise.

Sample

Input
4 4
0 1
0 2
1 2
2 3

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

7 11
0 1
0 2
0 4
1 3
1 5
1 6
2 4
2 5
3 5
3 6
5 6

0

Output
YES
NO
YES

Problem setter: David García Soriano


Added by:David García Soriano
Date:2011-11-24
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CUPCAM 2009