(Please provide solutions in Python, thanks !)

Battle of States

Unfortunately, after the deadly invasion of the Night Kings army, all the cities of Westeros are now occupied by white walkers!

Jon Snow has formed a small council and they have prepared a map of cities and the roads between them. These roads are cursed by the night king to work only in one direction, so if anyone moves in opposite direction, they will turn into zombies! The council has divided the cities into some number of states in the following way:

For any two cities X and Y , we say X and Y belong to the same state if and only if there is a safe way to go from X to Y (without turning into zombies) and also there is a safe way to go from Y to X.

Jon Snow and his allies want to fight and kill those creatures! They know that for each state, they need 1 dragonglass dagger in order to be able to clear up that state completely! They will start their journey from a random city and will follow the roads in order to kill all white walkers in the state which that city belongs to. They then must move to a city in a nearby state, or if its not possible (there is no way to go to a nearby state) they will end their journey. Note that a dragonglass dagger used in one state cannot be used in another state.

If Jon Snows army runs out of dragonglass daggers before ending their journey, then they will be killed by the army of dead. Whats the minimum number of daggers they should take with themselves in order to be sure that they wont be killed in this journey, no matter what city from which they start their journey?

Input Format

The first line of input will contain an integer N which indicates the number of cities (assume the cities are labeled from 1 to N ). Each of the following lines will contain two space delimited integers like n_i n_j which represents a safe 1-directional road from n_i to n_j and you have n_i n_j

Constraints

number of cities are less than 100.

Output Format

An integer which indicates the minimum number of daggers that jon snow should take in order to be sure he will not run out of daggers during his journey.

Sample Input 0

9 1 2 2 3 3 1 3 4 3 7 4 6 6 5 5 4 7 8 8 9 9 7 

Sample Output 0

2 

Explanation 0

If you draw the map of cities, you see they form 3 states, if Jon Snow starts from the state which contains cities {1,2,3}, then he needs two daggers to finish his journey.

(The reason that only 2 daggers would be required would be because if we construct the graph of the sample input , 3 strongly connected components (states) are formed, and at max only 2 states can be visited from the above input.

For example, using the above sample input, there are 9 cities & we get the following states: A = {1,2,3}, B = {4,5,6} and C = {7,8,9}

As a result, we can either go from A to C or A to B. Irrespective of which state we start from, we cannot go from B to C or vice versa since there is no path. Hence, we hit the condition "no further route to reach another state" and finish our journey by visiting at most 2 out of the 3 states. Hence the answer is that 2 dragonglass would be required.

(Please provide solutions in Python, thanks!)