题目描述

译自 ROIR 2017 Day1 T3. Размещение данных

一家大型 IT 公司的电信网络包含 $n$ 台服务器，编号从 $1$ 到 $n$。某些服务器对之间通过双向通信通道相连，网络中总共有 $m$ 个通道。保证服务器网络的结构使得数据可以通过通信通道从任意一台服务器传输到任意另一台服务器，可能需要通过一个或多个中间服务器。

服务器集合 A 被称为故障容错的，如果在任意一条通信通道不可用的情况下，满足以下条件：对于任何不在该集合中的服务器 X，存在一种方式通过剩余的通道将数据从集合 A 中的至少一台服务器传输到服务器 X。

下图中展示了一个网络示例以及由编号为 $1$ 和 $4$ 的服务器组成的故障容错集合。数据传输到服务器 $2$ 的方式如下：当服务器 $1$ 和 $2$ 之间的通道不可用时，可以从服务器 $4$ 传输；当服务器 $2$ 和 $3$ 之间的通道不可用时，可以从服务器 $1$ 传输。对于服务器 $3$ 和 $5$，无论哪条通道不可用，都可以通过其他通道从服务器 $4$ 传输数据。

为了提高数据的可用性和对故障的容错能力，公司的一个开发团队需要在网络中放置数据。为此，他们希望将数据同时复制到多台服务器上，形成一个故障容错集合。为了最小化成本，需要选择包含最少服务器数量的故障容错集合。此外，为了了解网络的灵活性，需要计算选择此类集合的方式数量，由于该数量可能很大，需要计算该数量除以 $10^{9}+7$ 的余数。

你的任务是编写一个程序，根据给定的网络描述确定以下两个数字：$k$ - 故障容错集合中的最小服务器数量，$c$ - 选择包含 $k$ 台服务器的故障容错集合的方式数量对 $10^{9}+7$ 取模的结果。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 200000, 1 \leq m \leq 200000)$，分别表示服务器数量和通信通道数量。

接下来的 $m$ 行，每行包含两个整数，描述服务器之间的通信通道。每个通道由两个整数表示，即它所连接的服务器编号。

保证任意两台服务器之间最多直接连接一条通道，没有通道连接服务器自身，并且任意一对服务器之间存在数据传输路径（可能通过一个或多个中间服务器）。

输出格式

输出两个整数，用空格分隔：$k$ 表示故障容错集合中的最小服务器数量，$c$ 表示选择包含 $k$ 台服务器的故障容错集合的方式数量对 $10^{9}+7$ 取模的结果。

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

2 3

在给出的样例中，故障容错的包含两台服务器的集合有：$\{1, 3\}, \{1, 4\}, \{1, 5\}$。

数据范围与提示

详细子任务附加限制及分值如下表所示：