#P18873. [HONI 2024/2025 #4] Tura Mačkica

[HONI 2024/2025 #4] Tura Mačkica

题目描述

有 nn 座公园和 n+mn+m 条道路。恰好 mm 条道路各由一只猫巡逻。每只猫只允许游客沿指定方向经过自己的道路,游客经过时就会摸到这只猫。其余 nn 条无猫道路可以双向通行。只用无猫道路也能从任意一座公园到达任意另一座公园。

游客要走一条回到起点的路线,摸到每一只猫。同一条道路最多走一次,反向走也算走过这条道路。开始的公园可以任选。求所需经过的最少道路数。如果无法做到,输出 -1。

输入格式

第一行两个整数 n,mn,m,满足 1≤n≤2⋅1041\le n\le2\cdot10^4、0≤m≤2⋅1040\le m\le2\cdot10^4。

接下来 nn 行,每行两个整数 a,ba,b,表示一条无猫道路连接公园 a,ba,b。允许自环和重边。

再接下来 mm 行,每行两个整数 x,yx,y,表示一条有猫道路只允许从 xx 走到 yy。允许多条道路连接同一对公园。公园编号均在 [1,n][1,n] 内。

输出格式

输出最短路线的长度,无法完成则输出 -1。

子任务

子任务 分值 额外限制
1 11 n,m≤20n,m\le20
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