#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 2007, mod = 998244353;

int n, m;
bitset < N > e[N], e2[N], ban;

bitset < N > go[N][2];
int top[N][2];

inline int Back(int x, int o) {
	while(top[x][o] >= 0 && !go[x][o][top[x][o]]) --top[x][o];
	return top[x][o];
}

vector < array < int, 4 > > ans;
void op(int x, int y) {
	if(x == y) {
		cout << "???" << endl;
		exit(0);
	}
	e[x][y] = 1 - e[x][y];
	e[y][x] = 1 - e[y][x];
}
inline void doit(int a, int b, int c, int d) {
	if(!e[a][b] || !e[c][d] || e[b][c] || e[a][d]) {
		cout << "xdmwxl" << endl;
		exit(0);
	}
	swap(a, b);
	if(!e[a][b] || !e[c][d] || e[a][c] || e[b][d]) {
		cout << "yrzjzycn" << endl;
		exit(0);
	}
	array < int, 4 > R = {a, b, c, d};
	ans.emplace_back(R), op(a, b), op(c, d), op(a, c), op(b, d);
}

int ok; 
void solve(int *a, int len) {
	if(len == 4) {
		if(a[0] >= n) {
			doit(a[0] % n, a[1] % n, a[2] % n, a[3] % n);
		} else {
			doit(a[1] % n, a[2] % n, a[3] % n, a[0] % n);
		}
		return ;
	}
	int rp = -1;
	for(int p = 1; p < n; p += 2) {
		if(abs(a[p] - a[0]) == n) {
			rp = p;
		}
	}
//	if(abs(a[0] - a[3]) == n)
	if(rp != -1) {
		int sav = a[-1];
		a[-1] = a[len - 1];
		solve(a - 1, len);
		a[-1] = sav;
		return ;
	}
	int sav = a[len];
	a[len] = a[0];
	if(e[a[0] % n][a[3] % n] == a[3] / n) {
		solve(a, 4), solve(a + 3, len - 2);
	} else {
		solve(a + 3, len - 2), solve(a, 4);
	}
	a[len] = sav;
}

int pool[N * N * 2], *STK = pool + N * N;
int MP[N];
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 
	cin >> n >> m;
	L(i, 1, m) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		e[u].set(v);
		e[v].set(u);
	}
	
	L(i, 1, m) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		e2[u].set(v);
		e2[v].set(u);
	}
	
	L(i, 0, n - 1) {
		if(e[i].count() != e2[i].count()) {
			cout << -1 << '\n';
			return 0;
		} 
	}
	L(i, 0, n - 1) {
		top[i][0] = top[i][1] = n;
		L(j, i + 1, n - 1) {
			if(e[i][j] != e2[i][j]) {
				go[i][e[i][j]][j] = 1;
				go[j][e[i][j]][i] = 1;
			} 
		}
	}
	
	me(MP, -1);
	L(u, 0, n - 1)
		while(true) {
			if(Back(u, 0) == -1) break;
			int x = u;
			int cur = 0;
			int top = 0;
			while(true) {
				int rid = cur * n + x;
				if(MP[rid] != -1) {
					int l = MP[rid], r = top;
					L(i, l, r - 1) MP[STK[i]] = -1;
					solve(STK + l, r - l);
					top = l;
					if(top == 0) break; 
					continue;
				}
				MP[rid] = top, STK[top++] = rid;
				int y = Back(x, cur);
				go[x][cur][y] = 0;
				go[y][cur][x] = 0;
				cur ^= 1, x = y;
			}
		}
	L(i, 0, n - 1) {
		L(j, 0, n - 1) {
			if(e[i][j] != e2[i][j]) {
				cout << "wawaa" << endl;
				exit(0);
			}
		}
	}
	cout << sz(ans) << '\n';
	for(auto u : ans) 
		cout << u[0] + 1 << ' ' << u[1] + 1 << ' ' << u[2] + 1 << ' ' << u[3] + 1 << '\n';
	return 0;
}