SOJ ONLINE JUDGE

위상 정렬

난이도: Gold III 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB
방향 비순환 그래프그래프 탐색위상 정렬

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과 $M$개의 방향 간선으로 이루어진 그래프가 있다.

간선 $(u,v)$는 $u$번 정점에서 $v$번 정점으로 향한다.

모든 정점을 정확히 한 번씩 나열하되, 모든 간선 $(u,v)$에 대해 $u$번 정점이 $v$번 정점보다 앞에 나오도록 하라.

조건을 만족하는 순서가 여러 개라면 그중 하나를 출력한다.

조건을 만족하는 순서가 존재하지 않는다면 CYCLE을 출력한다.

입력

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(1 \leq N \leq 100\,000, 0 \leq M \leq 200\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 방향 간선을 나타내는 두 정수 $u$, $v$가 주어진다. $(1 \leq u,v \leq N, u \neq v)$

같은 방향 간선은 두 번 이상 주어지지 않는다.

출력

조건을 만족하는 순서가 존재한다면 $N$개의 정점 번호를 순서대로 출력한다.

정점 번호는 공백으로 구분한다.

조건을 만족하는 순서가 존재하지 않는다면 CYCLE을 출력한다.

예제 입력 1

6 6
1 4
1 2
2 4
3 4
3 5
4 6

예제 출력 1

1 3 2 5 4 6 

예제 입력 3

4 4
1 2
2 3
3 2
3 4

예제 출력 3

CYCLE

제출