Skip to content

atcoder abc224

 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
59
60
61
62
63
64
65
66
# 5
# 1 2
# 1 3
# 1 9
# 2 9
# 3 9
# 3 9 2 4 5 6 7 8
from collections import defaultdict

# 1. struct graph
# 2. find empty space
# 3. do dp

graph = defaultdict(list)
visited = defaultdict(int)
cnt = 1

N = int(input())

# struct graph
for i in range(N):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

pieces = list(map(int, input().split()))

# find empty space
cur = list(set(range(1, 10)) - set(pieces))[0]

pieces.append(cur)
pieces = list(map(str, pieces))

if pieces == sorted(pieces):
    print(0)
    exit()

# do dp
q = ["".join(pieces)]

while q:
    len_q = len(q)
    is_finished = False
    for j in range(len_q):
        cur = q.pop(0)
        if visited.get(cur):
            continue
        visited[cur] = cnt
        for i in graph[cur[0]]:
            next_pieces = list(cur[1][:])
            next_cur = i
            next_pieces[next_pieces.index(i)] = cur[0]

            if next_pieces == sorted(next_pieces):
                print(cnt)
                is_finished = True
                break
            q.append((next_cur, tuple(next_pieces)))
        if is_finished:
            break
    if is_finished:
        break
    cnt += 1

if not is_finished:
    print(-1)