描述

我们有一个国家的农田地图。这个国家的全部农田被划分成了一组互不相交的农田区域。在这个国家里，每个农民仅拥有一个农田区域。两个相邻的农田区域之间有一道边界围栏。这个国家的农田地图可以用一个平面图来表示。下面的图 1 展示了一个例子。

图 1：农田图 G (V,E)

存在两种类型的边，边界边和非边界边。图 G (V,E) 中除了边 $(v8, v6)$ 和 $(v11, v10)$ 之外的所有边都是边界边，这些边界边位于两个相邻的农田区域之间。在农田图中，“合适的农田区域” 是一个由简单环界定的封闭区域，并且其内部不应包含任何顶点或边。在这张图中，多边形 $< v1,v9,v8,v7 >$ 是一个合适的农田区域，而区域 $< v2, v1, v7, v8 , v2, v5, v4, v3 >$ 不是一个合适的农田区域，因为它的边界环不是简单的。 我们假设农田图 G (V,E) 是一个简单连通图，即不允许有自环（图 2 (a)）和平行边（图 2 (b)）。此外，在农田图 G (V,E) 中，我们不考虑 G (V,E) 的外部面。你可以看到，在图 1 所示的 G (V,E) 中有 2 个合适的农田区域，即 $< v1,v9,v8,v7 >$ 和 $< v2,v3,v4,v5>$，因为它们内部没有顶点或边。但是多边形 $< v1,v7,v8,v2 >$ 不是一个合适的农田区域，因为顶点 v3、v4 和 v5 位于该区域内。同样地，某个区域不是合适的区域，因为顶点 v10 在该区域内部。退化多边形 $< v6, v8 >$ 不是一个合适的区域，因为它内部没有有效的面积。

图 2：(a) 自环 $< v1,v1>$ ，以及 (b) 3 条平行边 $\{ < v1,v2>,< v1,v2>, < v1,v2>\}$

对于输入的农田图数据还有其他一些假设条件： 至少存在一个合适的农田区域。 农田图中每个顶点的位置都是不同的。 不存在边交叉的情况，这意味着图 G (V,E) 是一个平面图。 农田图 G (V,E) 是简单且连通的。 让我们来定义 “合适的农田区域” 的 “大小”。合适的农田区域的大小是该区域边界边的数量。例如，合适的农田区域 $< v2,v3,v4,v5 >$ 的大小是 4。 问题是要找出具有指定大小的合适区域的数量。如果你被要求找出图 1 所示的图中大小为 4 的合适区域的数量，你必须回答有 2 个大小为 4 的合适区域，因为农田区域 $<v1,v9,v8,v7>$ 和 $< v2,v3,v4,v5 >$ 是合适区域，且它们的大小都是 4。如果不存在这样的区域，那么你必须输出 0。

输入

输入由 $M$ 个测试用例组成。输入的第一行包含一个正整数 $M$，即你要解决的测试用例的数量。在第一行之后，接着是 $M$ 个测试用例的输入数据。每个测试用例的第一行包含一个正整数 $N$（>=3），即顶点的数量。接下来的 $N$ 行每行的格式如下： $i x_i y_i d_i a_1 a_2 a_3 ..... a_{d_i}$ “$i$” 是顶点编号，$x_i$ 和 $y_i$ 是顶点 $i$ 的坐标 $(x_i, y_i)$，$d_i$ 是顶点 $i$ 的度数。接下来的 $\{ a_i \}$ 是顶点 $i$ 的相邻顶点。最后一行给出 $k$，即你必须统计的合适区域的大小。 注意，输入中的测试用例数量 $M$ 小于 10。给定的农田图的顶点数量 $N$ 小于 200。所有顶点都位于 1000×1000 的网格点上。

输出

输出必须包含 $M$ 个非负整数。每行包含对应输入测试用例的答案 $n$。

2                  
12                    
1  2 6   3  9 7 2 
2  5 6   4  5 3 1 8   
3  3 5   2  4 2       
4  3 4   2  3 5       
5  4 4   2  4 2 
6  7 4   1  8 
7  2 3   2  8 1 
8  5 3   5  7 2 9 12 6 
9  1 2   3  11 8 1 
10 3 2   1  11 
11 2 1   3  10 9 12 
12 6 1   2  8 11 
4  
3                     
1  2 2   2  2 3 
2  1 1   2  1 3 
3  4 1   2  1 2 
4

2
0

来源

2001 年大田（Taejon）竞赛