10413 - 篱笆回路

农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱 笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。 布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆的有如下属性：

该段篱笆的长度 该段篱笆的一端所连接的另一段篱笆的标号 该段篱笆的另一端所连接的另一段篱笆的标号 幸运的是，没有篱笆连接它自身。 对于一组有关篱笆如何分割牧场的数据，写一个程序来计算出所有分割出的区域中最小的周长。 例如，标号1~10的篱笆由下图的形式组成（下面的数字是篱笆的标号）： 　

       1

+---------------+ |\ /| 2| \7 / | | \ / | +---+ / |6 | 8 \ /10 | 3| \9 / | | \ / | +-------+-------+

   4       5

上图中周长最小的区域是由2，7，8号篱笆形成的。 　

第1行: N (1 <= N <= 100) 第2行到第3*N+1行: 每三行为一组，共N组信息: 每组信息的第1行有4个整数: s, 这段篱笆的标号(1 <= s <= N); Ls, the这段篱笆的长度 (1 <= Ls <= 255); N1s (1 <= N1s <= 8) 与本段篱笆的一端所相邻的篱笆的数量; and N2s与本段篱笆的另一端所相邻的篱笆的数量。 (1 <= N2s <= 8).
每组信息的的第2行有 N1s个整数, 分别描述与本段篱笆的一端所相邻的篱笆的标号。 每组信息的的第3行有N2s个整数, 分别描述与本段篱笆的另一端所相邻的篱笆的标号。

输出的内容为单独的一行，用一个整数来表示最小的周长。

Fence Loops

The fences that surround Farmer Brown's collection of pastures have gotten out of control. They are made up of straight segments from 1 through 200 feet long that join together only at their endpoints though sometimes more than two fences join together at a given endpoint. The result is a web of fences enclosing his pastures. Farmer Brown wants to start to straighten things out. In particular, he wants to know which of the pastures has the smallest perimeter.

Farmer Brown has numbered his fence segments from 1 to N (N = the total number of segments). He knows the following about each fence segment:

the length of the segment the segments which connect to it at one end the segments which connect to it at the other end. Happily, no fence connects to itself. Given a list of fence segments that represents a set of surrounded pastures, write a program to compute the smallest perimeter of any pasture. As an example, consider a pasture arrangement, with fences numbered 1 to 10 that looks like this one (the numbers are fence ID numbers):

       1

+---------------+ |\ /| 2| \7 / | | \ / | +---+ / |6 | 8 \ /10 | 3| \9 / | | \ / | +-------+-------+

   4       5

The pasture with the smallest perimeter is the one that is enclosed by fence segments 2, 7, and 8.

PROGRAM NAME: fence6 INPUT FORMAT Line 1: N (1 <= N <= 100) Line 2..3*N+1: N sets of three line records:

The first line of each record contains four integers: s, the segment number (1 <= s <= N); Ls, the length of the segment (1 <= Ls <= 255); N1s (1 <= N1s <= 8) the number of items on the subsequent line; and N2sthe number of items on the line after that (1 <= N2s <= 8). The second line of the record contains N1 integers, each representing a connected line segment on one end of the fence. The third line of the record contains N2 integers, each representing a connected line segment on the other end of the fence.

SAMPLE INPUT (file fence6.in) 10 1 16 2 2 2 7 10 6 2 3 2 2 1 7 8 3 3 3 2 1 8 2 4 4 8 1 3 3 9 10 5 5 8 3 1 9 10 4 6 6 6 1 2 5 1 10 7 5 2 2 1 2 8 9 8 4 2 2 2 3 7 9 9 5 2 3 7 8 4 5 10 10 10 2 3 1 6 4 9 5

OUTPUT FORMAT The output file should contain a single line with a single integer that represents the shortest surrounded perimeter. SAMPLE OUTPUT (file fence6.out) 12