Get-Together at Stockholm

Time Limit: 3000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Peter has recently decided to hold a party at Stockholm, where the ACM/ICPC 2009 World Final will be held. Unfortunately, despite Peter’s affluence, he is not able to invite all of his friends due to the astronomical price of the air ticket to Stockholm.
He has devised the following rule to determine which subset of his friends will be invited:
a) Any invited person must have at least A acquaintances at the party. This is to ensure everyone at the party will not feel alien.
b) Any invited person must be unfamiliar with at least B people. Otherwise some people may not have the chance to communicate with a stranger.
Given the relationships between Peter’s friends, you are to figure out whom Peter should invite to the party so as to maximize its size.

Input

There are multiple test cases in the input file.
Each test case starts with four integers, N, M, A, and B ( 1 ≤ N ≤ 100 , 0 ≤ M ≤ N*(n-1)/2 , 0 ≤ A , B ≤ N - 1). Each of the following M lines contains
two integers, X and Y, ( 0 ≤ X,Y ≤ N-1 , X≠Y), indicating that friend X and friend Y are acquaintances.
Two successive test cases are separated by a blank line. A case with N = 0, M = 0,A = 0 and B = 0 indicates the end of the input file, and should not be processed by your program.

Output

For each test case, please print a single integer, the maximum number of friends
Peter will be able to invite.

Sample Input

3 2 1 1 0 1 1 2 4 4 2 1 0 1 1 2 2 3 0 3 0 0 0 0

Sample Output

Case #1: 0 Case #2: 4

Hint

lcy

Source

2008 Asia Regional Hangzhou

提交代码