← 返回题目列表

AtCoder · arc049_c

C. 着色

中文机器翻译题面 查看原题

問題文

高桥在旅行时买了一种名为“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