34416번 - Follow The Prize 다국어

문제

A total of $n$ cups were placed upside-down on a table, a prize was placed under one of them, and then the cups were shuffled. Luckily, you know under which cup the prize began, and how the cups were shuffled. Can you determine the final position of the prize?

A cup (and the prize which it might cover) can only be in one of $n$ distinct positions at any given time: 1,ドル 2, \ldots, n$. No two cups can be in the same position at any given time.

The cups are shuffled by performing a series of swaps. A swap is defined as exchanging the location of two cups. For example if the cups in positions 4ドル$ and 7ドル$ were swapped, the cup originally in position 4ドル$ would end in position 7ドル,ドル and the cup originally in position 7ドル$ would end in position 4ドル$. If the prize were originally under cup 7ドル,ドル this swap would have moved the prize to position 4ドル$.

입력

The first line is $n,ドル an integer between 2ドル$ and 1ドル,000円,000円,ドル inclusive, defining the number of cups.

The second line is an integer between 1ドル$ and $n,ドル inclusive, which defines the initial position of the prize.

The third line is $m,ドル a non-negative integer less than or equal to 1ドル,000円,000円,ドル defining the number of swaps performed to shuffle the cups.

The final $m$ lines report the swaps that were performed, in order. Each line consists of two different space-separated integers, between 1ドル$ and $n,ドル defining the positions of the cups that were exchanged for that swap.

출력

The output is a single integer between 1ドル$ and $n,ドル which is the position of the prize after all of the swaps are performed.

제한

노트