가장 긴 최단 경로

바이타자르는 정보 수업에서 그래프를 배웠다. 그래프는 $N$개의 정점과, 정점들을 잇는 간선의 집합이다. 그래프가 연결되어 있다는 것은 임의의 두 정점 사이에 연결이 존재한다는 뜻이며, 그 연결은 다른 정점을 거쳐도 된다. 사이클은 정점들의 수열 $v_1, v_2, \cdots, v_k$로서, 인접한 두 정점 $v_i$와 $v_{i+1}$ 사이, 그리고 첫 정점 $v_1$과 마지막 정점 $v_k$ 사이에 간선이 있는 것을 말한다.

인터넷을 둘러보던 바이타자르는 트리와 해파리라는 특수한 그래프를 직접 실험해 보고 싶어 했다.

그래프가 트리라는 것은 연결되어 있고 사이클이 없다는 뜻이다. 해파리는 트리에 간선을 정확히 하나 추가해서 만든다. 이때 추가하는 간선은 아직 간선으로 연결되어 있지 않은 서로 다른 두 정점을 잇는다. 따라서 해파리는 사이클을 정확히 하나 가진다.

예시 트리	예시 해파리

두 정점 사이의 최단 경로는 두 정점을 잇는 경로 중 가장 짧은 것이다. 형식적으로는 서로 다른 정점들의 수열 $v_1, v_2, \cdots, v_t$로서, 인접한 두 정점이 간선으로 연결되어 있는 것이다. 아래 그림은 정점 1과 6 사이의 최단 경로를 빨간색으로 표시한 것이다. 해파리에서는 정점 4를 지나는 경로가 가장 짧을 수 없으므로 최단 경로가 정점 4를 지나지 않는다.

바이타자르는 그래프의 최단 경로들 중 가장 긴 것의 길이와, 그러한 최단 경로의 개수를 알고 싶어 한다. 두 경로는 적어도 한 정점이 다르면 서로 다른 경로로 센다. 다른 정점이 끝점일 필요는 없다.

첫 줄에는 공백으로 구분된 자연수 $N$ ($1 \le N \le 500000$)과 $M$이 주어진다. 각각 정점의 수와 간선의 수이다. $M$은 항상 $N$(해파리) 또는 $N-1$(트리)과 같다.

이어지는 $M$개의 줄에는 각각 간선 하나가 주어진다. $i$번째 줄에는 간선으로 연결된 두 정점의 번호 $U_i$, $V_i$ ($1 \le U_i, V_i \le N$, $U_i \ne V_i$)가 주어진다. 같은 간선이 두 번 나오지 않는다.

정확히 두 줄을 출력한다. 첫째 줄에는 입력 그래프에서 가장 긴 최단 경로의 길이를, 둘째 줄에는 그러한 최단 경로의 서로 다른 개수를 출력한다.