N,M,S=map(int,input().split())
p=[]
for i in range(M):
x,y=map(int,input().split())
p.append([x,y])
bruh=[[] for i in range(N)]
for i in range(M):
bruh[p[i][0]-1].append(p[i][1])
bruh[p[i][1]-1].append(p[i][0])
visit=[False]*N
d=[[0,0] for i in range(N)]
d[S-1][1]=S-1
def bfs(x):
global visit,bruh,d
q=[x]
visit[x-1]=True
while len(q):
for i in q:
u=q.pop(0)
for j in bruh[u-1]:
if not visit[j-1]:
visit[j-1]=True
d[j-1][0]=d[u-1][0]+1
d[j-1][1]=j
print(d)
q.append(j)
d.sort()
for i in d:
if not(i[0]==i[1]==0):
print(i[1],i[0])
bfs(S)