城市联盟 1189

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：26 AC：9 Score：100

gsy所在的国家共有 n 个城市，这 n 个城市之间共有 m 条双向道路，现在国王想选择一些城市作为 "城市联盟"。

为了联盟内城市的关系融洽，也为了城市之间互相发展，国王定下了组成联盟的规则，对于联盟内的所有城市需要满足以下条件：

1. 在联盟中的每个城市至少要和 x 个联盟内的城市直接相连。

2. 在联盟中的每个城市至少要和 y 个联盟内的城市不直接相连。

现在gsy想要知道这个 "城市联盟" 中最多可以有多少个城市？

第一行包含四个整数 n,m,x,y，含义如题

接下来 m 行每行包含两个整数 u,v 表示 u 和 v 两个城市之间有一条双向道路

对于 100% 的数据，1 <= n <= 500, 1 <= u,v <= n, 0 <= m <= n * (n-1) / 2

输出只有一个整数，表示 "城市联盟" 中最多可以有多少个城市。

input:

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

output: