그래프 세기

베시는 \(1\ldots N\)으로 번호가 붙은 정점 \(N\)개와 간선 \(M\)개를 가진 연결된 무방향 그래프 \(G\)를 가지고 있다 (\(2\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}\)). \(G\)에는 자기 루프(정점에서 자기 자신으로 가는 간선)는 있을 수 있지만, 평행 간선(같은 두 끝점을 잇는 여러 간선)은 없다.

\(f_G(a,b)\)를, 각 \(1\le a\le N\)과 \(0\le b\)에 대해 정점 \(1\)에서 정점 \(a\)까지 정확히 \(b\)개의 간선을 지나는 경로가 존재하면 참, 그렇지 않으면 거짓으로 평가되는 불리언 함수라고 하자. 한 간선을 여러 번 지나면 그 횟수만큼 개수에 포함된다.

엘시는 베시를 따라 하고 싶어 한다. 구체적으로, 엘시는 모든 \(a\)와 \(b\)에 대해 \(f_{G'}(a,b)=f_G(a,b)\)가 성립하는 무방향 그래프 \(G'\)를 만들고 싶어 한다.

여러분의 임무는 엘시가 만들 수 있는 서로 다른 그래프 \(G'\)의 개수를 \(10^9+7\)로 나눈 나머지를 세는 것이다. \(G\)와 마찬가지로 \(G'\)에도 자기 루프는 있을 수 있지만 평행 간선은 없다 (즉, \(N\)개의 번호 붙은 정점 위의 서로 다른 그래프는 총 \(2^{\frac{N^2+N}{2}}\)개이다).

각 입력에는 독립적으로 해결해야 하는 \(T\)개(\(1\le T\le \frac{10^5}{4}\))의 테스트 케이스가 포함되어 있다. 모든 테스트 케이스에 대한 \(N^2\)의 합은 \(10^5\)를 넘지 않음이 보장된다.

문제 제공: Benjamin Qi

채점 방식

• 입력 3의 모든 테스트 케이스는 \(N\le 5\)를 만족한다.
• 입력 4-5의 모든 테스트 케이스는 \(M=N-1\)을 만족한다.
• 입력 6-11의 모든 테스트 케이스에서는, 모든 \(b\)에 대해 \(f_G(x,b)=f_G(y,b)\)가 성립하는 경우가 아니라면, \(f_G(x,b)\)는 참이고 \(f_G(y,b)\)는 거짓이 되는 \(b\)가 존재한다.
• 입력 12-20의 테스트 케이스는 추가 제약이 없다.

문제 제공: Benjamin Qi

입력의 첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.

각 테스트 케이스의 첫째 줄에 정수 \(N\)과 \(M\)이 주어진다.

각 테스트 케이스의 다음 \(M\)개의 줄에는 각각 두 정수 \(x\)와 \(y\) (\(1\le x\le y\le N\))가 주어지는데, 이는 \(G\)에서 \(x\)와 \(y\) 사이에 간선이 존재함을 나타낸다.

가독성을 위해 연속된 테스트 케이스는 빈 줄로 구분된다.

각 테스트 케이스마다 서로 다른 \(G'\)의 개수를 \(10^9+7\)로 나눈 나머지를 한 줄에 하나씩 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > February > Platinum