题目描述

Farmer John 有 N 头奶牛，编号为 1 ~ N。所有奶牛的身高都是正整数，单位厘米。

John 想知道奶牛的身高，所以去收集信息。但是他并没有收集到奶牛的具体身高，只收集到了两种类型的信息：

第一种类型的信息有 P 条，形如 a b 表示奶牛 a 恰好比奶牛 b 矮 1 厘米。

第二种类型的信息有 Q 条，形如 x y 表示奶牛 x 不比奶牛 y 高。

问：奶牛最多可能有多少种不同的身高？

注：如果多头奶牛拥有相同的身高，只能算作一种身高。

输入格式

第一行：包含三个整数 N, P, Q

接下来 P 行，每行包含两个整数 a, b

接下来 Q 行，每行包含两个整数 x, y

输出格式

输出一个整数，表示最多的身高种数。

如果无解，即收集到的信息有误，则输出 -1。

样例1输入

5 2 1
1 2
1 3
4 5

样例1输出

4

样例2输入

3 2 1
1 2
2 3
3 1

样例2输出

-1

数据范围

15% 的数据：$N ≤ 10$。

100% 的数据：$2 ≤ N ≤ 600, 1 ≤ P + Q ≤ 10^5, 1 ≤ a, b, x, y ≤ N$。