Description

There are N students in line according to the seat number, then M pairs of students exchanged their positions in the sequence.

Can you help the teacher find the positions of students K₁ ~ K_Q? 

 

For example, N = 4 M = 3, and three exchanges are:

1 2

2 3

3 4

The seat arrangement of students during the exchange process:

1 2 3 4

-> 2 1 3 4

-> 2 3 1 4

-> 2 3 4 1

The final positions of students 1 ~ N are 4 1 2 3

Input

The first line contains three integers N M Q, the number of students, the number of pairs who exchange positions and the number of students whose positions the teacher wants to know.

Each of the next M lines contains two integers a b, indicating the seat exchange.

The last line contains Q integers that mean K₁ ~ K_Q, giving the id. of the students whose positions the teacher wants to know.

 

 

test cases:

(4/6) 1 <= a, b, K_i <= N, M, Q <= 1000

(1/6) 1 <= a, b, K_i <= N, M <= 1000, 1 <= Q <= 1000000

(1/6) 1 <= a, b, K_i <= N, M <= 100000, 1 <= Q <= 1000000

NOTE:

To pass test cases 5 and 6, please consider how to reduce unnecessary loop iterations.

Output

The positions of students K₁ ~ K_Q

Note that you need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss