배열 A 찾기

시간 제한2초메모리 제한512 MB

요약
크기 N인 배열 A 중 B보다 사전 순으로 뒤에 오면서 M개의 A[i] < A[j] 조건을 만족하는 것 가운데 사전 순으로 가장 앞서는 배열을 구하고, 없으면 -1을 출력한다.
난이도

보통10점 중 7점

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

문제

다음 조건을 만족하는 배열 A를 찾아보자.

  • 크기는 N이고, 2×109보다 작거나 같은 자연수로 이루어져 있다.
  • 크기가 N인 배열 B보다 사전 순으로 뒤에 온다.
  • M개의 (i, j)쌍은 A[i] < A[j]를 만족한다.

입력

첫째 줄에 배열의 크기 N과 쌍의 개수 M이 주어진다. 둘째 줄에는 B[1], B[2], ..., B[N]이 주어진다. 셋째 줄부터 M개의 줄에는 A[i] < A[j]를 의미하는 i, j가 주어진다.

출력

문제의 조건을 만족하는 배열 A 중에서 사전 순으로 가장 앞서는 것을 출력한다. 만약, 조건을 만족하는 배열이 없는 경우에는 -1을 출력한다.

제한

  • 1 ≤ N ≤ 100,000
  • 0 ≤ M ≤ 100,000
  • 1 ≤ B[i] ≤ 109
  • 1 ≤ i, j ≤ N, i ≠ j

예제4

  1. 예제 1

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

  2. 예제 2

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

  3. 예제 3

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

  4. 예제 4

    입력
    9 10
2 4 3 5 1 7 2 9 3
1 9
1 4
2 4
3 5
5 7
4 7
5 6
7 6
6 8
7 8
    예상 출력
    2 4 3 5 4 7 6 8 3