All Tracks Algorithms Graphs Depth First Search Problem

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.

enter image description here

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, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications