SOLVE

LATER

Rhezo and Critical Links

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)\)

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

Initializing Code Editor...

{"8fa31c6": "/pagelets/recommended-problems/algorithm/rhezo-and-critical-links-3/", "780d869": "/pagelets/problems-hint/algorithm/rhezo-and-critical-links-3/", "7d9cc50": "/pagelets/problem-author-tester/algorithm/rhezo-and-critical-links-3/", "416752a": "/pagelets/suggested-problems/algorithm/rhezo-and-critical-links-3/", "2e96d9a": "/pagelets/show-submission/algorithm/rhezo-and-critical-links-3/"}

realtime.hackerearth.com

80

ed2b62dfdefda58ae9b536a05017a201f2e9b4a2

58a29e5cae2309f04b28

/realtime/pusher/auth/