#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 3e5 + 7;

int n, m, cur;
int a[N], bio[N];
set <int> adj[N];
vector <pii> res;

void dfs(int x) {
	if (a[cur] != x) {
		res.pb({a[cur-1], a[cur]});
		dfs(a[cur]);
		return;
	}
	cur++;
	bio[x] = 1;
	while (!adj[x].empty()) {
		int y;
		if (cur < n && adj[x].find(a[cur]) != adj[x].end()) y = a[cur];
		else y = *adj[x].begin();
		if (!bio[y]) dfs(y);
		else adj[x].erase(y);
	}
}

int main () {
	FIO;
	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y; x--; y--;
		adj[x].insert(y);
		adj[y].insert(x);
	}
	for (int i = 0; i < n; i++) cin >> a[i], a[i]--;
	
	while (cur < n) dfs(a[cur]);
	
	cout << res.size() << "\n";
	for (auto x : res) cout << x.F+1 << " " << x.S+1 << "\n";

	return 0;
}