Informatica Online Judge

  집회 #1 [1642 / 066A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 5


The Champion of this Problem (C++) : gs14004 - 0ms / 3548byte
My Best Submission (C++) : N/A

[Potyczki Algorytmiczne 2015 (번역 : 32nd 구재현)]

Background

매년 GSHS국에서는 “P=NP 등식” 이라는 집회가 열린다. 임의의 언어 L에 대해서, L을 다항시간에 인식하는 비결정론적 튜링 머신이 존재한다면, 같은 언어를 다항 시간안에 인식하는 결정론적 튜링 머신이 존재한다고 믿는 재현이와 같은 사람들은, 본인들의 관점을 대중들에게 각인시키기 위해 이러한 집회를 연다.

얼마 전까지만 해도 집회는 평화롭게 진행되었다 - 참가자들은 “3-SAT은 쉽다!” 라는 구호를 외치거나, 해밀턴 사이클을 구하는 다항 시간 알고리즘의 의사 코드가 적힌 현수막을 들고 거리를 행진했다. 집회가 너무 평화로운 나머지, 사람들은 집회에 큰 관심을 두지 않게 되었고, 재현이는 “우리의 비밀번호는 안전하지 않다!” “우리의 사생활은 감시당하고 있다!” 와 같은, 조금 더 선동적인 (그리고 P=NP라면 어느 정도 사실인) 구호를 외치기 시작했다.

GSHS 정부는, 집회에서 외치는 선동적인 구호들 때문에, 국민들이 은행에서 돈을 대거 인출해 가거나, SNS 계정을 지우는 것에 대해서 걱정하고 있다. 이렇게 될 경우 국가 경제와 안보에 치명적인 영향이 있을 것이며, 또한 대통령 창호가 더 이상 린킨 파크의 비공개 SNS를 몰래 염탐할 수 없게 될 것이다. 정부는 이러한 상황을 막아야만 한다.

이를 위해 정부는 “코이충연합” 이라는 어용 단체를 고용했다. 코이충연합은 P≠NP를 주장하는 단체로, 평화적인 방법으로 반대 집회를 여는 한편, 재현이의 단체가 시위를 하는 길목을 막고자 한다. 코이충연합은 반대 집회를 어느 한 곳에서, 예고 없이 열 예정이다.

코이충연합의 수장 현수는, 재현이의 단체에 대한 정보를 캐내기 위해서 노력했지만, 재현이의 단체가 어떠한 경로로 집회를 다니는지를 끝내 알아내지 못했다. 현수가 알아낸 정보는, 재현이가 임의의 교차로에서 집회를 시작하고, 1개 이상의 도로를 거친 후, 해당 교차로로 다시 돌아와 집회를 해산한다는 정보 뿐이다.

현수의 무능함에 화가 난 창호는 현수를 숙청해 버리고, 여러분들에게 몇가지 작업을 맡겼다. 첫번째로, 여러분은 현수가 얻은 정보가 옳은 지를 검증해야 한다. 즉, GSHS에서 재현이가 집회를 할 가능성이 있는 회로가 존재하는지를 판별해야 한다. 만약에 그러한 회로가 존재함이 확인되었을 경우, 창호는 재현이가 어떠한 회로를 생각하고 있던 간에, 재현이를 만날 수 있는 교차로를 모두 찾고 싶어 한다.

살고 싶다면, 원하든 원치 않든 여러분들은 창호를 도울 수 밖에 없다. 빨리 코딩해라!

Input

첫번째 줄에는 교차로의 수 N과 도로의 수 M이 주어진다. (1 <= N <= 500000, 1 <= M <= 1000000) 교차로는 1부터 N까지의 번호가 붙어있다.

이후 M개의 줄에 도로가 (ai, bi)의 형태로 주어진다. (1 <= ai, bi <= N, ai != bi) 이는 ai에서 bi로 향하는 일방 통행 도로가 존재함을 뜻한다.

이미 나왔던 (ai, bi) 쌍이 다시 나오는 경우는 없다.

[Sub-Task Info]
#1 : N <= 2000, M <= 10000
#2 : 추가 제약 조건이 없다.

Output

집회를 할 가능성이 있는 회로가 존재하지 않는다면, “NIE”을 출력한다.

그렇지 않다면, 첫번째 줄에 재현이를 무조건 만날 수 있는 정점의 수 k를 출력한다. 두번째 줄에 k개의 정점을 오름차순으로 출력한다. 만약 k = 0일 경우, 두번째 줄은 비어있어야 한다.

IO Example

입력 1
4 5
1 2
2 3
3 1
3 4
4 2

출력 1
2
2 3

입력 2
3 2
1 2
2 3

출력 2
NIE

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]