시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 225 101 65 38.690%

문제

방향 그래프 G = (V, E)가 주여져 있다.

임의의 노드 u, v ∈ V에 대해서 u에서 v로 E에 포함된 간선만을 이용해 갈 수 있는 경로가 있으면 uv로 표현한다.

만약 어떤 노드 vV가 자신으로부터 도달할 수 있는 모든 노드로부터 돌아오는 경로가 있다면, 즉 다음 조건을 만족한다면 노드 vV를 싱크라고 부른다.

  • 조건: ∀wV, (vw) ⇒ (wv)

또한, 그래프 G의 싱크를 모아놓은 집합을 bottom(G)로 표현한다.

  • bottom(G) = {v ∈ V: ∀wV, (vw) ⇒ (wv)}

주어진 그래프 G=(V, E)의 bottom(G)를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫 줄에는 노드의 수 n (1 ≤ n ≤ 5,000)과 음이 아닌 정수 m이 주어진다. V = {1, 2, ..., n}이고, 간선의 수 |E|=m임을 의미한다.

그 다음부터는 각 간선을 나타내는 m쌍의 수 v1 w1 v2 w2 ... vm wm이 공백으로 구분되어 주어진다. 이는 (vi, wi) ∈ E를 의미한다.

마지막 줄에 0이 주어지고, 이 경우는 처리하지 않고 프로그램을 종료시켜야 한다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다.

예제 입력 1

3 3
1 3 2 3 3 1
2 1
1 2
0

예제 출력 1

1 3
2

예제 입력 2

2 1
2 1
2 0

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

예제 출력 2

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

힌트