반대 시위

매년 그렇듯이 비토비체에서는 P = NP 평등 행진이 열린다. 이 행사는 비결정적 튜링 기계가 다항 시간 안에 인식하는 모든 언어 $L$에 대해, 결정적 튜링 기계도 다항 시간 안에 $L$을 인식한다고 믿는 사람들이 모여 자신의 견해를 시민들에게 드러내는 자리다.∗ 지난 행진은 평화롭게 진행되었다. 참가자들은 기껏해야 "3-SAT는 쉽다!"라고 외치거나, 해밀턴 사이클을 찾는 최신 다항 시간 "알고리즘"의 의사 코드를 적은 현수막을 들었고, 행인들의 관심은 거의 끌지 못했다. 올해 주최 측은 비토비체 주민들의 주의를 끌기 위해 더 충격적인 구호를 외치려 한다(P = NP라면 어느 정도 사실이기도 하다). 예를 들어 "우리 돈은 안전하지 않다!"와 "우리 사생활은 위협받고 있다!"가 있다. 비토비체 안보국(ABB) 요원들은 행진의 주장에 자극을 받은 주민들이 은행에서 돈을 대량으로 인출하고, ABB가 주민 감시에 쓰는 소셜 네트워크 계정을 대거 삭제할까 우려한다. 간단히 말해, 비토비체의 상황이 불안정해질 것이라는 의심이 있다. 이런 불안정을 막기 위해 ABB 요원들은 $P \ne NP$를 주장하는 반대 시위를 조직하려 한다. 동시에 행진이 지나가지 못하도록 평화적으로 막을 계획도 세운다. ABB는 행진 경로에 있는 교차로 한 곳에서 갑자기 반대 시위를 시작할 예정이다. 그러나 P = NP 행진의 정확한 경로는 끝까지 비밀로 유지되므로, 기관은 반대 시위 장소를 미리 준비해야 한다. ABB는 행진이 어떤 교차로에서 출발해 0이 아닌 수의 도로를 지나 다시 출발점으로 돌아온다는 제보만 받았다. 첫 번째 과제는 이 정보를 사전에 검증하는 것이다. 즉 비토비체의 도로망에 그런 경로가 존재할 수 있는지 확인한다. 요원들은 제보가 사실이라면 행진 경로가 반드시 지나는 교차로가 있는지도 알고 싶어 한다. 그들은 그런 교차로를 모두 찾아 달라고 요청했다. 그중에서 그들이 반대 시위에 가장 알맞은 장소를 고를 것이다. 그런 교차로가 없다면 ABB는 2안을 실행한다. 비토비체에는 일방통행 도로로 연결된 $n$개의 교차로가 있다. 행진에는 차량도 포함되므로, 행진은 도로의 방향을 따라서만 이동할 수 있다고 가정한다.∗ P 대 NP 문제에 대한 더 자세한 내용은 http://en.wikipedia.org/wiki/P_versus_NP_problem에서 볼 수 있다.

첫 줄에는 두 정수 $n$과 $m$이 주어진다($2 \le n \le 500\,000$, $1 \le m \le 1\,000\,000$). 각각 교차로의 수와 도로의 수다. 교차로는 1부터 $n$까지 번호가 매겨진다. 이어지는 $m$개의 줄은 도로를 설명한다. $i$번째 줄의 두 정수 $a_i$, $b_i$($1 \le a_i, b_i \le n$, $a_i \ne b_i$)는 $i$번째 도로가 교차로 $a_i$에서 교차로 $b_i$로 이어진다는 뜻이다. 같은 순서쌍 $(a_i, b_i)$는 두 번 나오지 않는다.

행진 경로가 ABB의 제보와 맞게 진행될 수 없다면 "NIE"라는 한 줄을 출력한다. 그렇지 않다면 두 줄을 출력한다. 첫 줄에는 행진 경로가 반드시 지나는 교차로의 수 $k$를 쓴다. 둘째 줄에는 그 교차로들의 번호를 오름차순으로 $k$개 쓴다. $k = 0$이면 둘째 줄은 빈 줄로 둔다.