시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB164573940.206%

문제

다음 조건을 만족하는 배열 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

예제 입력 1

3 2
1 2 3
2 1
1 3

예제 출력 1

2 1 3

예제 입력 2

3 2
1 2 3
2 1
1 2

예제 출력 2

-1

예제 입력 3

3 0
1 2 3

예제 출력 3

1 2 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

예제 출력 4

2 4 3 5 4 7 6 8 3

출처