팬그룹 (Fangroups)

프로그램 명: balkan_fangroups(special judge)

제한시간: 0.2 초

//sj 가 아직....

쌀국에서는 N개의 도시가 있고 M개의 일방통행 도로가 있다. 각 도시마다 정확히 한 개의 야구 구단이 있고, 각 구단에는 두터운 팬층이 있다. 쌀국 메이져 리그 개막식 때, 각 구단의 팬들은 원정을 떠난다. k번 구단의 팬들이 원정을 떠나는 방식은 아래와 같다.

⑴ 만약 자신의 연고지(k번 도시)가 이미 점령당했다면, 팬들은 아무 행동도 하지 않는다. 그렇지 않다면, 팬들은 자신의 연고지를 점령한다.
⑵ k번 구단의 팬들이 a번 도시를 점령했다면, 팬들은 a번 도시에서 갈 수 있는 다른 도시들로 이동한다. 만약 k번 구단의 팬들이 다른 구단이 이미 점령한 지역으로 이동한다면, 그 도로에서 싸움이 일어난다. 그렇지 않으면 k번 구단의 팬들은 새로운 지역을 점령하고 이와 같은 작업을 반복한다.
⑶ 만약 더 이상 나아갈 곳이 없다면, 팬들은 원정을 끝낸다.

N개 구단의 팬들은 자신들끼리 원정을 가는 순서를 정했기 때문에, 한 구단의 팬들이 원정을 하는 동안에는 다른 구단에서는 원정을 하지 않는다.

RBC (Riceland Baseball Commitee)에서는 싸움이 난 거리가 어디인 지 조사를 마쳤다. RBC의 간부를 도와 구단의 팬들이 원정을 간 순서를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 도시의 수와 길의 수를 나타내는 자연수 N, M이 주어진다.
두 번째 줄부터 M개의 줄에는 각 길에 대한 정보가 주어진다.

첫 번째 수와 두 번째 수는 각 길의 시작점과 끝점의 번호이다. 만약 그 길에서 싸움이 일어났다면 세 번째 수가 1이고, 그렇지 않으면 세 번째 수는 0이다. 2 ≤ N ≤ 20,000, 1 ≤ M ≤ 200,000

전체 데이터의 20%는 N이 10 이하이고, 전체 데이터의 50%는 N이 1,000 이하이다.

출력

만약 RBC의 조사 결과가 맞지 않는다면 -1을 출력한다.

그렇지 않으면 첫 번째 줄에 각 구단의 팬들이 원정을 가는 순서를 공백을 사이에 두고 출력한다.

입출력 예

입력

8 9
1 4 1
1 8 1
2 3 0
5 6 0
6 5 0
7 4 1
6 4 0
7 1 1
4 5 0

출력

8 5 2 6 3 1 7 4

예제 설명

⑴ 8번 구단의 팬들이 원정을 가면서 8번 도시만 점령한다.
⑵ 5번 구단의 팬들이 원정을 가면서 4, 5, 6번 도시를 점령한다.
⑶ 2번 구단의 팬들이 원정을 가면서 2, 3번 도시를 점령한다.
⑷ 6번 구단의 팬들은 아예 원정을 가지 못한다.
⑸ 3번 구단의 팬들도 아예 원정을 가지 못한다.
⑹ 1번 구단의 팬들이 원정을 가면서 1번 도시를 점령한다. 1번 구단의 팬들이 4, 8번 도시를 가나, 이미 점령된 지역이므로 싸움이 난다.
⑺ 7번 구단의 팬들이 원정을 가면서 7번 도시를 점령한다. 7번 구단의 팬들이 4, 1번 도시를 가나, 이미 점령된 지역이므로 싸움이 난다.
⑻ 4번 구단의 팬들은 아예 원정을 가지 못한다.

출처 : Balkan Olympiad in Informatics 2012, Day 2 Task 2
http://boi2012.dms.rs/index.php?action=show&data=tasks
번역 : functionx

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]