A well-known bandit who used to haunt the forests around Siruseri was eliminated by the policemen a few

months ago. There are several stories about a valuable treasure that he is alleged to have buried

somewhere in the forest.

The deceased bandit had several hideouts and the police found a lot of things in these hideouts --- a

number of guns, ammunition, knives, ... Interestingly, in every hideout there was a strange looking

machine. This machine looked a bit like the weighing machine that is found in Indian railway stations

where you insert a coin and get a card with your weight printed on it. The police had no idea what these

machines were meant for and since they were heavy and in the middle of the forest they just left them there.

Only one man knew that the clue to the buried treasure was in these innocuous looking machines and that

was Muttal. Muttal used to be part of the dacoit's band of robbers but was thrown out for being too dumb.

Here is how the treasure was to be found. One had to insert a 1 rupee coin into one of these machines.

This machine would then put out a token and a card on which was printed the name of the machine to be

visited next. The token was then to be inserted into the machine whose name was printed on the card. The

new machine would, in turn, produce another token and another card with a new destination printed on it,

and so on.

If you started with by putting a 1 rupee coin in the correct machine place and followed the sequence of

machines indicated by the cards, inserting each token produced by one machine into the next one, eventually

one of these machines would put out a map to the treasure. Unfortunately, though, Muttal did not know which

machine one should begin with.

Unknown to Muttal, the bandit had played one last joke on the world. Knowing his end was near, he had

reprogrammed these machines. There was no longer any map. All that you got for inserting a token in any

machine was another token and a card leading you to the next machine. So poor Muttal is going to spend the

rest of his life inserting tokens into machines and walking from one machine to another.

You are given M machines that generate and respond to T different kinds of tokens. We regard the 1 rupee

coin also as one of the T types of tokens. For each machine m and each token t you are told what happens

when t is inserted into m: that is, which token is produced by m and what the next destination printed on

the card is.

Your task is the following. Given the identity of the machine where Muttal starts his search and an integer

N, identify the Nth machine that Muttal will visit. Muttal always begins his search by inserting a 1 rupee

coin into the first machine.

For example suppose there are three machines and two kinds of tokens and the description of the machines

is as follows:

Machine Input Token Next Token Next Machine

M1 T1 T2 M2

M1 T2 T1 M2

M2 T1 T1 M3

M2 T2 T2 M3

M3 T1 T1 M1

M3 T2 T2 M1

We take T1 to represent the one rupee coin. If Muttal starts at machine M1 then the sequence of machines

he visits is M1, M2, M3, M1, M2, M3, ... Thus, the fourth machine he visits is M1, the fifth machine he visits is M2 and so on.

T is the number of tokens, S is the machine where Muttal starts his wild goose chase and you need to compute

the Nth machine he visits. We assume that the machines are numbered 1..M and the tokens are numbered 1..T and

that the one rupee coin is the same as token 1. This is followed by M ¡Á T lines of input (lines 2..M¡ÁT+1) each

containing two integers. The first T of these give information about what comes out of machine 1 if different

tokens are inserted into it, the next T describes the same for machine 2 and soon. In other words, line m¡ÁM+i+1

(0 ¡Ü m < M, 1 ¡Ü i ¡Ü T) contains two integers t(m,i) and c(m,i) where t(m,i) is the token put out by machine m

when token i is inserted into it and c(m,i) is the machine name printed in the card put out when token i is inserted

into machine m.

You may assume that 1 ¡Ü M ¡Ü 200, 1 ¡Ü T ¡Ü 20 and N ¡Ü 1000000000. You may further assume that in 50%

of the inputs N ¡Ü 1000000.

A single integer A indicating the Nth machine that Muttal visits.

2 2

1 2

1 3

2 3

1 1

2 1