Longest Shortest Paths

Time limit5sMemory limit1024 MB

Summary

Given a tree or a graph with exactly one cycle, find the longest shortest path length and how many shortest paths have that length.

Level: Medium7 of 10
Topics: Tree, Graph, DFS, Dynamic programming
Solved: No attempts yet

Problem

Bajtazar learned what a graph is in his computer science class. A graph is a set of $N$ vertices and edges that connect pairs of vertices. A graph is connected if there is a path between any two vertices, which may pass through other vertices. A cycle is a sequence of vertices $v_1, v_2, \cdots, v_k$ such that each pair of consecutive vertices $v_i$ and $v_{i+1}$ is joined by an edge, and so are the first and last vertices $v_1$ and $v_k$ .

While reading web pages, Bajtazar wanted to experiment with two special kinds of graphs: trees and jellyfish.

A graph is a tree if it is connected and has no cycles. A jellyfish is made from a tree by adding exactly one edge between two different vertices that are not yet joined by an edge. So a jellyfish always has exactly one cycle.



Illustrative tree	Illustrative jellyfish

The shortest path between two vertices is the shortest route between them along edges. Formally, it is a sequence of vertices $v_1, v_2, \cdots, v_t$ with all vertices distinct, where each pair of consecutive vertices is joined by an edge. The figure below shows the shortest paths between vertices 1 and 6 in red. In the jellyfish, the shortest path does not go through vertex 4, since such a route would not be the shortest.

Bajtazar wants to know the length of the longest of the shortest paths in his graph, and the number of ways to choose such a path. Two paths are different if they differ in at least one vertex. That vertex does not have to be an endpoint.

Input

The first line contains two natural numbers $N$ ( $1 \le N \le 500000$ ) and $M$ , separated by a single space. They are the number of vertices and the number of edges. $M$ is always equal to $N$ (jellyfish) or $N-1$ (tree).

Each of the following $M$ lines describes one edge with two natural numbers $U_i$ and $V_i$ ( $1 \le U_i, V_i \le N$ , $U_i \ne V_i$ ), the vertices it joins. No edge is repeated.

Output

Print exactly two lines. The first line contains the length of the longest shortest path in the input graph. The second line contains the number of different such paths.

Examples2

Example 1
Input
```
7 6
1 2
2 3
3 4
3 5
5 7
5 6
```
Expected output
```
4
2
```
Example 2
Input
```
7 7
1 2
2 3
2 4
4 3
3 5
5 6
5 7
```
Expected output
```
4
2
```