맞불 집회

매년 그랬듯이 The $P=\mathit{NP}$ Equality Parade가 Bytebury에서 열린다. 이 행사는 모든 언어 $L$에 대해, 비결정적 튜링 기계가 다항 시간 안에 $L$을 인식한다면, 결정적 튜링 기계도 다항 시간 안에 그 언어를 인식한다는 믿음을 가진 사람들이 자신의 견해를 공개적으로 드러내는 행사다.

지난 행사들은 평화롭게 진행되었다. 참가자들은 기껏해야 "3-SAT is easy!"라고 외치거나, 해밀턴 사이클을 찾는 최신 다항 시간 "알고리즘"의 의사코드를 적은 현수막을 들었다. 그러나 지나가는 사람들의 관심은 거의 끌지 못했다. 올해 주최 측은 Bytebury 주민들의 주목을 받기로 하고, 더 충격적인 구호를 외칠 계획이다. $P=\mathit{NP}$가 참이라면 어느 정도 맞는 말이 되는 구호들이다. 그중에는 "Our money is not safe!"와 "Our privacy is threatened!"도 포함된다.

Bytebury 보안국(BSB)은 이런 구호 때문에 Bytebury 주민 대다수가 은행에서 돈을 찾고, BSB가 주민 감시에 쓰는 소셜 미디어 계정을 지울까 우려한다. 쉽게 말해, Bytebury의 상황이 매우 불안정해질 수 있다.

이런 불안정을 막기 위해 BSB 요원들은 $P\neq \mathit{NP}$라는 믿음을 알리는 맞불 집회를 열 계획이다. 동시에 평화적인 방식으로 행진을 막으려 한다. BSB는 맞불 집회를 갑자기 시작할 예정이며, 장소는 행진 경로에 있는 교차로 중 하나여야 한다. 안타깝게도 $P=\mathit{NP}$ 행진의 정확한 경로는 끝까지 비밀로 유지되므로, 보안국은 맞불 집회 장소를 미리 준비해야 한다. BSB가 아는 것은 행진이 어느 교차로에서 출발해 도로를 최소 하나 이상 지나 다시 출발점으로 돌아온다는 사실뿐이다. 먼저 이 정보가 맞는지 확인해야 한다. 즉, Bytebury의 도로망에 그런 경로가 존재할 수 있는지 검사한다. 또한 정보가 맞다고 가정할 때 행진이 반드시 지나는 교차로가 있는지도 알고 싶어 한다. 요원들은 그런 교차로를 모두 찾아 달라고 요청했다. 그중 하나가 맞불 집회의 가장 좋은 장소로 선택된다. 그런 교차로가 없다면 BSB는 2안으로 넘어간다.

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

BSB가 아는 정보대로 행진 경로를 정할 수 없다면, "NIE"(폴란드어로 "아니오")라는 단어 하나만 한 줄에 출력한다. 그렇지 않으면 두 줄을 출력한다. 첫 줄에는 행진 경로가 반드시 지나는 교차로의 수 $k$를 쓴다. 둘째 줄에는 그 교차로들을 오름차순으로 쓴다. $k=0$이면 둘째 줄은 비워 둔다.