BFS

from queue import Queue
n, m = map(int, input().split()) #n - кол-во вершин, m - кол-во ребер
g = [[] for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)
used = [-1] * n
used[0] = 0
q = Queue()
q.put(0)
while not q.empty():
    h = q.get() #h - текущая вершина
    for e in g[h]:
        if used[e] == -1:
            used[e] = used[h] + 1
            q.put(e)
end = int(input())
print(used[end - 1], used)