Hamiltonian Path in Dungeons

You are given a set of n dungeons numbered from 1 to n, each with an associated difficulty. There are m bidirectional tunnels connecting these dungeons. The hero must start at the dungeon with the lowest difficulty and finish at the dungeon with the highest difficulty. Your task is to determine whether there exists a Hamiltonian path (i.e. a path that visits every dungeon exactly once) that starts at the dungeon with the minimum difficulty and ends at the dungeon with the maximum difficulty.

If there is such a path, output the order of dungeons (using 1-indexing) that the hero should follow. Otherwise, output Impossible.

Formally, let \(D = \{d_1, d_2, \dots, d_n\}\) be the set of dungeons with difficulties. Let s be the index such that \(d_s = \min\{d_i\}\) and e be the index such that \(d_e = \max\{d_i\}\). You must find a sequence \(P = [p_1, p_2, \dots, p_n]\) where all \(p_i\) are distinct, \(p_1 = s\) and \(p_n = e\), and for every consecutive pair \(p_i, p_{i+1}\), there exists a tunnel connecting these two dungeons.

inputFormat

The input is given via standard input and has the following format:

n m
d1 d2 ... dn
u1 v1
u2 v2
... 
u_m v_m

Here, n and m denote the number of dungeons and tunnels, respectively. The second line contains n integers representing the difficulty of each dungeon. Each of the next m lines contains two integers u and v, indicating that there is a tunnel between dungeon u and dungeon v.

The starting dungeon is the one with the minimum difficulty and the ending dungeon is the one with the maximum difficulty.

outputFormat

Output a single line to standard output. If a valid Hamiltonian path exists, print n space-separated integers denoting the order in which the dungeons are visited (1-indexed). If no such path exists, print Impossible.

## sample

4 4
1 2 3 4
1 2
2 3
3 4
4 1

1 2 3 4

</p>