Ball

Interview

Time limit2sMemory limit128 MB

Summary

Track which of three cups covers a ball as cups swap positions M times, then output the cup number holding it.

Level: Easy2 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

Three cups are placed upside down in a row on a table. From left to right, the cups are numbered 1, 2, and 3. A ball is initially placed under cup 1.

For each move, two cup numbers X and Y are given. The cups with those numbers exchange their positions at the same time. The ball itself does not move while the cups are moved; after the exchange, it is covered by whichever cup is now at the ball's position.

After all M exchanges, determine the number of the cup that contains the ball.

Input

The first line contains the number of exchanges M. M is a positive integer no greater than 50.

Each of the next M lines contains two integers X and Y, meaning that cups X and Y exchange positions. Both X and Y are at most 3, and they may be equal.

The input never produces a state where the ball is outside all cups.

Output

Print the number of the cup containing the ball. If no cup contains the ball, print -1; however, this situation does not occur in the given input.

Examples4

Example 1
Input
```
4
3 1
2 3
3 1
3 2
```
Expected output
```
3
```
Example 2
Input
```
2
1 2
3 1
```
Expected output
```
2
```
Example 3
Input
```
5
2 3
1 3
2 3
2 1
3 1
```
Expected output
```
3
```

Example 4

Input

Expected output