1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
# """
# start at station 1 then go to station N
#
# There are W one way walkways between stations
# A, B = stations connected by walkway
# time = 1 min
#
# Every day (D is total days), station X and Y swap
#
# only want to get off the subway once
#
# """
from queue import Queue
def swap(i, j):
stations[i], stations[j] = stations[j], stations[i]
N, W, D = tuple(map(int, input().split()))
walkways = dict()
for i in range(W):
A, B = tuple(map(int, input().split()))
walkways[A] = walkways.get(A, list()) + [B]
stations = list(map(int, input().split()))
for i in range(D):
X, Y = tuple(map(int, input().split()))
swap(X - 1, Y - 1)
q = Queue()
q.put((0, 1))
visited = set()
while not q.empty():
m, station = q.get()
if m > len(stations):
break
if station == N:
print(m)
break
# take a train
if stations[m] == station:
q.put((m + 1, stations[m + 1]))
# take a walkway
if station in visited:
continue
visited.add(station)
if station in walkways:
for destination in walkways[station]:
q.put((m + 1, destination))
|
