Please click here to download a PDF version of the contest problems. The problem is problem G in the PDF. Remember that you must use stdin/stdout at SPOJ.

---

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:

1. Any invited person must have at least A acquaintances at the party. This is to ensure everyone at the party will not feel alien.
2. 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.

Example

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

Output:
Case #1: 0
Case #2: 4

---

hide comments

	Simes: 2023-02-04 16:48:40 I've extracted the problem from the PDF. I hope that's ok? If there are any mistakes or discrepancies, assume the PDF is correct.