By XI Maratona de Programação IME-USP, 2007 Brazil
We have already commented about the Mrs. Montagny's parties at the edge of the Lake Louise in Banff. In her parties, she undertakes to solve another problem that shakes dinners organizers around the world: where to seat your guests. The mogul simplifies the problem by asking the guests, on the same questionnaire already mentioned, that note on the list of guests who they wish to have in front of them at the dinner table. The ideia is to have your friends always ahead, so that the conversation can flow better. Her ability is such that she was hired by Fairmont Banff Springs Hotel (hotel in which the ICPC World Finals will take place in 2008: http://en.wikipedia.org/wiki/Banff Springs Hotel) for work on arrangement of banquet tables.
Your task in this problem is to assist the mogul again. Given the wishes of the guests, your program must decide whether it is possible to arrange them on a table so that each guest has all his friends on the opposite side of the table.
The input is composed of several instances. The first line of each instance contains two integers n (1 ≤ n ≤ 100) and m (0 ≤ m ≤ n(n−1)/2), where n is the number of guests and m is the number of friendly relations. Each of the following m lines contains two integers u and v indicates that u is friend of v and v is friends of u, where 1 ≤ u, v ≤ n.
The entry ends with end of file.
For each instance, you must print an instance identifier k, where k is the number of the current instance. On the next line, print yes it is possible or no otherwise.
|Sample Input||Sample Output|