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

题目背景

译自 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}$；

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

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #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

输出 #2

10

输入输出样例 #3

输入 #3

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

输出 #3

-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$ 条无向边时，图是连通的；

子任务编号	$n,m\le$	特殊性质	得分
$1$	$20$		$11$
$2$	$2\times 10^4$	A	$41$
$3$			$68$

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

#5722. 「COCI 2024/2025 #4」Tura Mačkica

标签: 传统 | 时间限制: 500 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #4 T5「Tura Mačkica」

众所周知，Zagreb 有 $n$ 个公园，$m$ 只猫，以及 $n+m$ 条连接公园的街道。猫是非常有领地意识的动物，因此每条街道上最多只有一只猫。它会凶猛地攻击沿着街道某一特定方向行进的每个人，但对于从相反方向行进的人，它会要求必须被抚摸（pets）后才允许通过。Zagreb 市政府意识到了这一情况，确保市民仅利用那 $n$ 条没有猫的街道，就能从任意一个公园到达另一个公园。

旅游中心决定在 Zagreb 开启一项所谓的「寻猫之旅（Cat Tour）」。参加该路线的游客将能够抚摸 Zagreb 的每一只猫，并返回起点，以便可以循环往复。为了确保游客不会迷路，旅游中心会在每条街道上设置指示牌告知他们下一步该走哪条街，因此寻猫之旅不能两次经过同一条街道（即使行驶方向不同也不行）。显然，游客们期望抚摸每一只猫，且不被任何一只猫攻击，同时整个路线尽可能短。

请帮旅游中心计算最短寻猫之旅的长度；若寻猫之旅不存在，则输出 $-1$。

输入格式

第一行包含两个整数 $n, m$ $(1 \leq n \leq 2 \cdot 10^{4}, 0 \leq m \leq 2 \cdot 10^{4})$，分别代表公园的数量和猫的数量。

接下来的 $n$ 行包含成对的整数 $a, b$ $(1 \leq a, b \leq n)$，描述没有猫的街道。注意可能存在 $a=b$，或者两条及以上的街道连接相同的公园。

接下来的 $m$ 行包含成对的整数 $x, y$ $(1 \leq x, y \leq n)$，描述猫允许从 $x$ 到 $y$ 通行的街道。注意同样可能存在两条及以上的街道连接相同的公园。

输出格式

在一行中输出最短寻猫之旅的长度。若寻猫之旅不存在，输出 $-1$。

样例 1

输入

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

输出

2

最短寻猫之旅为 $3 \rightarrow 5 \rightarrow 3$。

样例 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

样例 3

输入

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

输出

-1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$11$	$n, m \leq 20$
$2$	$41$	存在一条连接公园与其自身的街道，且该街道没有猫巡逻。
$3$	$68$	无附加限制。