권위

말나르 씨는 여러 분야에서 세계적으로 권위를 인정받는 인물이다. 예를 들어 건조 육가공품의 품질, 베란다에서 청양고추를 유기농으로 기르는 방법, 포도 주스 시음 등에서 권위자로 통한다. 이 문제에서는 그가 지금 겪고 있는 고민을 다루며, 항공 산업에서 쌓은 권위로 그 문제를 어떻게 해결하는지 살펴본다.

실은 올해 말나르 씨는 싱가포르행과 모스크바행 비행 일정이 잡혀 있었다. 항공권은 이미 구입했고, 넓은 숙소도 골랐으며, 최고의 웰니스 및 스파 여행지도 알아봤다. 그러나 전염병 위기로 여행이 모두 취소되었다. 크게 낙담하고 걱정한 그는 곧바로 항공 노선과 항공 산업 전반의 상황을 조사했고, 그 과정에서 세상이 더 이상 연결되어 있지 않다는 사실을 알아챘다. "이대로는 안 돼. 당장 세상을 구해야겠어!" 말나르 씨는 이렇게 생각하고 일에 뛰어들었다.

세상에는 $N$개의 공항과 $M$개의 항공 노선이 있다. 공항은 $1$부터 $N$까지의 자연수로 구분하며, 각 항공 노선은 서로 다른 두 공항을 잇는다. 즉 두 공항 사이를 비행기가 양방향으로 오갈 수 있다. 정상적인 상황에서는 하나 이상의 항공 노선을 거쳐 어느 공항에서든 다른 모든 공항으로 갈 수 있었다. 곧 세상은 연결되어 있었다. 말나르 씨는 몇 번의 전화만으로 세상을 다시 연결하려 한다. 각 전화는 어떤 공항에 걸며, 같은 공항에 여러 번 거는 경우도 있다. 대화는 대략 다음과 같이 진행된다.

공항 직원: 안녕하세요! 공항입니다. 무엇을 도와드릴까요?

말나르 씨: 안녕하세요, 말나르입니다. 귀 공항의 항공 노선이 말이 안 된다는 것을 알았습니다. 완전히 반대로 해 주셔야겠어요. 공항 집합 $A$는 귀 공항과 항공 노선으로 직접 연결된 공항들이고, 집합 $B$는 그 밖의 모든 공항이라고 합시다. 귀 공항과 $A$의 공항을 잇는 항공 노선을 모두 없애고, 귀 공항과 $B$의 공항을 잇는 항공 노선을 새로 만들어 주세요. 지금 일이 있어서 가봐야 해요. 제가 말씀드린 대로 처리해 주세요.

공항 직원: 실수해서 죄송합니다. 말씀하신 대로 처리하겠습니다.

여러분의 과제는 말나르 씨가 세상을 다시 연결하려면 최소 몇 번의 전화를 해야 하는지 구하는 것이다. 또한 전화 횟수를 최소로 유지하면서 전화를 거는 방법이 몇 가지인지도 구하라. 방법의 수는 $10^9 + 7$로 나눈 나머지로 출력한다. 충분히 많이 전화하면 말나르 씨가 언제나 세상을 구할 수 있음을 증명할 수 있다.

첫 줄에는 본문에 나온 자연수 $N$과 $M$이 주어진다.

이어지는 $M$개의 줄 중 $i$번째 줄에는 항공 노선이 있음을 뜻하는 두 자연수 $a\_i$와 $b\_i$ ($1 ≤ a\_i , b\_i ≤ N$, $a\_i ≠ b\_i$)가 주어진다. 같은 두 공항을 잇는 항공 노선은 두 개 이상 존재하지 않는다.

첫 줄에 본문에서 구한 최소 전화 횟수를 출력한다.

둘째 줄에 본문에서 구한 방법의 수를 $10^9 + 7$로 나눈 나머지로 출력한다.

첫 번째 예제 설명: 세상은 이미 연결되어 있으므로 말나르 씨는 전화를 한 번도 할 필요가 없다.

두 번째 예제 설명: 세상을 연결 상태로 만드는 가장 짧은 전화 순서는 다음 네 가지뿐이다: $(1, 4)$, $(4, 1)$, $(2, 3)$, $(3, 2)$.