UCRPC F21 B - Lost in the Shuffle

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 256M

Problem type

Find the doll with the most mini-dolls inside!

Try not to blink during the shuffle!

Lost in the Shuffle is a four-player mini-game in Super Mario Party, and you can view how the game is played here. In the game, Toad places five matryoshka dolls resembling them on the table. The middle one is a special one since it contains the most mini-dolls inside. Toad will then shuffle the five dolls by swapping pairs of them for several rounds, speeding up gradually. The players will then choose a matryoshka doll and the player that chooses the special one (the one that was originally in the middle) wins the game.

The last several rounds of shuffling go pretty fast, so it's very hard to tell by just staring at the screen. Given all the swaps that will be done in order, can you write a program to decide which one to choose to win the game?

Input Specification

The first line of the input contains one integer, n (0\le n\le 10^4), which is the total number of swaps in the game.

In the next n lines, line i contains a pair a_i, b_i (1\le a, b\le 5), which means that in the i-th swap, doll a_i will be swapped with doll b_i.

The five dolls are labeled 1 to 5. The middle one (the one with label 3) is our target.

Output Specification

The output only contains one integer, which is the current position of the special doll. Note that the output must be in the range of 1 to 5.

Sample Input

1 3
2 4
1 2
2 5
1 2

Sample Output


Explanation for Sample Output

In the first test case, the special doll was first swapped to position 1 in the first swap. Then in the 3rd swap, it was put at position 2. Then in the 4th swap, it will be moved to position 5. The last swap didn't change its position. Therefore the output is 5.

Source of pictures and descriptions: https://www.mariowiki.com/Lost_in_the_Shuffle. You can also find more details about the game from this site.


There are 20 test cases, 4 points each.


There are no comments at the moment.