농지

어떤 나라의 농지 지도가 주어진다. 나라 전체의 농지는 서로 겹치지 않는 여러 개의 농지 구역으로 나뉘어 있으며, 각 농부는 정확히 하나의 농지 구역을 소유한다. 이웃한 두 농지 구역 사이에는 경계 울타리가 있다. 이 농지 지도는 평면 그래프 $G(V, E)$ 로 나타낼 수 있다.

간선에는 두 종류가 있다. 이웃한 두 농지 구역을 나누는 경계 간선(boundary edge) 과, 어떤 구역의 내부로 뻗어 있는 비경계 간선(non-boundary edge) 이다.

정상 농지 구역(proper farming region) 이란, 하나의 단순 사이클(simple cycle)로 둘러싸인 닫힌 영역으로서 그 내부에 어떤 정점이나 간선도 포함하지 않는 영역을 말한다. 예를 들어 어떤 사각형의 내부에 다른 정점이 들어 있다면, 그 사각형은 정상 농지 구역이 아니다. 또한 경계 사이클이 단순하지 않은(같은 정점이나 간선을 두 번 지나는) 영역도 정상 농지 구역이 아니다. 넓이가 없는 퇴화된 영역(예: 두 정점만으로 이루어진 영역)도 정상 농지 구역이 아니다.

농지 그래프 $G(V, E)$ 에 대해 다음을 가정한다.

• 그래프는 단순(simple)하고 연결(connected)되어 있다. 즉 자기 자신을 잇는 간선(self-loop)이나, 두 정점을 잇는 여러 개의 평행 간선(parallel edge)은 없다.
• $G(V, E)$ 의 바깥 면(outer face, 무한 영역)은 세지 않는다.
• 정상 농지 구역은 적어도 하나 존재한다.
• 모든 정점의 위치는 서로 다르다.
• 간선끼리 교차하지 않는다. 즉 $G(V, E)$ 는 평면 그래프이다.

정상 농지 구역의 크기(size) 는 그 구역을 둘러싼 경계 간선의 개수로 정의한다. 예를 들어 네 개의 간선으로 둘러싸인 사각형 구역의 크기는 $4$ 이다.

정수 $k$ 가 주어질 때, 크기가 정확히 $k$ 인 정상 농지 구역의 개수를 구하여라. 그런 구역이 없다면 $0$ 을 출력한다.

첫 줄에 테스트 케이스의 수 $M$ 이 주어진다 ($1 \le M < 10$).

이어서 $M$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정점의 개수 $N$ 이 주어진다 ($3 \le N < 200$).

다음 $N$ 개의 줄에는 각 정점의 정보가 다음 형식으로 주어진다.

i xi yi di a1 a2 ... adi

여기서 $i$ 는 정점 번호, $(x_i, y_i)$ 는 정점 $i$ 의 좌표, $d_i$ 는 정점 $i$ 의 차수(degree)이며, 이어지는 $a_1, \dots, a_{d_i}$ 는 정점 $i$ 와 인접한 정점들의 번호이다.

각 테스트 케이스의 마지막 줄에는, 세어야 할 정상 농지 구역의 크기 $k$ 가 주어진다.

모든 정점은 $1000 \times 1000$ 격자의 격자점 위에 놓여 있다.

각 테스트 케이스마다, 크기가 정확히 $k$ 인 정상 농지 구역의 개수를 한 줄에 하나씩 출력한다. 즉 $M$ 개의 음이 아닌 정수를 출력한다.