#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
//using i128 = __int128;
#define sz(a) (int)(a.size())
#define rep(x,a,b) for(int x = a; x < b; x++)
#define all(a) a.begin(), a.end()
#define uni(a) a.resize(unique(all(a)) - a.begin())
#define maxe(a) max_element(all(a))
#define mine(a) min_element(all(a))
#define lb(b,val) lower_bound(b.begin(), b.end(), val) - b.begin()
#define ub(b,val) upper_bound(b.begin(), b.end(), val) - b.begin()
#define fd(b,val) find(all(b), val) - b.begin()
#define ct(b,val) count(all(b), val)
#define bp(s) __builtin_popcountll(s)
#define fi first 
#define se second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define sp setprecision
const int mod = 1e9 + 7;
struct DSU{
    vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1)
    {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x)
    {
        return x == f[x] ? x : f[x] = find(f[x]);
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x != y)
        {
            siz[x] += siz[y];
            f[y] = x;
        }
    }
    int size(int x)
    {
        return siz[find(x)];
    }
};
void solve(){
    int n, m, u, v;
    cin >> n >> m;
    vector<int> p(n + 1), st(n + 1), a(n + 1), id(n + 1);
    set<int> g[n + 1];
    DSU dsu(n + 1);
    vector<array<int, 2>> res, ed(m + 1);
    rep(i, 1, m + 1){
        cin >> ed[i][0] >> ed[i][1];
    }
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        a[p[i]] = i;
        id[i] = p[i];
    }
    rep(i, 1, m + 1){
        u = ed[i][0];
        v = ed[i][1];
        g[a[u]].insert(a[v]);
        g[a[v]].insert(a[u]);
        dsu.merge(a[u], a[v]);
    }
    int idx = 1;
    int now = 0;
    function<void(int, int)> dfs = [&](int u, int f){
        st[u] = 1;
        //cout << id[u] << endl;
        now++;
        if(idx > n) return;
        if(idx == u) idx++;
        for(auto v : g[u]){
            if(st[v]) continue;
            if(v == idx){
                dfs(v, u);         
            }      
            else{
                res.pb({id[u], id[idx]});
                idx++;
                dfs(idx - 1, u);           
                dfs(u, f);         
            } 
        }
    };
    rep(i, 1, n + 1){
        now = 0;
        if(!st[i]) dfs(i, 0);
    }
    cout << sz(res) << endl;
    for(auto [x, y] : res) cout << x << " " << y << endl;
}
signed main(){
    int _ = 1;
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    while(_--){
        solve();
    }
    return 0;
}