该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

A component of an undirected graph $G$ is a maximum connected sub-graph of $G$. A linear component is a component that has a linear structure property-- that is, each vertex in that component has exactly one previous vertex (except the first one), and one next vertex (except the last one). The size of a linear component is the number of edges in the component.

Now given an undirected graph, you are supposed to find the largest size of its linear components.

输入格式

Each input file contains one test case, which first gives 2 positive integers: $n$ ($\le 10^4$), the number of vertices, and $m$ ($\le 5n$), the number of edges.

Then $m$ lines follow, each describes an edge in the form u v, where u and v are the indices of the two ends of the edge. The vertices are indexed from 1 to $n$. It is guaranteed that no duplicated edges are given.

输出格式

For each case, print in a line the number and the largest size of the linear components. The numbers must be separated by a space. If there is no linear component, the maximum size is defined to be $-1$.

样例

14 11
1 2
2 3
3 1
4 5
6 5
6 7
8 7
9 10
11 12
11 13
11 14

2 4

4 4
1 2
2 3
3 4
4 2

0 -1

限制

对于所有的测试用例,限制为400 ms, 64 MB