8.5 Megacity

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.

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.

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

\(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.

\(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.

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.

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.

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.

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.