선 그래프

작년에 Rounddog는 꽤 어려운 문제들이 나온 대회에 참가했는데, 선 그래프 문제를 풀지 못했다. 그래서 최근 그는 선 그래프를 더 깊이 공부하기로 했다.

그래프 이론에서 단순 무향 그래프 $G$의 선 그래프 $L(G)$는 $G$에 있는 임의의 두 간선 사이의 인접 관계를 나타내는 또 다른 단순 무향 그래프이다. 정확히 말하면, 자기 루프나 다중 간선이 없는 무향 그래프 $G$에 대해 선 그래프 $L(G)$는 다음 조건을 만족하는 그래프이다.

• $L(G)$의 각 정점은 $G$의 간선 하나를 나타낸다.
• $L(G)$의 두 정점은 대응하는 두 간선이 $G$에서 공통 끝점을 가질 때, 그리고 그때에만 인접한다.

단순 무향 그래프 $G$가 주어지면, Rounddog의 연구 목표는 $L(G)$의 최대 클리크를 찾는 것이다. 그는 이 연구 결과의 일부를 여러분을 위한 문제로 만들었다.

이 문제에서는 단순 무향 그래프 $G$와 작은 양의 정수 $k$가 주어진다. $L_0(G) = G$이고, 각 양의 정수 $s$에 대해 $L_s(G) = L(L_{s-1}(G))$라고 하자. $L_k(G)$의 모든 최대 클리크를 찾은 뒤, $L_k(G)$ 최대 클리크의 정점 수와 서로 다른 최대 클리크의 개수를 1 000 000 007로 나눈 나머지를 Rounddog에게 알려 주어야 한다.

여기서 무향 그래프의 정점 부분집합은, 그 안의 임의의 두 정점 사이에 간선이 있을 때 클리크라고 한다. 최대 클리크는 정점 수가 가능한 한 가장 많은 클리크이다.

입력에는 여러 개의 테스트 케이스가 포함되며, 첫 줄에는 테스트 케이스의 개수 $T$ ($1 \le T \le 1000$)가 하나의 정수로 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$ ($1 \le n \le 100\,000$), $m$ ($0 \le m \le 200\,000$), $k$ ($1 \le k \le 4$)가 주어진다. 이들은 주어진 단순 무향 그래프 $G$의 정점 수와 간선 수, 그리고 선 그래프 연산을 반복하는 횟수이다.

이어서 $m$개의 줄이 주어지며, 그래프의 모든 간선을 나타낸다. 각 줄에는 두 정수 $u$와 $v$ ($1 \le u, v \le n$, $u \ne v$)가 주어지고, 이는 정점 $u$와 $v$ 사이의 간선을 뜻한다.

모든 테스트 케이스에서 $n$의 합은 2 000 000을 넘지 않고, $m$의 합은 3 000 000을 넘지 않는다. 또한 각 테스트 케이스의 그래프에는 자기 루프와 다중 간선이 없다.

각 테스트 케이스에 대해, 최대 클리크의 정점 수와 서로 다른 최대 클리크의 개수를 1 000 000 007로 나눈 나머지를 공백으로 구분하여 한 줄에 출력한다.