← 返回题目列表

Codeforces · 177/C2

C2. 聚会

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

为了庆祝第二届 ABBYY 杯锦标赛,Smart Beaver 决定举办一场派对。海狸有很多熟人,有的人是朋友,有的人互相不喜欢。为了使聚会成功,聪明的海狸只想邀请那些有朋友关系的朋友,而不邀请那些互相不喜欢的人。友情和厌恶都是相互的感情。

更正式地说,每个受邀者应满足以下条件:

- 他所有的朋友也应该被邀请参加聚会;
- 党内不应该有他不喜欢的人;
- 所有被邀请参加聚会的人都应该直接或通过任意长度的共同朋友链与他建立友谊。如果存在一系列人 a2, a3, ..., ap - 1,使得所有对的人 ai 和 ai + 1 (1 ≤ i < p) 都是朋友,我们会说人 a1 和 ap 通过共同朋友链连接起来。

帮助海狸找到他可以邀请的熟人的最大数量。

输入

输入的第一行包含一个整数n——海狸的熟人数量。

第二行包含一个整数 k $$( 0 \leq k \leq \min ( 1 0 ^ { 5 }, \frac { n \cdot ( n - 1 ) } { 2 } ) )$$ — 好友对的数量。接下来的 k 行包含空格分隔的整数对 ui, vi $$( 1 \leq u _ { i }, v _ { i } \leq n, u _ { i } \neq v _ { i } )$$ — 构成第 i 对朋友的人的索引。

下一行包含一个整数 m $$( 0 \leq m \leq min(10^{5},\frac{n(n-1)}{2}))$$ — 互相不喜欢的人对的数量。接下来的 m 行以与描述朋友对相同的格式描述彼此不喜欢的人对。

每对人在输入中最多被提及一次 $$( 0 \leq k + m \leq \frac { n \cdot ( n - 1 ) } { 2 } )$$。特别是,两个人不能同时成为朋友,同时又互相不喜欢对方。

获得 30 点的输入限制为:

- 2 ≤ n ≤ 14

获得 100 点的输入限制为:

- 2 ≤ n ≤ 2000

输出

输出一个数字——可以邀请参加聚会的最大人数。如果无法选出满足所有要求的一组人,则输出0。

示例

输入 #1

9
8
1 2
1 3
2 3
4 5
6 7
7 8
8 9
9 6
2
1 6
7 9

输出 #1

3

注意

让我们看一下这个例子。

可以邀请两组人:{1, 2, 3} 和 {4, 5},因此答案将是这些组中最大组的人数。组 {6,7,8,9} 不适合,因为它包括互相不喜欢的人 7 和 9。组 {1, 2, 3, 4, 5} 也不适合,因为并非所有成员都通过一系列共同的朋友联系在一起(例如,人 2 和 5 没有联系)。