Submission #76895373

---

Source Code Expand

from collections import deque

M = int(input())
graph = [[] for n in range(10)]

for m in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

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

e = 0

for n in range(1, 10):
    if n not in p_list:
        e = n

p_list.append(e)

p_info = tuple(p_list)

used = {}

used[p_info] = 0

queue = deque()

queue.append((p_info, 0))


while queue:
    q = queue.popleft()
    now = q[0]
    c = q[1]

    e = now[-1]
    for neibor in graph[e]:
        nex = []
        for n in range(1, 10):
            p = now[n - 1]
            if p == neibor:
                nex.append(e)
            elif p == e:
                nex.append(neibor)
            else:
                nex.append(p)
        ne = tuple(nex)

        if ne in used:
            continue
        else:
            used[ne] = c + 1
            queue.append((ne, c + 1))
    # print(used)
goal = [n + 1 for n in range(9)]
goal = tuple(goal)

if goal not in used:
    print(-1)
else:
    print(used[goal])

Submission Info

Judge Result