# 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.

Sample Input 1 | Sample Output 1 |
---|---|

3 3 1 2 2 3 3 1 3 2 1 |
1 1 3 |

Sample Input 2 | Sample Output 2 |
---|---|

5 4 1 2 3 4 4 5 5 3 2 3 1 4 5 |
impossible |