Problem 6.  OLD MAP

 

In monastery library was found an old book with maps, and on each are denoted only castles and roads. Roads connect castles and do not cross. You can travel between any two castles using those roads. Every estate is bounded by a simple polygon of roads. The tax on the estates depends on the number of castles which are in it. The smallest tax is for the estate, which do not have any castle or road in its interior.

You are to write a program ZAD6.EXE which determines the number of estates on the given map bounded by exactly k roads for which the tax is smallest.

 

INPUT: Every map is given in the following format. Castles are numbered from 1 to n. In the first line of input text file ZAD6.DAT is an integer n (3 ≤ n ≤ 1000) the number of castles. In each of the next n lines are given following information for every castle: integer coordinates x and y (0 ≤ x, y ≤ 10000) of the castle, d the number of castles which are directly connected to it, and t1 t2 t3 ..... td list of neighboring castles. In the last line there is a single integer k (3 ≤ k ≤ 1000), the size of estates (number of bounding roads).

 

OUTPUT: In the single line of the output text file ZAD6.DAT there is an integer, number of estates of the given map of size k with the lowest tax.


 

EXAMPLE:

ZAD6.DAT

17

1 5 2 2 5

4 5 3 1 3 5

6 1 3 2 4 8

7 5 4 3 5 6 11

5 8 5 13 16 1 2 4

8 4 2 4 7

8 3 1 6

10 2 4 9 10 11 3

12 2 2 10 8

12 4 4 12 11 8 9

10 5 6 14 15 4 8 10 13

11 6 2 10 13

10 9 3 5 11 12

9 7 2 15 11

7 7 2 14 11

3 10 2 5 17

2 9 1 16

4

 

 

 

 

 

 

 

ZAD6.RES

2