eolymp
bolt
Try our new interface for solving problems
Məsələlər

Party Night

Party Night

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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 guring 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 P_0 and P_1, and after-parties A_0, A_1 and A_2, such that person 0 went to P_0 and A_0, person 1 to P_0 and A_1, person 2 to P_0 and A_2, and person 3 to P_1 and A_2; this arrangement satis es all required conditions. However, if persons 0 and 3 claimed to have met too, the data would become inconsistent.

Giriş verilənləri

The input file will contain several test cases. Each of them begins with a line containing two integers: 1n100, the number of villagers; and 0m1000. m lines follow, each containing a pair of integers i and j, 0i, 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.

Çıxış verilənləri

For each test case, print "YES" if there is a con guration 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.

Nümunə

Giriş verilənləri #1
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 0
Çıxış verilənləri #1
YES
NO
YES