[COCI 2024/2025 #4] 猫 / Tura Mačkica

译自 [COCI 2024/2025 #4](https://hsin.hr/coci/) 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$。 | 子任务编号 | $n,m\le$ | 特殊性质 | 得分 | | :--: | :--: | :--: |:--: | | $ 1 $ | $20$ | | $ 11 $ | | $ 2 $ | $2\times 10^4$ | A | $ 41 $ | | $ 3 $ | $2\times 10^4$ | | $ 68 $ | - 特殊性质 A：无向边中存在自环。