문제
정올이의 목장에는 N마리의 소가 살고 있다. 소들도 같은 장소에 오래 살다보면, 위계질서라는게 생기기 마련이다. 이 위계질서는 목장 주인이 우유를 짜는 순서를 결정한다. 정올이의 목장에 있는 소들도 위계질서가 있는데, 이는 구체적으로 다음과 같다.
예를 들어 어떤 위계질서가 {2, 5, 7, 1}이라면 2번 소는 5번 소보다 먼저 착유(우유를 짜냄)되어야 한다. 만약 이 질서가 무너지면, 정올이가 집에 돌아간 후 2번 소가 5번 소를 괴롭힐 수 있기 때문이다. 마찬가지로, 5번 소가 7번 소보단 먼저 착유되어야 하고, 7번 소도 1번 소보다 순서상 먼저여야 한다.
정올이는 이런 위계질서가 M개나 존재한다는걸 발견했다. 이를 앞에서부터 1번 위계질서, 2번 위계질서… 이런 식으로 번호를 매기도록 하자. 모든 위계질서를 다 지켜줄 주는 없기 때문에, 정올이는 1번부터 X번 위계질서 까지만 지켜보려고 한다. 이 때 이 X를 최대화 시키고 싶은게 정올이의 마음이다.
X를 최대화 시켰을 때, 가능한 우유 짜는 순서를 출력하는 프로그램을 작성하라. 가능한 순서가 여러 가지일 경우, 앞에서부터의 소 번호가 작은 경우를 답으로 한다.
입력
첫 줄에 N(1 <= N <= 100,000)과 M(1 <= M <= 50,000)이 공백을 사이에 두고 주어진다.
다음 각 M줄 별로 위계질서가 주어진다.
첫 번째 수는 위계질서의 크기인 i이며, 다음 i개의 위계질서가 공백을 사이에 두고 주어진다.
i는 N이하의 양의 정수이며, 어떤 위계질서 내의 모든 소 번호를 다 합해도 200,000이 넘지 않는다.
출력
X가 최대화 될 경우, 가능한 우유 짜는 순서를 출력한다.
예제
4 3
3 1 2 3
2 4 2
3 3 4 1
1 4 2 3
힌트
출처
USACO 2018 US Open Gold
로그인해야 코드를 작성할 수 있어요.