Migrated from Lutece 2612 tarjan

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个 $n$ 个点，$m$ 条边的无向图简单图。求割点数量，割边数量，极大点双连通分量数量，极大点双连通分量包含边数的最大值。

割点：在图中移除这个点后，存在一个点对在原图中连通在新图中不连通。

割边：在图中移除这条边后，存在一个点对在原图中连通在新图中不连通。

点双连通分量：原图的一个点数大于 $1$ 的连通子图，不存在对于这个子图的割点。

极大点双连通分量：是点双连通分量，且任意新增一个点后不是点双连通分量。

Input

第一行两个整数 $n,m$，分别表示图的点数和边数。

接下来 $m$ 行，每行两个整数 $u,v$，表示一条边。

Output

一行四个整数，用空格分割，分别表示割点数量，割边数量，极大点双连通分量数量，极大点双连通分量包含边数的最大值。

Samples

6 6
1 2
2 3
3 4
4 5
5 6
6 1

0 0 1 6

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

2 1 3 3

Constraints

$1\le n\le 1000$ $0\le m\le \frac{n(n-1)}{2}$ $1\le u,v\le n$ 保证无重边，无自环。

Note

如果存在一条边 $u,v$，那么 $\{u,v\}$ 也是一个点双连通分量。

Resources

2021-2023 UESTC ICPC Training for Graph