시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 132 68 62 62.000%

문제

Once in a while, Moloco employees partition themselves into two groups, and engage in a best-of-five series of the League of Overwatch. Since some pairs of employees are hardcore gamers and they have played together as a duo in the past, the company decided to split them for this friendly company-wide event to make the event less competitive but more enjoyable for newbies.

Formally, there are n employees at Moloco who are numbered as 1 through n

There are m known pairs of employees (fi, si) such that the employees fi and si have played a duo game in the past -- they must belong to different groups for this event.

Given this information, determine whether it is possible to partition n employees to two non-empty groups such that each employee belongs to exactly one group and there is no pair (fi, si) such that both fi and and si belong to the same group.

입력

First line contains two integers, n and m where 1 ≤ n ≤ 1,000,000 and 1 ≤ m ≤ 1,000,000.

The following m lines contain two integers where i+1th line describes fi and si where 1 ≤ fi, sin. It is guaranteed that fisi for all i.

출력

Your output should be a single line that contains a string "POSSIBLE" or "IMPOSSIBLE" (quotes for clarity only). 

예제 입력 1

3 4
1 2
2 3
3 1
2 1

예제 출력 1

IMPOSSIBLE

예제 입력 2

3 3
1 2
1 2
2 3

예제 출력 2

POSSIBLE

힌트

Example 2: ({2} and {1,3} is a valid partition.)

출처

Contest > Startlink Online Contest > Startlink Online Contest #1 B2번