#include<bits/stdc++.h>

using namespace std;   

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

int n, m;
vector<vector<int>> g;
vector<int> p;

bool read() {
	if (!(cin >> n >> m))
		return false;
	g.assign(n, {});
	forn(i, m){
		int v, u;
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	p.resize(n);
	forn(i, n){
		cin >> p[i];
		--p[i];
	}
	return true;
}

void solve() {
	forn(i, n) sort(g[i].begin(), g[i].end());
	vector<int> lft(n);
	forn(i, n) lft[i] = g[i].size();
	vector<int> st;
	vector<pair<int, int>> res;
	int ans = 0;
	for (int v : p){
		while (!st.empty()){
			int u = st.back();
			if (binary_search(g[u].begin(), g[u].end(), v))
				break;
			if (lft[u] != 0){
				res.push_back({v, u});
				++ans;
				break;
			}
			st.pop_back();
		}
		st.push_back(v);
		for (int u : g[v]){
			--lft[u];
		}
	}
	cout << ans << '\n';
	for (auto [v, u] : res)
		cout << v + 1 << " " << u + 1 << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	//cin >> t;
	while (read()){
		solve();
	}
}