정올이의 목장에는 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

1번과 2번 위계질서만 봤을 때, 1 2 3의 순서가 지켜지면서 4 2의 순서가 지켜지는 경우는 두 가지이다: 1 4 2 3과 4 1 2 3. 이때 1 4 2 3이 더 작으므로, 답이 된다. 3번 위계질서까지 지켜지면서 우유를 짜는 순서를 정하는 방법은 없다.