def DFS(start):
b[start]=1
for u in a[start]:
if b==0:
DFS(u)
print(start,u)
n,m=map(int,input().split())
a = [[] for i in range(n+1)]
for i in range(m):
x, y = map(int, input().split())
a[x].append(y)
a[y].append(x)
b=[0](n+1)
DFS(1)

def DFS(start):
visited[start]=True
for u in b[start]:
if not visited:
DFS(u)
n= int(input())
a= [[int(j) for j in input().split()] for i in range(n)]
b=[list() for i in range (n)]
for i in range(n):
for j in range(n):
if a[j]==1:
b.append(j)
visited=[False](n+1)
DFS(1)
k=0
for i in range(n):
if visited==True:
k+=1
if k==n:
print('YES')
else:
print('NO')

def DFS(start):
visited[start]=True
for u in b[start]:
if not visited:
DFS(u)
n= int(input())
a= [[int(j) for j in input().split()] for i in range(n)]
b=[list() for i in range (n)]
for i in range(n):
for j in range(n):
if a[j]==1:
b.append(j)
visited=[False](n+1)
k=0
t=0
for i in range(n):
for j in range(i):
t+=a[j]
DFS(0)
for i in range(n):
if visited==True:
k+=1
if k==len(b) and t==n-1:
print('YES')
else:
print('NO')

def DFS(start):
visited[start]=True
for u in b[start]:
if not visited:
DFS(u)
n= int(input())
a= [[int(j) for j in input().split()] for i in range(n)]
b=[list() for i in range (n)]
for i in range(n):
for j in range(n):
if a[j]>0:
b.append(j)
visited=[False](n+1)
k=1
DFS(0)
for i in range(n):
if not visited:
k+=1
DFS(i)
print(k)