众所周知，萨格勒布有 $n$ 个公园，$m$ 只猫，以及 $n + m$ 条连接这些公园的街道。猫是非常有领地意识的动物，因此每条街道上最多只有一只猫。猫在街道上巡逻，会猛烈攻击任何沿该方向行进的人，但对于沿相反方向行进的人，它会要求对方抚摸它才允许通过。萨格勒布市意识到这一情况，确保了市民仅使用 $n$ 条没有猫的街道就能从任意一个公园到达其他任何公园。

旅游中心决定在萨格勒布开设所谓的“猫咪之旅”。游客将能够抚摸萨格勒布的每一只猫，并返回起始地点，以便重新开始。为了确保游客不会迷路，旅游中心会在每条街道上设置路标，告诉他们接下来应该走哪条街道，因此猫咪之旅不能走同一条街道两次（即使是反方向也不行）。显然，游客期望抚摸每一只猫，且不被任何猫攻击，同时行程尽可能短。

请帮助旅游中心找到最短的猫咪之旅长度，或者指出这是不可能的。

输入格式

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

接下来的 $n$ 行包含每对 $a, b$ ($1 \le a, b \le n$)，描述没有猫的街道。注意，可能存在 $a = b$ 的情况，也可能有多条街道连接相同的公园。

接下来的 $m$ 行包含每对 $x, y$ ($1 \le x, y \le n$)，描述猫允许从 $x$ 通行到 $y$ 的街道。注意，可能有多条街道连接相同的公园。

输出格式

在唯一的一行中，输出最短猫咪之旅的长度，如果不存在猫咪之旅，则输出 “-1”。

子任务

样例

输入格式 1

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

输出格式 1

2

说明

最短的猫咪之旅是 $3 \to 5 \to 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

输出格式 2

10

输入格式 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