15511번 - League of Overwatch at Moloco (Hard) 다국어

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 (f_i, s_i) such that the employees f_i and s_i 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 (f_i, s_i) such that both f_i and and s_i 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 f_i and s_i where 1 ≤ f_i, s_i ≤ n. It is guaranteed that f_i ≠ s_i for all i.

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

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