Problem A
Swapping Places

You got a new graph $G=(V,E)$! It is undirected and has a unique number $v$ at each vertex. It is built (out of wood, steel and marble) in a way that lets you perform a swap on any edge $e\in E$, which has the effect of swapping the two numbers $u$ and $v$ on the vertices which $e$ connects.

Unfortunately, when you got the graph the numbers were all scrambled in a way that you do not like. So you came up with a function, in fact a permutation, $\sigma (v)$ that you feel is a better expression of your preferences. You would like to relabel each vertex so that the vertex currently labelled $v$ will then be labelled $\sigma (v)$.

Is it possible to come up with a sequence of at most $|V|^2$ edge swaps so that after all the swaps are done, every number label $v$ is replaced with $\sigma (v)$? If so, provide this sequence of swaps. Otherwise, indicate that it is impossible.

Input

The first line of input contains two integers $N$ and $M$, denoting the number of vertices and number of edges. It is guaranteed that $N \le 10^3$ and $M\le \binom N2$. The following $M$ lines contain two integers each. The $i^{th}$ such line contains integers $u_ i$ and $v_ i$, where $1\le u_ i,v_ i\le N$ and $u_ i\ne v_ i$, indicating that there is an edge connecting the vertices numbered $u_ i$ and $v_ i$. The last line contains $N$ integers, where the $i^{th}$ integer ($1 \leq i \leq N$) is the value $\sigma (i)$. All values in $\sigma $ will be unique, that is, $\sigma $ is a permutation.

Output

If it is impossible to change the numbers as desired using any sequence of at most $|V|^2$ edge swaps, output a single line with the word impossible.

Otherwise, you should output a sequence of edge swaps. The first line of output should contain a single integer $k$ ($0\le k\le N^2$) indicating the number of swaps to follow. Then $k$ lines follow describing the sequence of edge swaps. The $i^{th}$ line should contain two integers $a_ i$ and $b_ i$ which should be swapped. There must be an edge connecting the vertices currently labelled with $a_ i$ and $b_ i$ when they are swapped.

3 3
1 2
2 3
3 1
3 2 1

1
1 3

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

impossible