Telecommunication Partners
By Rodolfo Jardim Azevedo 
Brazil
By Rodolfo Jardim Azevedo Brazil
ICPC, an international telecommunication company, wants to improve its relationship with business subscribers, offering a discount on calls made to a fixed set of telephone numbers selected by the client company. To help ICPC decide on the cost for this new service, they searched their database and produced a list of calls made last year by one company to another. If a company communicated with another company (making or receiving a call) during last year, we will say they are Business Partners.
You have been hired by ICPC to process the list of calls from last year and determine the size (in number of companies) of the largest set of companies that are Business Partners of at least K other companies in the same set and all companies can do business directly or indirectly with any company of this set (one company can do deals directly with another if they are partners or if both are in the same set). That is, you must find a set S of companies such that every company in S has at least K business partners that are also in S (and possibly partners that are outside S), where K is a parameter chosen by the ICPC.
Your program should process several test cases. The first line of a test case contains three integers N, P and K. N represents the total number of companies subscribed to ICPC (1 ≤ N ≤ 1000); companies are identified by numbers between 1 and N. P represents the total number of business partner pairs, produced from last year calls; and K is the minimum number of business partners a company must have in the final set (1 ≤ K ≤ N-1), as described above. The next P lines describe each a business partner pair, represented as two integers X and Y, where X and Y are companies (1 ≤ X ≤ N, 1 ≤ Y ≤ N and X ≠ Y). The value N = 0 indicates the end of input.
For each test case from the input, your program should print a single line, containing the size of the largest set of companies found by your program.
| Sample Input | Sample Output |
|
5 3 1 |
3 |