Problem Statement

Yukiko, who loves Amidakuji (ghost leg), is making an Amidakuji for the "Amida Advent Calendar" again this year.
She first decided on the "correspondence between the starting points and the arrival points of the Amidakuji", and then started making the Amidakuji.
Things went smoothly at first, but she got distracted by other Advent Calendars, and before she knew it, it was the day before her assigned date! All she has at hand is an unfinished Amidakuji!
So, on behalf of Yukiko, write a program that completes the Amidakuji.

The unfinished Amidakuji consists of $N$ vertical lines and $K$ horizontal bars perpendicular to them.
All $K$ horizontal bars are at different heights, and the $k$-th horizontal bar from the top connects the $X_k$-th vertical line from the left and the $Y_k$-th vertical line from the left.

The "correspondence between the starting points and the arrival points of the Amidakuji" that Yukiko first decided on is represented by a permutation $A_i(1\leq i\leq N)$ of $1 \sim N$.
This means that starting from the $i$-th vertical bar from the left, you arrive at the $A_i$-th vertical bar from the left.

Input

$N$
$K$
$X_1$ $Y_1$
$\vdots$
$X_K$ $Y_K$
$A_{1}$ $\dots$ $A_{N}$

The first line contains the number of vertical bars $N$, and the second line contains the number of horizontal bars $K$.
The following $K$ lines contain the information of the horizontal bars.
Line $3+K$ contains $A_i(1\leq i\leq N)$, representing the correspondence between the starting points and the arrival points, separated by spaces.

All inputs are integers and satisfy the following constraints.

• $ 2 \leq N \leq 100 $
• $ 0 \leq K \leq 6000 $
• $ 1 \leq X_i < Y_i \leq N $
• $ X_i + 1 = Y_i $
• $A_i$ is a rearrangement of the sequence $1,2, \dots , N$

Output

Complete the Amidakuji by adding some horizontal bars below the $K$-th horizontal bar from the top.

This problem uses a special judge.
If there are multiple solutions that follow the output format described below, you may output any of them.
It is guaranteed that at least one valid solution exists.

Output Format

Output the horizontal bars to add in the following format.

$L$
$X_{K+1}$ $Y_{K+1}$
$\vdots$
$X_{K+L}$ $Y_{K+L}$

All outputs must be integers and satisfy the following constraints.

• $L$ horizontal bars are added.
• The completed Amidakuji consists of $K + L$ horizontal bars, and its "correspondence between the starting points and the arrival points of the Amidakuji" matches $A$.
• All $K + L$ horizontal bars are at different heights, and the $k(1\leq k\leq K+L)$-th horizontal bar from the top connects the $X_k$-th vertical line from the left and the $Y_k$-th vertical line from the left.
• $ 0 \leq L \leq 6000 $
• $ 1 \leq X_i < Y_i \leq N $
• $ X_i + 1 = Y_i $

Sample

Sample 1

Input

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

Output

3
1 2
3 4
2 3

For example, the Amidakuji is completed by adding 3 bars as shown below.

Sample 2

Input

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

Output

11
1 2
5 6
3 4
5 6
3 4
2 3
1 2
3 4
2 3
4 5
5 6

For example, the Amidakuji is completed by adding 11 bars as shown below.