Sorting Students with Pair Constraints

You are given n students along with their heights and m pairs of indices. Each pair indicates that the two students corresponding to these indices must stand next to each other in the final arrangement.

Your task is to rearrange the students so that their heights are in non-decreasing order while ensuring that for every given pair \((i,j)\), the two students (identified by their original indices) appear consecutively in the sorted order.

If it is impossible to rearrange the students to meet the pair constraints, output -1.

Note: In your final answer, the positions of students are determined solely by the sorted order of their heights. For each pair \((i,j)\), if the positions of heights corresponding to indices \(i\) and \(j\) (in the sorted array) are \(p_i\) and \(p_j\), respectively, then the condition \(|p_i-p_j|=1\) must hold.

inputFormat

The input is read from standard input (stdin) and is in the following format:

1. The first line contains an integer n representing the number of students.
2. The second line contains n space-separated integers, the heights of the students.
3. The third line contains an integer m representing the number of pairs.
4. The following m lines each contain two space-separated integers, indicating a pair of indices (0-indexed) that must stand together.

outputFormat

Output the sorted list of students' heights (space separated) if it is possible to rearrange them while keeping each specified pair adjacent. If such an arrangement is impossible, output -1.## sample

4
150 160 155 165
2
0 2
1 3

150 155 160 165