8.5 Megacity
(RankList for this Question)
Score: 100pts
Time Limit: 1.00 sec
You are given \(n\) cities and \(m\) one way roads from city \(u\) to \(v\). Let’s call a group of cities as Megacity iff all the cities within that Megacity are reachable from all the other cities within the same Megacity. Formally, Megacities are strongly connected components of a directed graph.
Pingu wants to move to a new city and wants to select a city which satisfies the following conditions -
The city is a part of a Megacity.
This Megacity is the biggest among all the Megacities.
A ‘Megacity’ is called the biggest, if there are no megacities which have more cities than the biggest ‘Megacity’.

You need to output the cities of the Megacity that satisfy Pingu’s conditions in alphabetical order. If there are multiple Megacities that satisfy the conditions, output cities of all such Megacities. Incase you the question isn’t clear, kindly go through the sample cases.

Constraints
\(2 \leq n \leq 20\)
\(1 \leq m \leq 380\)
Strings \(u\) and \(v\) contain Latin characters.

Input Format
\(n\) \(m\)
\(u_1\) \(v_1\)
\(u_2\) \(v_2\)
.
.
.
\(u_m\) \(v_m\)

Output Format
\(x\)
\(w_1\) \(w_2\) . . . \(w_x\)

Here, \(x\) is the number of cities that satisfy the condition. In the new line, output names of the cities separated by spaces.

Example 1
Input:
10 12
Seahawktra Linesouth
Linesouth Saphis
Saphis Parkbriley
Parkbriley Seahawktra
Saphis Slandste
Slandste Tainsling
Tainsling Wathcoa
Wathcoa Slandste
Montlouis Tainsling
Montlouis Marpidscky
Marpidscky Montlouis
Marpidscky Santagrove

Output:
4
Linesouth Parkbriley Saphis Seahawktra

Explanation:
\(\href{https://www.dropbox.com/s/6j2oqnxocta5ria/8-1.png?dl=0}{\text{Click here to view the graph}} \)
Here, there are 4 Megacities as marked in the diagram. Now the biggest of them is the first one containing 4 cities. So we output the corresponding names of the 4 cities.

Example 2
Input:
6 7
Seahawktra Saphis
Saphis Parkbriley
Parkbriley Linesouth
Linesouth Saphis
Linesouth Seahawktra
Linesouth Slandste
Slandste Tainsling

Output:
4
Linesouth Parkbriley Saphis Seahawktra

Explanation:
\(\href{https://www.dropbox.com/s/esj7wb0xahrwqwq/8-2.png?dl=0}{\text{Click here to view the graph}} \)

Here, there are 3 Megacities - 1 of size 4 and rest of size 1 each. Thus, the biggest one of them is 4, so we output the corresponding names in alphabetical order.

Example 3
Input:
6 5
Seahawktra Linesouth
Seahawktra Saphis
Seahawktra Tainsling
Seahawktra Slandste
Seahawktra Parkbriley

Output:
6
Linesouth Parkbriley Saphis Seahawktra Slandste Tainsling

Explanation:
\(\href{https://www.dropbox.com/s/sn7f9r1yv582q4y/8-3.png?dl=0}{\text{Click here to view the graph}} \)

Here, there are 5 Megacities - all of size 1. Thus all Megacities’ cities satisfy the condition so we output all the cities in alphabetical order.

Example 4
Input:
9 10
Linesouth Seahawktra
Linesouth Saphis
Saphis Parkbriley
Parkbriley Slandste
Slandste Linesouth
Parkbriley Tainsling
Tainsling Wathcoa
Wathcoa Montlouis
Montlouis Marpidscky
Marpidscky Tainsling

Output:
8
Linesouth Marpidscky Montlouis Parkbriley Saphis Slandste Tainsling Wathcoa

Explanation:
\(\href{https://www.dropbox.com/s/zkfqrnfe1dxiwlf/8-4.png?dl=0}{\text{Click here to view the graph}} \)

Here, there are 3 Megacities - 2 of size 4 and 1 of size 1. So, the biggest one is one with size 4. So we output all the cities in both the Megacities with size 4.

Log In to solve the Question