아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

부대 창설 행사

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

요약
각 병사가 희망 무대 중 가장 앞선 하나에만 배치될 때 모든 무대의 최소 인원을 채우는 무대 순서를 찾는다.
난이도

보통10점 중 7점

유형
그리디, 정렬, 구간, 위상 정렬
정답자
아직 제출이 없습니다

문제

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

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

성공적인 행사를 위해선 무대마다 정해진 최소 인원수를 만족해야 한다. 그러나 인원을 세심하게 분배할 여유가 없기 때문에, 우선 무대 순서를 확정한 뒤 해당 무대를 희망했던 병사들을 무대에 세울 예정이다. 다만, 모든 병사는 연습에 집중하기 위해 본인이 희망한 가장 앞 순서의 무대에만 참여한다.

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

입력

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

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

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

출력

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

가능한 순서가 존재하지 않는다면, -1을 출력한다.

제한

  • 1≤N≤50,0001 \le N \le 50\\,000
  • 1≤P≤100,0001 \le P \le 100\\,000
  • 1≤m_i≤P1 \le m\_i \le P
  • 1≤x_i≤N;1 \le x\_i \le N; x_ix\_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