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 *A*_{i} and
*B*_{i}, with 1 ≤ *A*_{i} <
*B*_{i} ≤ *N*, indicating that nobles
*A*_{i} and *B*_{i} 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-2018; Last Updated: 29 Mar 2005