# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Kanhaiya Mohan

Tester: Felipe Mota, Aryan

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2676

# PREREQUISITES:

Graphs

# PROBLEM:

The country of Chefland is a group of N cities having M directed roads between its cities. It takes 1 second to travel on any road.

Chef has decided to travel through this country. His travel plan goes as follows -

- He will randomly choose a starting city.
- While there are outgoing roads in his current city, he will randomly choose one of them and travel it. He can choose roads he has already traveled through and visit cities multiple times.
- He will stop if there are no outgoing roads in the current city or N seconds have passed.

Chef will be disappointed if after traveling he does not end up in the capital city.

The ministers have not yet decided upon the capital city. They would like to choose it in such a way that Chef is not disappointed by his trip. To make their decision a bit easier, they can build some new roads between cities.

Find the **minimum** number of roads that need to be built such that the ministers can choose a capital city that doesnâ€™t disappoint Chef no matter where his trip starts or how it progresses.

It is possible that the current road system is such that no matter which roads are added, a capital that doesnâ€™t disappoint Chef cannot be chosen. In this case, print -1 instead.

# QUICK EXPLANATION:

Observation \;1: The candidates that can be a capital city cannot have any outgoing edges.

Observation \;2: If the graph contains any cycle, then there cannot be a capital city.

Claim For any k candidates for capital cities, the number of edges that needs to be added to make a unique capital is (k-1)

Thus we would first check for cycles in the graph and if no cycle is present in the graph, then we would count the number of vertices having no outgoing edges and answer would be one less than that.

# TIME COMPLEXITY:

O(V + E) for each test case.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester-1â€™s Solution

Tester-2â€™s Solution