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

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

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.

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.

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.

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.

提交代码