Malnar 先生在很多方面都被公认为权威。例如，他是冷切肉制品质量、阳台辣椒生态种植、葡萄汁品鉴等方面的权威。在本题中，我们将探讨他目前面临的一个问题，并研究 Malnar 先生如何利用他在航空业无可置疑的权威来解决他的问题。

今年，Malnar 先生原定前往新加坡和莫斯科。他已经预订了机票，选择了宽敞的住宿，并研究了最好的健康与水疗目的地。不幸的是，由于疫情危机，旅行被取消了。他感到非常沮丧和担忧，立即开始研究航班时刻表和航空业的总体状况，并注意到世界不再是连通的了。“这怎么行，我必须立即拯救世界！”Malnar 先生心想，并开始着手工作。

世界上有 $N$ 个机场和 $M$ 条航线。机场用 $1$ 到 $N$ 的自然数编号，每条航线连接两个不同的机场，这意味着飞机可以在这两个机场之间双向飞行。在正常情况下，可以通过一条或多条航线从任何机场到达任何其他机场，也就是说，世界是连通的。Malnar 先生将通过几次电话重新连接世界。每个电话都将打给某个机场，有些电话可能会多次打给同一个机场，电话内容大致如下：

机场代表：您好！这里是机场，有什么可以帮您？

Malnar 先生：您好，我是 Malnar。我注意到你们的航线毫无意义，你们需要做完全相反的事情。也就是说，设集合 $A$ 包含与你们直接相连的机场，集合 $B$ 包含所有其他机场。我希望你们取消连接你们机场和集合 $A$ 中机场的所有航线，并引入连接你们机场和集合 $B$ 中机场的航线。我现在有事要忙，必须走了，请按我说的去做。

机场代表：很抱歉我们的疏忽，我们会按照您的要求去做。

你的任务是确定 Malnar 先生为了重新连接世界必须拨打的最少电话次数。此外，确定在保持电话次数最少的情况下，他有多少种不同的拨打方式。请将方案数对 $10^9 + 7$ 取模后输出。可以证明，只要拨打足够多的电话，Malnar 先生总是能拯救世界。

输入格式

第一行包含题目描述中的自然数 $N$ 和 $M$。

在接下来的 $M$ 行中，第 $i$ 行包含两个自然数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le N, a_i \neq b_i$)，表示机场 $a_i$ 和 $b_i$ 之间存在一条航线。不存在连接同一对机场的两条航线。

输出格式

第一行输出题目要求的最小电话次数。

第二行输出题目要求的方案数，对 $10^9 + 7$ 取模。

子任务

如果你的程序在某个测试点上输出了正确的最小次数，但输出了错误的方案数（或者没有输出），你将获得该测试点分数的 $15\%。

一个子任务的得分等于你的程序在该子任务的任一测试点上获得的最低分数。

样例

输入 1

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

输出 1

0
1

输入 2

4 2
1 4
2 3

输出 2

2
4

输入 3

8 9
1 4
2 3
6 7
8 5
2 4
7 8
5 6
6 8
4 3

输出 3

1
5

说明

第一个样例的说明：世界已经是连通的，因此 Malnar 先生不需要拨打任何电话。

第二个样例的说明：以下是使世界连通的最短电话序列：$(1, 4), (4, 1), (2, 3), (3, 2)$。