Indian National Olympiad in Informatics

Online Programming Contest, 5-6 March, 2005

IARCS home > OLYMPIAD

Advanced Division

Problem 2: The Bickering Task Force, (K Narayan Kumar, CMI)

We meet our old friend the Despotic King again. The king was no believer in democracy (understandably) and did not wish to share any information regarding the running of his country even with the nobles in his court. He had a inner circle (a cabal) consisting of a few old friends from his youth and couple of proteges and ran the kingdom with their help. It was however a benevolent dictatorship and thus there was hardly a protest either in the court or among the subjects.

The king's sons and potential successors were however of dubious attitude and quality. Clearly, dictatorship of the incompetent was the future of the country if the king were to abdicate or die. Some of the younger nobles banded together and confronted the king and demanded openness.

The king promised to appoint a Task Force with members selected from among the nobles to oversee the administration of the country. However he wished to choose its members in such a way that they would waste all their time fighting each other, leaving them no opportunity to introduce any changes in the way the country was being run.

His able advisor, the wily prime minister, gave him a list of all the pairs of nobles who hated each other. The king then wanted the minister to pick as large a Task Force as possible (so that his generosity was evident), in such a way that each member of the Task Force hates at least K other members (where K was a number to be determined by the king). The Task Force cannot be empty.

Note that whenever a pair of nobles "A and B" appears in the prime minister's list, it means that A hates B and, symmetrically, B hates A.

Suppose there are 8 nobles and the prime minister's list says that the following pairs of nobles "hate each other":

 1 and 2
 1 and 3
 1 and 5
 1 and 6
 2 and 5
 2 and 6
 3 and 4
 3 and 5
 4 and 6
 4 and 7
 5 and 6
 7 and 8

For K = 2, {1,2,3,4,5,6} is the largest possible Task Force in which everyone hates at least 2 others. In this Task Force, 1 hates 2,3,5 and 6, 4 hates 3 and 6, and so on.

On the other hand, if the king sets K to 3 then {1,2,5,6} would be largest Task Force in which everyone hates at least 3 others. For K = 4 or more, as you can check, there is no way to group the nobles so that every member hates K or more other members in the group.

Your task is to help the minister determine the size of the largest Task Force that can be formed from a given set of nobles in accordance with the king's wishes.

Input format

The first line of the input contains three integers N, M and K. N is the number of nobles, M is the number of pairs of nobles who hate each other and K is the minimum number of members that each member of the chosen group must hate within the group.

The next M lines (lines 2,...,M+1) describe the "hate" relationship. Line i+1 contains two space separated integers Ai and Bi, with 1 ≤ Ai < BiN, indicating that nobles Ai and Bi hate each other.

Output format

The first line of the output must contain either YES or NO.

A YES in the first line indicates that it is possible to select a Task Force in which each member hates at least K others. In this case, the second line of the output contains an integer S giving the size of the largest such Task Force.

A NO indicates that it is not possible to form a Task Force in which each member hates at least K others. In this case the output consists of just one line.

Test Data:

You may assume that N < 3000.

Example:

Here are some sample inputs and outputs corresponding to the examples discussed above.

Sample Input 1

8 12 2
1 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
4 6
4 7
5 6
7 8 

Sample Output 1

YES
6

Sample Input 2

8 12 3
1 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
4 6
4 7
5 6
7 8 

Sample Output 2

YES
4

Sample Input 3

8 12 4
1 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
4 6
4 7
5 6
7 8 

Sample Output 3

NO



Copyright (c) IARCS 2003-2024;   Last Updated: 29 Mar 2005