Cycle-Free Paths for Important Vertices

This problem is a variant of the cycle elimination problem. You are given an undirected graph with n vertices and m edges. Additionally, the vertices are numbered from 1 to n, and vertices with labels ≤ k are considered important.

Your task is to remove as few edges as possible so that no simple cycle in the remaining graph contains any important vertex. In other words, for every vertex v with v ≤ k, there should be no cycle passing through v.

Note: A simple cycle is a cycle that does not repeat vertices (except for the starting and ending vertex). Cycles that involve only vertices with labels greater than k are allowed.

The condition for an important vertex v to be cycle‐free is equivalent to the following: if you remove v from the graph, then no two neighbors of v are connected by a path. Equivalently, for every important vertex v with at least two neighbors, if there exists a path between any two distinct neighbors (after removing v), then v lies in a cycle. You need to remove enough edges so that this does not happen.

The mathematical condition when a cycle is formed can be expressed in \( \LaTeX \) as follows: if vertex \( v \) has neighbors \( u_1, u_2, \ldots, u_d \) in the remaining graph, then a necessary and sufficient condition for \( v \) to appear in a cycle is that there exists \( i \neq j \) such that:

[ \exists, u_i, u_j \text{ with } u_i \neq u_j \text{ and } u_i \stackrel{G\setminus {v}}{\longleftrightarrow} u_j. ]

Your goal is to compute the minimum number of edges that need to be removed to satisfy the condition for every important vertex.

inputFormat

The input consists of:

• The first line contains three integers n, m, and k — the number of vertices, edges, and the number of important vertices (vertices with labels ≤ k).
• The next m lines each contain two integers u and v (1-indexed) representing an undirected edge between vertices u and v.

You may assume that 1 ≤ k ≤ n and that the graph does not contain self-loops or multiple edges.

outputFormat

Output a single integer — the minimum number of edges to remove so that no important vertex (vertex with label ≤ k) lies on any simple cycle.

sample

3 3 2
1 2
2 3
1 3

1