Problem 1050. -- Moving Tables## HDU_1050: Moving Tables

Time Limit: 1000 MS Memory Limit: 32 MB 64bit IO Format: %I64d

Submitted: 8 Accepted: 8

[Submit][Status][Web Board]## Description

The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.

For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.

## Input

The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above.

## Output

The output should contain the minimum time in minutes to complete the moving, one per line.

## Sample Input

3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

## Sample Output

[Submit][Status][Web Board]