Molvania 的皇家城堡遵循其王朝首位君主 Sane 国王的设计。他通过“分而治之”的策略进行统治。因此，所有城堡都是根据基于互连建筑的层次结构建造的。一座建筑由大厅和连接大厅的走廊组成。

最初，城堡仅由一座建筑（主建筑）组成。当人口增长时，城堡会进行如下扩展：建造一座新的外围建筑，并将其连接到现有的建筑之一。像任何其他建筑一样，新建筑也由大厅和走廊组成。此外，还会建造一条额外的走廊，将现有建筑中的一个大厅与新建筑中的一个大厅连接起来。这条走廊是进入新建筑的唯一途径。

一座建筑中的大厅数量最多为 10 个。

图 1：下文提供的示例中的城堡布局。

在动荡时期，国王通过战略性地在大厅中部署守卫来监控所有走廊。他要求你确定监控城堡中所有走廊所需的最少守卫数量（因为他希望尽可能多地保留他的私人卫队）。请注意，自上次火灾以来，城堡内没有门，因此我们可以放心地假设，放置在大厅中的守卫可以监控所有连接的走廊。

输入格式

输入包含多个城堡的描述。在城堡内，每个大厅由 1 到 10000 之间的一个唯一编号标识。每座城堡都是递归定义的，从主建筑的描述开始：

1. 一行包含三个整数，分别表示该建筑中的大厅数量 ($2 \le n \le 10$)、该建筑中的走廊数量 ($1 \le m \le 45$) 以及随后连接到该建筑的外围建筑数量 ($0 \le w \le 10$)。
2. 对于 $m$ 条走廊中的每一条：
   • 一行包含两个整数（每个 $\le 10000$），表示由该走廊连接的两个大厅。这两个大厅都位于当前建筑内。
3. 对于 $w$ 个外围建筑中的每一个：
   • 一行包含两个整数，描述通往该外围建筑的走廊。第一个整数表示当前建筑中的一个大厅，第二个整数表示外围建筑中的一个大厅。
   • 外围建筑及其随后连接的任何更新建筑的结构，通过重复规则 1 到 3 进行描述。

城堡是完全连通的：任何大厅都可以直接或间接地到达其他任何大厅。不存在起点和终点相同的大厅，且每两个大厅之间最多只有一条走廊。

输出格式

对于每座城堡，打印一行，包含一个正整数：为监控城堡中所有走廊，放置在大厅中的最少守卫数量。

样例

输入格式 1

5 8 2
1 2
2 4
3 4
1 3
1 5
2 5
3 5
4 5
1 6
3 3 0
6 7
7 8
8 6
5 10
3 2 2
10 11
10 12
11 13
2 1 0
13 9
11 14
3 2 0
14 15
14 16

输出格式 1

8
14