그래프 카드

시간 제한30초메모리 제한1024 MB

요약

주어진 연결 그래프 카드들 가운데 서로 동형이 아닌 그래프의 개수를 셉니다. 각 카드는 간선 목록으로 주어지며 간선 수가 정점 수와 같습니다.

난이도: 보통10점 중 7점
유형: 그래프, 트리, 문자열, 해시맵
정답자: 아직 제출이 없습니다

문제

카드 묶음이 탁자 위에 놓여 있다. 각 그래프 카드 $\chi$ 에는 무방향 단순 그래프 $G_\chi$ 가 붙어 있다. 각 $G_\chi$ 는 연결 그래프이며, 정점 수와 간선 수가 같다. 카드마다 정점 수가 다를 수 있다.

두 카드에 붙은 그래프 $G_1 = (V_1, E_1)$ 과 $G_2 = (V_2, E_2)$ 가 동형이면 두 카드는 같다고 본다. 즉, $V_1$ 에서 $V_2$ 로 가는 전단사 함수 $f$ 가 존재해서, $V_1$ 의 모든 $x, y$ 에 대해 $(x, y) \in E_1$ 일 때에만 $(f(x), f(y)) \in E_2$ 가 성립한다. 덱에 들어 있는 서로 다른 그래프 카드의 개수를 구하는 것이 목표다.

입력

첫 줄에 테스트 케이스의 수 $t$ 가 주어진다. 각 테스트 케이스는 카드 수 $n > 0$ 을 적은 줄로 시작하고, 이어서 $n$ 개의 줄이 주어진다. 각 줄은 그래프 카드 하나를 나타내며 다음 형식이다.

k u1 v1 u2 v2 ... uk vk

여기서 $k > 0$ 은 정점 수이자 간선 수다. 각 $i \in [1, k]$ 에 대해 $(u_i, v_i)$ 가 간선이다. 정점 번호는 $[1, k]$ 범위의 정수다.

출력

각 테스트 케이스마다 덱에 들어 있는 서로 다른 그래프 카드의 개수를 한 줄에 출력한다.

제한

$0 < t \le 30$
$0 < n, k \le 10^6$
각 테스트 케이스에서 $n$ 개 카드의 정점 수 합은 $10^6$ 이하다.

예제2

예제 1

입력

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

예상 출력

예제 2

입력

2
2
4 1 2 2 3 3 1 1 4
5 1 2 2 3 3 1 2 4 2 5
3
9 1 2 2 5 5 7 7 6 6 3 3 1 2 4 7 9 9 8
9 1 4 4 2 2 3 3 5 5 7 7 6 6 4 7 8 8 9
9 1 2 2 5 5 4 4 1 4 7 7 8 8 6 8 9 5 3

예상 출력

2
2