Description

The fences on Farmer Brown's pasture have gotten out of control. They have been divided into segments that are $1\sim 200$ feet long. Two segments can be connected only at their endpoints, and sometimes more than two fences meet at a given endpoint. As a result, the fences form a network that partitions Brown's pasture. Brown wants to restore the pasture to its original state; to do so, he first needs to know which region has the smallest perimeter. Brown labeled each fence segment from $1$ to $N$ ($N=$ the total number of segments). For each segment, he knows:

• The length of the segment;
• The labels of the segments connected to one endpoint of this segment;
• The labels of the segments connected to the other endpoint of this segment.

Fortunately, no fence connects to itself. Given data describing how the fences partition the pasture, write a program to compute the smallest perimeter among all regions.

For example, fences labeled $1\sim 10$ form the configuration shown below (numbers indicate fence labels):

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

In the figure above, the region with the smallest perimeter is formed by fences $2, 7, 8$.

Input Format

The first line contains an integer $N$ ($1 \leq N \leq 100$).

Lines $2$ through $3\times N+1$ describe $N$ groups, three lines per group:

• The first line of each group has $4$ integers: $s$, the label of this fence segment ($1\le s\le N$); $L_s$, the length of this segment ($1\le L_s\le255$); $N1_s$, the number of neighboring fences at one endpoint ($1\le N1_s\le 8$); and $N2_s$, the number of neighboring fences at the other endpoint ($1\le N2_s\le 8$).
• The second line of each group has $N1_s$ integers: the labels of the fences adjacent at one endpoint.
• The third line of each group has $N2_s$ integers: the labels of the fences adjacent at the other endpoint.

Output Format

Output a single line containing one integer, the minimum perimeter.

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

12

Hint

This statement is translated from NOCOW.

USACO Training Section 4.1.

Translated by ChatGPT 5