首先我们可以发现最无脑的做法就是直接枚举所有无向边是不走，还是走，如果走那么是哪一个方向，然后这就是一个有向图，可以直接通过有向图欧拉路的性质来判断是否合法。

但是这样甚至可能最低的部分分都跑不过。

先考虑树的情况，我们已知知道了每条有向边的方向且这些边必须要走。

那么们从下到上递归遍历，发现在子树内的边已经全部确定时，这棵子树只能通过父亲节点使自己的出度或入度加上一或者不变。我们明显需要使子树内的出入度相等，可以设出为正一，入为负一，这样可以快速求出子树是需要出还是入，确定到父亲的边的方向。

确定了方向之后，我们需要再确定是否满足欧拉路的性质，先判断每个点的出入度是否相等，如果不相等，那么不成立。然后判断是否所有的边都连通，我是拿并查集直接实现的。

考虑变成基环树的情况，那么就是多加上了一条无向边，找到一个删掉以后会变成一个树的边，把这条边的三个方向枚举一遍，取一次最短的结果即可。

时间复杂度 $O(n+m)$。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,tmpu,tmpv,fa[20005],d[20005],f[20005],ans,du[20005];
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
vector<int> e[20005],e2[20005],e3[20005];
bool dfs(int p,int fa2,int &res){
	f[p]=d[p];
	for(int i:e[p]){
		if(i==fa2)continue;
		if(dfs(i,p,res))return true;
		f[p]+=f[i];
	}
	for(int i:e3[p])fa[find(i)]=find(p);
	if(abs(f[p])>1)return true;
	if(f[p]==1)e2[fa2].push_back(p),res++,fa[find(fa2)]=find(p);
	if(f[p]==-1)e2[p].push_back(fa2),res++,fa[find(p)]=find(fa2);
	return false;
}
void solve(){
	int res=0;
	for(int i=1;i<=n;i++)for(int j:e3[i])e2[i].push_back(j);
	for(int i=1;i<=n;i++)fa[i]=i;
	if(dfs(1,0,res))return;
	memset(du,0,sizeof(du));
	for(int i=1;i<=n;i++)for(int j:e2[i])du[j]++;
	for(int i=1;i<=n;i++)if(du[i]!=e2[i].size())return;
	int tmp=0;
	for(int i=1;i<=n;i++)if(find(i)!=i){
		if(find(i)==tmp||!tmp)tmp=find(i);
		else return;
	}
	ans=min(ans,m+res);
}
signed main(){
	cin>>n>>m;
	if(!m){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1,u,v;i<=n;i++){
		cin>>u>>v;
		if(find(u)!=find(v)){
			e[u].push_back(v),e[v].push_back(u);
			fa[find(u)]=find(v);
		}
		else tmpu=u,tmpv=v;
	}
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		e3[u].push_back(v);
		d[u]++,d[v]--;
	}
	ans=1e18;
	solve();
	if(tmpu!=tmpv){
		m++;
		for(int i=1;i<=n;i++)e2[i].clear();
		e2[tmpu].push_back(tmpv);
		d[tmpu]++,d[tmpv]--;
		solve();
		for(int i=1;i<=n;i++)e2[i].clear();
		e2[tmpv].push_back(tmpu);
		d[tmpu]-=2,d[tmpv]+=2;
		solve();
	}
	if(ans==1e18)cout<<-1;
	else cout<<ans;
	return 0;
}