Informatica Online Judge

  빌드오더 [1315 / 0523]

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


The Champion of this Problem (C++) : gs17018 - ms / 444byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

예전에 아주 인기를 끈 스타크래프트(starcraft)라는 게임이 있다.

이 게임은 전략시뮬레이션 게임으로 같은 조건으로 시작하여 미네랄을 최대한 빨리 모아 자신의 종족을 발전시켜 전력 등을 생산하고 적절한 전략을 써서 상대방과 전쟁을 치르는 게임이다.

이 게임에서 원하는 유닛을 생산하기 위해서는 그 유닛을 생산할 건물을 지어야 하는데, 이 건물은 조건없이 지을 수 있는 것도 있지만 다른 선행 건물(들)이 있어야 지을 수 있는 경우가 있다.

따라서 어떤 특정 건물을 짓기 위해서 어떤 순서로 건물을 지을지를 고민해야 한다. 이러한 건물 짓기 순서를 흔히 빌드오더라고 한다.

이번 문제에서는 각 건물을 건설하는 시간은 무시하고, 어떤 건물을 생산하기 위해서 사전에 어떤 건물들이 필요한지에 대한 정보가 주어진다.

예를 들어 테란의 펙토리(factory)를 만들기 위해서는 배럭(barrack)이 필요하다.

따라서 펙토리를 짓기 위해서는 "배럭 -> 펙토리"의 순으로 건물을 지어야 한다.

다음 그림을 보자.



이 그림에서 5번 건물을 만들기 위해서는 2, 3, 4번 건물이 지어져 있어야 한다.

그리고 2, 3, 4 건물을 만들기 위해서는 1번 건물이 필요하다.

1번 건물은 아무 조건없이 바로 만들 수 있다.

따라서 5번 건물을 짓기 위해서는 다음 6가지 순서가 가능하다.

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

하지만 다음 순서로는 불가능 하다.

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

여기서 가능한 순서들에서 (2, 3, 4)는 순서에 관계없이 만들 수 있고, 1, 5는 순서가 중요하다.

모든 건물들을 짓기위한 빌드 그래프가 주어질 때, n을 만들기 위한 빌드오더를 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 건물의 수 n과 각 건물을 만드는데 필요한 건물의 관계를 나타내는 수 m이 입력된다.

두 번째 줄부터 m줄에 걸쳐서 각 건물의 선후 관계가 표시된다.

만약 a b로 입력되면 b건물을 만들기 위해 a건물이 필요하다는 의미이다.


[입력값의 정의역]
2 <= n <= 5,000
1 <= m <= 100,000

Output

주어진 모든 건물들을 짖기위한 순서를 공백으로 구분하여 출력한다.

순서가 여러가지로 나온다면 아무거나 출력해도 된다.

그리고 출력되는 모든 문자는 공백으로 구분한다.

IO Example

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

출력1
1 2 3 4 5

입력2
3 3
1 2
2 3
3 1

출력2
-1

* 입력1은 예시 그림의 그래프이고, 입력2는 1을 만들기 위해서 3이 필요하므로 아예 건물을 지을 수 없다. 따라서 -1을 출력한다.

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