Information

A secret intelligence agency (so secret that its name cannot be given here) controls agents all over the world. From time to time the headquarters must send a message to every agent, and the transmission has to be as secure as possible.

The agency distrusts electronic communication, so messages are carried by contact persons ("contacts"). Agents and contacts form a large network: each contact carries information from exactly one agent to exactly one other agent, and only in that single direction. There may be several contacts that carry information between the same pair of agents.

When the headquarters send a message, their message officer uses some of his own contacts to pass it to a few field agents. Those agents use their contacts to forward it to more agents, and so on, until every agent has received it. To keep the risk low a message should be carried as few times as possible: no agent should receive the same message twice. Each agent therefore forwards a message according to a transmission scheme rather than using all of his contacts. A transmission scheme is a set of contacts such that, starting from the message officer, the message reaches every agent exactly once.

The agency recently discovered that some contacts abused confidential information. For this reason each message is split into two parts that are useless unless read together. The two parts are sent out so that no contact is ever used for both parts; this way no single contact sees the whole message. Every agent must still eventually receive both parts.

Given the network of agents and contacts, decide whether the agency can build two transmission schemes, one for each part, that together satisfy all conditions: each scheme delivers its part from the message officer to every agent exactly once, and the two schemes share no contact.

The first line contains two integers N (2 ≤ N ≤ 2000), the number of agents, and M (1 ≤ M ≤ 1000000), the number of contacts. The message officer at the headquarters is agent 1; the other agents are numbered from 2 to N. Contacts are numbered from 1 to M. Each of the next M lines contains two integers vᵢ and wᵢ (vᵢ ≠ wᵢ), meaning that contact i can carry a message from agent vᵢ to agent wᵢ.

Print POSSIBLE if two transmission schemes with no shared contact exist (one for each part of the message); otherwise print NONE.

In the sample the answer is POSSIBLE. For example, the first part can travel through contacts 1, 3 and 5 (headquarters → agent 2, agent 2 → agent 3, agent 2 → agent 4), and the second part through contacts 2, 4 and 6 (headquarters → agent 3, agent 3 → agent 2, agent 2 → agent 4). The two sets of contacts are disjoint and each delivers the message to every agent exactly once, so two valid schemes exist.