TESTO DEL PROBLEMA

Selezioni Territoriali 2012 – Olimpiadi Italiane dell’ Informatica

Grand Prix 

Descrizione del problema

State assistendo a un Gran Premio di Formula 1. Prima dell’inizio, il tabellone riporta la griglia di partenza, ovvero l’ordine in cui le vetture partiranno dalla linea del traguardo. Non appena inizia il gran premio, per ogni sorpasso, il tabellone scrive due numeri: quello della vettura che ha effettuato il sorpasso, e quello della vettura che è stata superata. Il vostro compito è di scrivere un programma che, ricevuti in ingresso l’ordine di partenza e la lista dei sorpassi, calcoli chi ha vinto il gran premio.
Per esempio, considerate il seguente gran premio, con 3 macchine e 4 sorpassi. L’ordine iniziale di partenza è stato: la vettura numero 2, poi la vettura numero 1 e infine la vettura numero 3. I sorpassi sono stati, nell’ordine:

1. la numero 3 ha superato la numero 1;
2. la numero 3 ha superato la numero 2;
3. la numero 1 ha superato la numero 2;
4. la numero 2 ha superato la numero 1;

In questo caso, è facile vedere che la vettura numero 3 ha vinto il gran premio. Come si può notare dall’esempio, i sorpassi avvengono sempre tra due vetture consecutive.

Dati di input

Il file di input è costituito da 1+N+M righe di testo. La prima riga contiene due interi positivi separati da uno spazio: N che è il numero di vetture e M che è il numero di sorpassi. Le successive N righe contengono l’ordine di partenza: per ogni riga c’è un numero intero K che rappresenta una vettura, con 1 ≤ K ≤ N. La vettura che parte in i-esima posizione nell’ordine di partenza si trova quindi nella riga (i+1) del file. Le restanti M righe contengono tutti i sorpassi, nell’ordine in cui sono avvenuti, uno in ogni riga. Ogni riga contiene due interi separati da uno spazio: A, ovvero il numero della vettura che ha effettuato il sorpasso, e B, ovvero il numero della vettura che ha subito il sorpasso.

Dati di output

Il file di output deve contenere un solo intero: il numero della vettura che ha vinto il gran premio.

Assunzioni

• 2 ≤ N ≤ 30
• 1 ≤ M ≤ 100