import           Control.Applicative
import           Control.Monad       (replicateM)
import           Data.List           (break, concatMap)
import qualified Data.Vector.Unboxed as V
import           Text.Printf

readInts :: IO [Int]
readInts = map read . words <$> getLine

main = do
  n <- readLn
  k <- readLn
  xs <- replicateM k $ do
    [x, y] <- readInts
    return (x, y)
  let go (x, y) i
        | x == i = y
        | y == i = x
        | otherwise = i
      bs = V.fromList $ 0 : map (\i -> foldr go i xs) [1..n]
  as <- V.fromList . (0:) <$> readInts
  let cs = map (\i -> as V.! (bs V.! i)) [1..n]
      go' (i, c) (xs, ys) = let (a, _:b) = break (== c) ys
                                j = length a + 1
                            in ([(k, k + 1) | k <- [i-1,i-2..j]] ++ xs, a ++ b)
      (left, _) = foldr go' ([], [1..n]) $ zip [1..n] cs
  printf "%d\n" $ length left
  mapM_ (\(x, y) -> printf "%d %d\n" x y) left