Maximum Committee

A party with n members is looking to develop a set of new policies. To do this, the party plans to form a committee for the development of these policies. In order for the policies to develop best, the committee should be as large as possible and every pair of committee members must disagree with each other.

In order to decide which pair of politicians disagree (and which agree), the party arranged for every possible pair of members to discuss a randomly chosen topic. Whenever two politicians cannot reach a consensus on the given topic, they are recorded in the party's merit book. With this book in hand, you are asked to select the largest committee such that no pair of its members has a consistent opinion.

However, it turns out that forming a large committee is challenging. Detailed analysis shows that for any nonempty subset of party members, there is at least one member who disagrees with strictly fewer than \( k \) other members in that subset. Hence, it is clear that the committee cannot have more than \( k \) members. The problem is: can one always select a committee of this size? In short, find the largest possible committee (i.e. the maximum clique in the disagreement graph) satisfying the condition that every two members disagree.

One-line summary: Given a graph that satisfies the property that for any nonempty induced subgraph there is a vertex with degree less than \( k \), determine the maximum clique size in the original graph.

inputFormat

The first line of input contains three integers \( n \), \( m \), and \( k \) (where \( n \) is the number of vertices, \( m \) is the number of edges, and \( k \) is the given parameter such that every nonempty induced subgraph has a vertex of degree < \( k \)).

Each of the following \( m \) lines contains two integers \( u \) and \( v \) (1-indexed) indicating that there is an edge between vertices \( u \) and \( v \). It is guaranteed that the graph satisfies the property described above.

outputFormat

Output a single integer: the size of the maximum clique (i.e. the largest committee) in the graph.

sample

4 4 3
1 2
2 3
3 4
1 4

2