Little Boruto And Rail Ways
Tag(s):

## BFS, DFS, Medium-Hard, Trees

Problem
Editorial
Analytics

As a present for becoming a Genin, Naruto bought for his son a Lego Train. The little child quickly became addict to the game. He usually spends a lot of time playing with them outside mission times; no wonder why he is good at creating complicated Train Structures.

A Train Structure in Lego is a set of Lego train stations with some Lego roads connecting them. Lego Roads are undirected, that is if you can travel from $station_u$ to $station_v$ and the reverse holds too.

After Finishing a structure, Little Boruto tries to improve its design. To do so, he first calculates the $designScore$ of his creation. According to him, the $designScore$ of a structure is the number of train stations from where you can start and return back to using at least $2$ Lego roads that are all pairwise different. Then, he will add exactly one Lego road to his structure and re- calculate the $designScore$ and records it. Among all possible choices he has made, he chooses the one which yields the maximum score.

This task is very demanding and Little Boruto never had the chance of trying all possible combinations before bed time. That’s why, he would like you to help him improving the design of his next creations.

Input Format:

First line contains two integers $n$ and $m$; the number of train stations and the numbers of roads, respectively. Each of the next $m$ lines contain a pair of integers $(u, v)$, meaning that there is a road connecting $station_u$ to $station_v$.

Output:

Print a single integer denoting the answer to the problem.

Constraints:

• $1 \le n \le 10^5$
• $1 \le m \le 2 \times 10^5$
• Self loops and multiple edges are not allowed
• There is at least one path from all pairs of train stations
SAMPLE INPUT
3 2
1 2
2 3
SAMPLE OUTPUT
3

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming