PRIMIT - Primitivus recurencis

A genetic code of the abstract primitivus (Primitivus recurencis) is a series of natural numbers K=(a_1 ... a_n). A feature of primitivus we call each ordered pair of numbers (l, r), which appears successively in the genetic code, i.e. there exists such i that l=a_i, r=a_i+1. There are no (p, p) features in a primitivus' genetic code. 

Task

Write a program which: 

  • reads the list of the features from the standard input,
  • computes the length of the shortest genetic code having given features,
  • writes the results to the standard output. 

Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case one positive integer number n is written. It is the number of different features of the primitivus. In each of the following n lines there is a pair of natural numbers l and r separated by a single space, 1 <= l <= 1000, 1 <= r <= 1000. A pair (l, r) is one of the primitivus' features. The features do not repeat in the input file

Output

Your program should write for each test case exactly one integer number equal to the length of the shortest genetic code of the primitivus, comprising the features from the input.

Example

Sample input:
1
12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6

Sample output:
15

All the features from the example are written in the following genetic code:
(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)

Warning: enormous Input/Output data, be careful with certain languages

Added by:Piotr Łowiec
Date:2004-09-13
Time limit:1.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:6th Polish Olympiad in Informatics, stage 3

hide comments
2014-08-28 15:30:16 Jerry Shen
Please give us the limit of n and test cases, so I can think of better algorithms.

Last edit: 2014-08-28 15:30:57
2010-07-20 10:35:41 :D
Upper bound can be deduced.
2010-05-06 20:30:56 madhav
what is the range of n?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.