問題文
高桥在旅行时买了一种名为“Nurimasu”的油漆,作为在比赛中获得最高奖项的奖励。
此外,高桥有 N 我有一个顶点有向图,图的每个顶点都是一个顶点 表示为 1, 頂点 2, ..., 頂点 N 。
高桥喜欢着色,因此他正在考虑使用他的“着色火星”来为手头的有向图的顶点着色。 然而,随机着色并不有趣,因此我们将在一些顶点之间的以下约束下着色。
- 类型 1:顶点 当给 x 着色时,顶点已经是 y 必须是彩色的。
- 类型 2:顶点 u 着色时,顶点已经是 v 至不得着色。
类型 1 约束的数量为 A 并且类型 2 约束的数量是 B 件。
最初,所有顶点都没有着色。 您的任务是以适当的顺序为图的顶点着色,并最终找到着色的顶点的最大数量。
入力
输入是按以下格式从标准输入给出的。
N A x_1 y_1 x_2 y_2 : x_A y_A B u_1 v_1 u_2 v_2 : u_B v_B
- 1 行包含一个整数,表示图中的顶点数。 N (1≦N≦100) 。
- 2 行包含一个整数,表示类型 1 约束的数量。 来自行 A (0≦A≦100) 。
- 3 从线 A 行提供有关类型 1 约束的信息。这几天之一 i (1≦i≦A) 行``某个顶点 x_i 着色时,顶点已经是 y_i 必须是彩色的。 ” 代表约束条件 2 整数 给出了 x_i,y_i(1≦x_i,y_i≦N,x_i≠y_i) 用空格分隔。
- 3+A 行包含一个整数,表示类型 2 约束的数量。 B (0≦B≦10) 。
- 3+A+1 从线 B 行提供有关类型 2 约束的信息。这几天之一 i (1≦i≦B) 行``某个顶点 u_i 着色时,顶点已经是 v_i 不得着色。 ” 代表约束条件 2 整数 给出了 u_i,v_i(1≦u_i,v_i≦N,u_i≠v_i) 用空格分隔。
- 可以给出约束的组合,使得出现在该约束下永远无法填充的顶点。此外,存在可能向多个用户给予相同约束的可能性。
出力
输出最终着色的最大顶点数。在输出末尾添加换行符。
入力例 1
3 2 1 2 2 3 1 3 1
出力例 1
3
您可以按照顶点 3 → 顶点 2 → 顶点 1 的顺序着色。
入力例 2
3 2 1 2 2 3 1 1 3
出力例 2
2
在此约束下,无法绘制顶点 1。
入力例 3
3 3 1 2 2 3 3 1 0
出力例 3
0
在此约束下,任何顶点都不能着色。
入力例 4
9 7 1 2 1 3 5 4 8 5 9 8 6 1 7 1 2 1 4 4 1
出力例 4
6
入力例 5
100 0 0
出力例 5
100