데이터 배치

대형 IT 기업의 통신망에는 1번부터 n번까지 번호가 붙은 n개의 서버가 있다. 일부 서버 쌍은 양방향 통신 채널로 연결되어 있으며, 망에 있는 채널은 모두 m개다. 통신 채널을 이용하면 하나 이상의 중간 서버를 거쳐서라도 어떤 서버에서 다른 어떤 서버로든 데이터를 전송할 수 있음이 보장된다.

서버 집합 A가 결함 감내 집합이라는 것은, 어떤 통신 채널 하나를 사용할 수 없게 되어도 다음 조건이 성립한다는 뜻이다. 이 집합에 속하지 않는 임의의 서버 X에 대해, 남은 채널만으로 집합 A의 서버 중 적어도 하나에서 서버 X로 데이터를 전송할 수 있는 방법이 존재한다.

그림 1은 망의 예와 1번, 4번 서버로 이루어진 결함 감내 집합을 보여준다. 서버 2로 데이터를 전송하는 방법은 다음과 같다. 서버 1과 2 사이의 채널을 사용할 수 없으면 서버 4에서 전송하고, 서버 2와 3 사이의 채널을 사용할 수 없으면 서버 1에서 전송한다. 서버 3과 5로는 어떤 통신 채널 하나를 사용할 수 없게 되어도 다른 채널을 통해 서버 4에서 데이터를 전송할 수 있다.

그림 1. 망의 예와 결함 감내 서버 집합.

회사 개발팀은 프로젝트를 진행하며 망에 자신들의 데이터를 배치하려고 한다. 데이터 가용성을 높이고 장애에 대비하기 위해 개발팀은 결함 감내 집합을 이루는 여러 서버에 데이터를 동시에 두어 복제하려고 한다. 비용을 최소화하려면 서버 수가 최소인 결함 감내 집합을 골라야 한다. 또한 망이 얼마나 유연하게 구성되었는지 알아보기 위해 그러한 집합을 고르는 방법의 수를 세어야 하며, 이 수가 클 수 있으므로 109 + 7로 나눈 나머지를 구해야 한다.

주어진 망의 설명을 보고 다음 값을 구하는 프로그램을 작성하라. k는 결함 감내 서버 집합에 속하는 서버 수의 최솟값, c는 k개 서버로 이루어진 결함 감내 집합을 고르는 방법의 수를 109 + 7로 나눈 나머지다.

첫째 줄에 서버 수와 통신 채널 수를 나타내는 정수 n과 m이 주어진다 (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).

다음 m개 줄에는 정수 두 개가 주어지며 통신 채널을 나타낸다. 각 통신 채널은 그 채널이 연결하는 서버 두 대의 번호로 주어진다.

어떤 두 서버도 통신 채널로 두 번 이상 직접 연결되지 않고, 어떤 채널도 서버를 자기 자신과 연결하지 않으며, 임의의 서버 쌍에 대해 하나 이상의 중간 서버를 거쳐서라도 한쪽에서 다른 쪽으로 데이터를 전송할 수 있는 방법이 존재함이 보장된다.

k와 c를 공백으로 구분해 출력하라. k는 결함 감내 서버 집합에 속하는 서버 수의 최솟값, c는 k개 서버로 이루어진 결함 감내 집합을 고르는 방법의 수를 109 + 7로 나눈 나머지다.

예제에서 두 서버로 이루어진 결함 감내 집합은 {1, 3}, {1, 4}, {1, 5}이다.