题目背景

译自 COCI 2024/2025 #4 T5。$\texttt{0.5s,0.5G}$。满分为 $120$。

猫是有很强的领土意识的动物。

题目描述

给定一张 $n$ 个节点，$(n+m)$ 条边的图。

其中 $n$ 条边是无向边，保证只保留这 $n$ 条边时，图仍然连通。 无向边可能有重边自环。

此外，还有 $m$ 条有向边，每条有向边上有一只猫。有向边可能有重边，但没有自环。

大家都喜欢撸猫。为此，你需要找到一条回路，使得这条回路经过每条有向边恰好一次。每条边至多只能经过一次。求出合法的回路的长度的最小值。

（注：从两个方向经过同一条无向边，算作经过两次，因此是不合法的。）

输入格式

第一行，两个非负整数 $n,m$。

接下来 $n$ 行，每行两个正整数 $u_i,v_i$，描述一条无向边 $(u_i,v_i)$。注意可能有重边自环。

接下来 $m$ 行，每行两个正整数 $x_i,y_i$，描述一条有向边 $x_i\to y_i$。注意可能有重边。

输出格式

如果不可能，输出一行一个 $\texttt{-1}$；

否则输出一行一个非负整数表示答案。

5 1
3 1
3 2
3 4
3 5
2 4
3 5

2

6 7
3 2
5 3
1 4
6 1
5 6
4 2
4 5
1 2
4 2
2 6
3 1
1 6
6 4

10

7 3
4 1
4 3
6 4
2 6
5 2
5 7
4 4
3 6
4 1
7 5

-1

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^4$；
• $0\le m\le 2\times 10^4$；
• $1\le u_i,v_i,x_i,y_i\le n$；
• 只保留 $n$ 条无向边时，图是连通的；
• $x_i\neq y_i$。

• 特殊性质 A：无向边中存在自环。