3201 : 우유짜기
- 제한시간
- 2000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 14 회
- 시도횟수
- 93 회
문제
정올이의 목장에는 N마리의 소가 살고 있다. 소들도 같은 장소에 오래 살다보면, 위계질서라는게 생기기 마련이다. 이 위계질서는 목장 주인이 우유를 짜는 순서를 결정한다. 정올이의 목장에 있는 소들도 위계질서가 있는데, 이는 구체적으로 다음과 같다.
예를 들어 어떤 위계질서가 {2, 5, 7, 1}이라면 2번 소는 5번 소보다 먼저 착유(우유를 짜냄)되어야 한다. 만약 이 질서가 무너지면, 정올이가 집에 돌아간 후 2번 소가 5번 소를 괴롭힐 수 있기 때문이다. 마찬가지로, 5번 소가 7번 소보단 먼저 착유되어야 하고, 7번 소도 1번 소보다 순서상 먼저여야 한다.
정올이는 이런 위계질서가 M개나 존재한다는걸 발견했다. 이를 앞에서부터 1번 위계질서, 2번 위계질서… 이런 식으로 번호를 매기도록 하자. 모든 위계질서를 다 지켜줄 주는 없기 때문에, 정올이는 1번부터 X번 위계질서 까지만 지켜보려고 한다. 이 때 이 X를 최대화 시키고 싶은게 정올이의 마음이다.
X를 최대화 시켰을 때, 가능한 우유 짜는 순서를 출력하는 프로그램을 작성하라. 가능한 순서가 여러 가지일 경우, 앞에서부터의 소 번호가 작은 경우를 답으로 한다.
입력형식
출력형식
입력 예4 3 3 1 2 3 2 4 2 3 3 4 1 |
출력 예1 4 2 3 |
Hint!