25528번 - Leave No One Behind 다국어

문제

A card game similar to Old Maid is played by n players P₁, ..., and P_n, sitting clockwise in this order.

For this game, n pairs of cards numbered 1 through n are used. Each player has two cards at hand to start with.

First, any player who has a pair of cards with the same number discards them. If by chance all the players discard the cards in hand, the game ends. Otherwise, the following actions are repeated until the game ends. Note that, from now on, for a player p, the next player means the player closest to p in the clockwise direction among those who still have one or more cards at that point in time.

• Choose the player p as follows.
  • For the first turn, choose P₁. If, however, P₁ has no cards, choose the next player of P₁.
  • For the second and subsequent turns, choose the next player of the one chosen for the previous turn.
• The next player of p, say p′, looks at the card(s) in the hand of p and draws the one having the smallest number among them.
• If that makes a pair of cards with the same number in the hand of p′, the pair is discarded. If no cards remain in any players' hands at this point, the game ends.

Figure B-1 shows the initial hands of the three players of the second dataset in Sample Input. Immediately after, the player P₁ discards the two cards in the hand. p of the first turn is P₂ because P₁ has no cards.

Figure B-1: The initial hands of the second dataset in Sample Input

Figure B-2 shows the hands of the five players of the last dataset in Sample Input after the following actions:

• P₁ is chosen first and the next player of P₁, that is, P₂, draws the card with the smallest number 1 from the P₁'s hand. P₂ has three cards with numbers 1, 3, and 5 in hand at the end of this turn;
• P₃, P₄, and P₅, in this order, draw the same card with the number 1 that was initially in the P₁'s hand; and
• P₅ discards the pair of cards with the number 1.

After this, P₁ draws the only remaining card in P₅'s hand and discards the drawn card and the card with the same number 2 in the hand. The player to be drawn from the hand next is the next player of P₅, which is P₂ because P₁'s hand is empty now.

Figure B-2: The hands of the last dataset in Sample Input after the fourth turn

Since at least one pair of cards is discarded between two drawings from the hand of the same player, the game will end sooner or later. Unlike Old Maid, no cards will be left in the hand of any player at the end.

Write a program that, for given initial hands of all the players, computes the number of times cards are drawn by the end of the game.

입력

The input consists of multiple datasets, each in the following format.

n
c1,1 c1,2
⋮
cn,1 cn,2

n is the number of players. n is an integer no less than two and no more than 1000. c_i,1 and c_i,2 are the numbers on the two cards in the initial hand of P_i (1 ≤ i ≤ n). Each integer between 1 and n, inclusive, appears exactly twice in c_1,1, c_1,2, ..., c_n,1, and c_n,2.

The end of the input is indicated by a line containing a zero. The input has at most 10000 lines.

출력

For each dataset, output a single line containing the integer that is the number of times cards are drawn.

제한

힌트