#P18873. [HONI 2024/2025 #4] Tura Mačkica
[HONI 2024/2025 #4] Tura Mačkica
题目描述
有 座公园和 条道路。恰好 条道路各由一只猫巡逻。每只猫只允许游客沿指定方向经过自己的道路,游客经过时就会摸到这只猫。其余 条无猫道路可以双向通行。只用无猫道路也能从任意一座公园到达任意另一座公园。
游客要走一条回到起点的路线,摸到每一只猫。同一条道路最多走一次,反向走也算走过这条道路。开始的公园可以任选。求所需经过的最少道路数。如果无法做到,输出 -1。
输入格式
第一行两个整数 ,满足 、。
接下来 行,每行两个整数 ,表示一条无猫道路连接公园 。允许自环和重边。
再接下来 行,每行两个整数 ,表示一条有猫道路只允许从 走到 。允许多条道路连接同一对公园。公园编号均在 内。
输出格式
输出最短路线的长度,无法完成则输出 -1。
子任务
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 11 | |
| 2 | 41 | 至少一条无猫道路是自环 |
| 3 | 68 | 无 |
样例
样例 1
输入
5 1
3 1
3 2
3 4
3 5
2 4
3 5
输出
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
输出
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