Question
Large Connected Components
You are given an undirected graph with KaTeX can only parse string typed expression nodes and KaTeX can only parse string typed expression edges. Your task is to determine how many connected components in the graph contain strictly more than KaTeX can only parse string typed expression nodes.
A connected component is a group of nodes where each node is reachable from every other node in the same group.
The nodes are numbered from KaTeX can only parse string typed expression to KaTeX can only parse string typed expression.
Input
The first line contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — the number of nodes, edges, and the minimum size threshold.
The next KaTeX can only parse string typed expression lines each contain two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — representing an undirected edge between nodes KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — representing an undirected edge between nodes KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Output
Print a single integer — the number of connected components having more than KaTeX can only parse string typed expression nodes.
Example
Input
7 4 2
1 2
2 3
4 5
6 7
Output
1
Explanation
The graph has 3 connected components:
{1, 2, 3} → size = 3
{4, 5} → size = 2
{6, 7} → size = 2
Only one component has more than KaTeX can only parse string typed expression nodes.
7 4 2
1 2
2 3
4 5
6 7
Output
1
Explanation
The graph has 3 connected components:
{1, 2, 3} → size = 3
{4, 5} → size = 2
{6, 7} → size = 2
Only one component has more than KaTeX can only parse string typed expression nodes.