All Tracks Algorithms Graphs Strongly Connected Components Problem

Monk And His Unique Trip

Graph, Graph Theory, Medium, Tree


Monk plans to visit Graphland. There are N cities and M one-way roads in Graphland. These cities are divided into various states. Cities of Graphland are partitioned into states in a unique way. For any two cities A and B, if it is possible to go from A to B and then return to A, they belong to the same state.

Graphland has inter state tax rule applicable. While passing through road between two cities belonging to different states, Monk has to pay a road tax of 1 dollar. For traveling on roads connecting cities in the same state, he will not be charged any tax. It is ensured that there is no road from any city to itself. It is also ensured that there will not be more than one one-way road from a city to another. Monk, being a foreigner to Graphland, is not aware of this tax rule. He just picks a source city and a destination city and he will travel between these two cities. Monk ensures that it is possible to reach the destination city from source using these one-way roads.

Monk can pick any two cities as source and destination respectively where it is ensured that destination is reachable from source using the roads. But he can take any of the possible paths for reaching the destination. Can you tell him the minimum amount of money he needs to bring so that he faces no issue in traveling no matter on whichever path he travels.

Input Format:

The first line contains two space-separated integers N and M denoting the number of cities in Graphland and number of one-way roads in Graphland respectively.

The next M lines contain two space separated integers \(U_i\) and \(V_i\) which denotes that there is a one way road from \(U_i\) to \(V_i\).

Output Format:

Output a single integer denoting the minimum money he needs to bring for traveling in Graphland.


  • \( 2 \le N \le 10^5 \)

  • \( 1 \le M \le min(2 * 10^5, N*(N-1)) \)

  • \( U_i \ne V_i \)

4 4
1 2
2 3
3 1
1 4

In the sample test case, cities 1, 2 and 3 belongs to the same state and city 4 belongs to another. So if he chooses either 1, 2 or 3 as the source and 4 as the destination, he needs to pay 1 dollar for the travel.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 512 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...
Your Rating:


This Problem was Asked in


Challenge Name

CodeMonk (CheckPoint III)

View All Notifications