All Tracks Algorithms Graphs Depth First Search Problem

Rhezo and Critical Links
Tag(s):

DFS, Easy, Graph Theory

Problem
Editorial
Analytics

Rhezo likes to play with graphs having N nodes and M edges. Lonewolf is ready to give him such a graph only on one condition. He wants Rhezo to find the number of critical links in the graph.

A critical link in a graph is an edge that has the following property: If we cut the link/edge, the graph will have exactly one more connected component than it previously had, and the difference between the number of nodes on each side of the edge is less than a certain integer P.

Given P and the graph, can you help Rhezo calculate the number of critical links?

Input:

First line contains 3 integers N, M and P as described in the problem statement. Each of the next M lines contain 2 integers A and B, meaning that node number A has a link/edge with node number B.

Output:

Find the number of critical links in the graph.

Constraints:

\(1 \le N, M, P \le 10^{5} \)

\(1 \le A,B \le N\)

\(1 \le M \le max(10^{5},N \cdot (N-1) / 2)\)

SAMPLE INPUT
5 4 100
1 2
2 3
3 4
4 5
SAMPLE OUTPUT
4
Explanation

Each edge is a critical link.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?