Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 31 Oct, 2017

Flight connections

Moderate

Problem statement

n number of cities (numbered from 1 to n) are connected by m number of 2-way flights. Connectivity factor of a city is calculated as, the number of cities which are reachable from that city. Two cities i and j are reachable, if you can reach from city i to j via direct or sequence of any number of flights.

Overall connectivity factor is sum of connectivity factors of all cities.

After few years, due to some financial crisis, 2 flights needs to shut down. We need to shut down the flights such that overall connectivity factor is maximized.

Given the details of flights (without any shut down), you need to find and print the updated overall connectivity factor after 2 shut downs, which is maximum.

Note : All pairs of cities don't have to be reachable after shut down of flights.
Input Format :
The first line contains two integers n and m, denoting the number of cities and number of flights. 
Next lines contains two integers Xi  and Yi, meaning that there is a flight between Xi  and Yi, . Also, it is guaranteed that the same edge will not be given twice.
Output Format :
Print a single integer, maximum overall connectivity factor  after 2 shut downs.
Constraints :
 1<=n<=500000
 2<=m<=1000000
 1<=(Xi,Yi)<=n