만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

부대 창설 행사

면접 대비

시간 제한1초메모리 제한1024 MB

요약
각 병사가 순서상 가장 앞에 있는 선호 부대에 배치될 때 모든 부대가 최소 인원을 채우는 부대 순서를 구합니다. 불가능하면 -1을 출력합니다.
난이도

보통10점 중 6점

유형
그리디, 큐, 배열
정답자
아직 제출이 없습니다

문제

부대 창설행사의 인원 모집이 조금 전 마무리되었다!

부대 창설행사는 11번부터 NN번까지 총 NN개의 무대로 구성되며, PP명의 병사가 참여한다. 병사들은 각자 하나 이상의 희망 무대를 선정한 상태이다.

성공적인 행사를 위해서는 무대마다 정해진 최소 인원수를 채워야 한다. 다만 병사를 세심하게 나눠 배치할 여유가 없으므로, 먼저 무대 순서를 정한 뒤 각 무대를 희망했던 병사들을 그 무대에 세운다. 모든 병사는 본인이 희망한 무대 중 순서가 가장 앞선 무대에만 참여한다.

행사가 성공할 수 있는 순서를 찾고, 그중 하나를 출력하라.

입력

첫 번째 줄에 무대의 수 NN과 병사의 수 PP가 공백으로 구분되어 주어진다.

두 번째 줄에 11번 무대부터 NN번 무대까지 각 무대의 최소 인원수 mim_i가 공백으로 구분되어 주어진다.

이후 PP줄에 걸쳐 각 병사가 희망하는 무대의 수 xix_i와, 오름차순으로 정렬된 xix_i개의 희망 무대 번호가 공백으로 구분되어 주어진다.

출력

모든 무대의 최소 인원수를 충족시킬 수 있는 순서가 있다면, NN줄에 걸쳐 그 순서 중 하나를 출력한다. 그런 순서가 없다면 -1을 출력한다.

제한

  • 1≤N≤50 0001 \le N \le 50\,000
  • 1≤P≤100 0001 \le P \le 100\,000
  • 1≤mi≤P1 \le m_i \le P
  • 1≤xi≤N1 \le x_i \le N; 모든 xix_i의 합은 500 000500\,000을 넘지 않는다.

예제3

  1. 예제 1

    입력
    3 5
1 1 1
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
    예상 출력
    -1

  2. 예제 2

    입력
    3 5
1 2 1
2 1 3
1 2
1 1
2 1 2
2 2 3
    예상 출력
    2
3
1

  3. 예제 3

    입력
    4 15
2 3 3 3
2 1 4
1 3
1 3
1 1
2 2 4
2 1 2
1 2
2 2 4
3 1 2 4
1 2
2 1 3
2 1 4
2 3 4
3 2 3 4
1 3
    예상 출력
    2
4
1
3