

kedge connected componentsTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 227 Accepted Submission(s): 155 Problem Description Efficiently computing kedge 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 kedge connected components has many real applications. For example, in social networks, computing kedge connected components can identify the closely related entities to provide useful information for social behavior mining. In a weblink 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 kedge 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 kedge 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_{1} and G_{2}. 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 selfloop or multiple edge, your task is just find out the number of kedge connected components in G. Input Multicases. 3 integer numbers n, m and k are described in the first line of the testcase.(3¡Ün¡Ü100, 1¡Üm¡Ün¡Á(n1)/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) Output A single line containing the answer to the problem. Sample Input
Sample Output
Hint Source  
