4654：k-edge connected components

Efficiently computing k-edge connected components in a large graph G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Computing k-edge connected components has many real applications. For example, in social networks, computing k-edge connected components can identify the closely related entities to provide useful information for social behavior mining. In a web-link based graph, a highly connected graph may be a group of web pages with a high commonality, which is useful for identifying the similarities among web pages. In computational biology, a highly connected subgraph is likely to be a functional cluster of genes for biologist to conduct the study of gene microarrays. Computing k-edge connected components also potentially contributes to many other technology developments such as graph visualization, robust detection of communication networks, community detection in a social network.

Clearly, if a graph G is not k-edge connected, there must be a set C of edges, namely a cut, such that the number |C| of edges in C is smaller than k and the removal of the edges in C cuts the graph G into two disconnected subgraphs G₁ and G₂. A connected component is a maximal connected subgraph of G. Note that each vertex belongs to exactly one connected component, as does each edge.

Now, we give you a undirected graph G with n vertices and m edges without self-loop or multiple edge, your task is just find out the number of k-edge connected components in G.

Multicases. 3 integer numbers n, m and k are described in the first line of the testcase.(3≤n≤100, 1≤m≤n×(n-1)/2,2≤k≤n)The following m lines each line has 2 numbers u, v describe the edges of graph G.(1≤u,v≤n,u≠v)

A single line containing the answer to the problem.