All Tracks Algorithms Graphs Articulation Points and Bridges Problem

Sherlock and Highways
Tag(s):

Medium-Hard

Problem
Editorial
Analytics

Sherlock wanted to have some fun and decided to visit Paris. An elderly man whom he met there wanted Sherlock to solve his problem and so he began -
For a graph G, the roads, which on deletion do not disconnect the graph are compressed into a node and the roads which on deletion disconnect the graph form an edge between these nodes. The resultant structure will be a tree of course! You have to help Sherlock by printing the number of edges and diameter of this tree.

Input Format
First line contains $$N$$ and $$M$$, the number of nodes and edges respectively.
Next M lines contain two space separated integers $$u$$ and $$v$$, denoting there is an edge between these two nodes.

Constraints

  • $$1 \le N \le 10^5$$
  • $$1 \le M \le 2*10^5$$
  • Input graph is connected.
  • No multiple edges and self loops are present.

Output Format
Print two space separated integers denoting the number of edges in the tree formed and diameter of the tree.

SAMPLE INPUT
4 3
1 2
1 3
2 4
SAMPLE OUTPUT
3 3
Time Limit: 1.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

School of Engineering, CUSAT

Challenge Name

221B Baker Street: Code for Watson

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications