402593: GYM100814 H Tonight's Dinner

Reem is organizing a big dinner tonight. In her garden there are two tables in the shape of regular polygons. One of those tables is the dinner table, and the other one is the dessert table. The guests will first eat dinner at the dinner table, and when dinner is over, they will all go to the dessert table to eat dessert. They will sit at the corners of the polygonal tables. Reem decided to assign a certain seating order for the guests around the dinner table, and another seating order for the guests around the dessert table. When dessert time comes, all guests will leave the dinner table, follow different paths in the garden, and reach their assigned seats at the dessert table. Reem wants the paths that the guests will follow to have minimal total number of intersections among themselves. She will provide you with the seating orders of the guests, and you will find the least possible number of intersections for the paths.

You may assume the following:

1) There will be n guests at the party and each will sit at a different corner. No two guests may share the same table corner. Reem herself is not considered a guest and won't be seated.

2) The garden has unlimited length in all directions. The dinner and the dessert table are regular polygons with n sides and n corners and they are centered at 2 different points in the garden. Dinner and dessert tables do not intersect in any way.

3) Each path is a curve that starts at a corner of the dinner table, and ends at a corner of the dessert table. A path may not intersect the tables at any point.

4) For any pair of guests (A,B), the path of guest A will have at most 1 point in common with the path of guest B.

5) No three or more paths will intersect at the same point, so each intersection point is between exactly 2 paths only.

The figure below shows one of the optimal solutions for first test case in the sample test:

The input will start with a single integer T, the number of test cases. Each test case will consist of three lines: The first line contains a single integer (2 < n < 100), the number of guests. The second line contains n space-separated strings (the names of the guests, given according to their seating order around the dinner table). The third line contains n space-separated strings (the names of the guests, given according to their seating order around the dessert table). Names will consist of no more than 10 alphanumeric characters and no two guests will have the same name. The list of names will be given in the clockwise order around each table.

Print a single line for each test case containing a single integer representing the minimum total number of intersections between paths.

2
3
A B C
A B C
3
Rayan Mustafa Ahmad
Rayan Ahmad Mustafa

1
0