0-1 BFS

'''
Дороги между разными хохяевами - по 1, иначе 0
10 11
1 1 1 1 2 1 1 2 2 1
1 2
2 8
8 10
10 6
6 9
5 9
4 5
4 9
3 4
3 7
7 1
'''
from collections import deque
n, m = map(int, input().split())
INF = 10**9
dist = [INF] * (n+1)
prev = [None] * (n+1)
dist[1] = 0
g = [[] for i in range(n+1)]
a = [0] + list(map(int, input().split()))
for i in range(m):
    x, y = map(int, input().split())
    w = 0
    if a[x] != a[y]:
        w = 1
    g[x].append((y, w))
    g[y].append((x, w))

q = deque()
q.append(1)
while q:
    v = q.popleft()
    for u, w in g[v]:
        if dist[v] + w < dist[u]:
            dist[u] = dist[v] + w
            prev[u] = v
            if w == 0:
                q.appendleft(u)
            else:
                q.append(u)
if dist[n] != INF:
    path = []
    p = n
    while p != None:
        path.append(p)
        p = prev[p]
    print(dist[n], len(path))
    print(*path[::-1])
else:
    print(-1)