정보 전달

이름조차 여기서 밝힐 수 없을 만큼 비밀스러운 어느 정보기관이 전 세계의 요원들을 관리한다. 본부는 때때로 모든 요원에게 메시지를 보내야 하며, 그 전달은 가능한 한 안전해야 한다.

이 기관은 전자 통신을 신뢰하지 않기 때문에 메시지를 연락원(이하 연락원)을 통해 전달한다. 요원과 연락원은 하나의 커다란 네트워크를 이룬다. 각 연락원은 정확히 한 요원에게서 다른 한 요원에게로, 오직 그 한 방향으로만 정보를 전달할 수 있다. 같은 두 요원 사이를 잇는 연락원이 여러 명일 수도 있다.

본부가 메시지를 보낼 때, 메시지 담당관은 자신의 연락원 중 일부를 사용해 몇몇 현장 요원에게 메시지를 전달한다. 그 요원들은 다시 자신의 연락원을 사용해 다른 요원들에게 전달하고, 이런 식으로 모든 요원이 메시지를 받을 때까지 이어진다. 위험을 줄이기 위해 메시지가 전달되는 횟수는 가능한 한 적어야 하며, 어떤 요원도 같은 메시지를 두 번 받아서는 안 된다. 따라서 각 요원은 모든 연락원을 쓰는 대신 하나의 전달 방식(전달 스킴)을 따른다. 전달 스킴이란 메시지 담당관에서 출발한 메시지가 모든 요원에게 정확히 한 번씩 도달하도록 하는 연락원들의 집합이다.

최근 이 기관은 일부 연락원이 기밀 정보를 악용했다는 사실을 알게 되었다. 그래서 각 메시지를, 함께 읽지 않으면 아무 의미가 없는 두 조각으로 나누어 보내기로 했다. 두 조각은 어떤 연락원도 두 조각 모두에 사용되지 않도록 전달된다. 이렇게 하면 어떤 연락원도 메시지 전체를 볼 수 없다. 그럼에도 모든 요원은 결국 두 조각을 모두 받아야 한다.

요원과 연락원의 네트워크가 주어질 때, 다음 조건을 모두 만족하는 두 개의 전달 스킴(각 조각마다 하나씩)을 만들 수 있는지 판단하라. 각 스킴은 메시지 담당관에서 모든 요원에게 자신의 조각을 정확히 한 번씩 전달하며, 두 스킴은 어떤 연락원도 공유하지 않는다.

첫째 줄에 요원의 수 N (2 ≤ N ≤ 2000)과 연락원의 수 M (1 ≤ M ≤ 1000000)이 공백으로 구분되어 주어진다. 본부의 메시지 담당관은 1번 요원이고, 나머지 요원은 2번부터 N번까지 번호가 매겨진다. 연락원은 1번부터 M번까지 번호가 매겨진다. 다음 M개의 줄 중 i번째 줄에는 두 정수 vᵢ와 wᵢ (vᵢ ≠ wᵢ)가 주어지며, 이는 i번 연락원이 vᵢ번 요원에게서 wᵢ번 요원에게로 메시지를 전달할 수 있음을 뜻한다.

어떤 연락원도 공유하지 않는 두 개의 전달 스킴(메시지의 각 조각마다 하나씩)이 존재하면 POSSIBLE을, 그렇지 않으면 NONE을 출력한다.

예시에서의 답은 POSSIBLE이다. 예를 들어 첫 번째 조각은 연락원 1, 3, 5를 통해 (본부 → 2번 요원, 2번 → 3번, 2번 → 4번), 두 번째 조각은 연락원 2, 4, 6을 통해 (본부 → 3번 요원, 3번 → 2번, 2번 → 4번) 전달될 수 있다. 두 연락원 집합은 서로 겹치지 않으며 각각 모든 요원에게 정확히 한 번씩 메시지를 전달하므로, 유효한 두 스킴이 존재한다.