#задача на bfs
# from collections import deque
# def BFS(S, N, G):
# visited = [False] * N
# queue = deque([S])
# visited[S] = True
# p = []
# while queue:
# V = queue.popleft()
# p.append(V + 1)
# for x in G[V]:
# if not visited[x]:
# visited[x] = True
# queue.append(x)
# return p
# N, S = map(int, input().split())
# G = [[] for _ in range(N)] # создаем пустые списки
# for i in range(N):
# a = list(map(int, input().split()))
# # Преобразуем 1-based номера в 0-based индексы
# for vertex in a:
# G[i].append(vertex - 1)
# G[i].sort() # сортируем индексы
# # g = []
# # for i in range(N):
# # l = list(map(int,input().split()))
# # g.append(l)
# # G =[[] for i in range(N)]
# # for i in range(N):
# # for j in range(N):
# # if g[i][j] == 1: G[i].append(j)
# x = BFS(S - 1, N, G)
# if len(x) == N:
# print(*x)
# else:
# print('НЕТ')
#задача 1 на полуполный граф
# n,m = map(int,input().split())
# g = [[0 for _ in range(n)] for j in range(n)]
# for i in range(m):
# v,u = map(int,input().split())
# v -= 1
# u -= 1
# g[v][u] = 1
# ans = 'YES'
# for v in range(n):
# for u in range(v + 1,n):
# if not (g[v][u] or g[u][v]):
# ans = 'NO'
# print(ans)
#истоки
# n = int(input())
# l = []
# k1 = []
# k0 = []
# for i in range(n):
# a = list(map(int,input().split()))
# l.append(a)
# for i in range(n):
# c = 0
# for j in range(n):
# if l[i][j] == 0:
# c += 1
# if c == n:
# k0.append(i+1)
# for j in range(n):
# k = 0
# for i in range(n):
# if l[i][j] == 0:
# k += 1
# if k == n:
# k1.append(j+1)
# G = []*n
# print(len(k1))
# for i in k1:
# print(i)
# print(len(k0))
# for i in k0:
# print(i)
#3 на dfs где ввод колво вершин и старт
# vis = []
# ans = []
# g = []
# def dfs(v):
# global vis,g
# vis[v] = 1
# ans.append(v + 1)
# for u in g[v]:
# if not vis[u]:
# dfs(u)
# n,s = map(int,input().split())
# s -= 1
# g = [[] for j in range(n)]
# # for i in range(n):
# # a = list(map(int,input().split()))
# # for j in range(n):
# # if a[j] == 1:
# # g[i].append(j)
# for i in range(n):
# a = list(map(int,input().split()))
# for j in range(len(a)):
# g[i].append(a[j] - 1)
# vis = [0] * n
# dfs(s)
# if len(ans) == n:
# print(*ans)
# else:
# print("НЕТ")
#последняя где точки и решетки
# def main():
# M, N = map(int, input().split())
# grid = [list(input().strip()) for _ in range(M)]
# visited = [[False] * N for _ in range(M)]
# pieces = 0
# # Направления: вверх, вниз, влево, вправо
# directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# def dfs(r, c):
# stack = [(r, c)]
# visited[r][c] = True
# while stack:
# x, y = stack.pop()
# for dx, dy in directions:
# nx, ny = x + dx, y + dy
# if 0 <= nx < M and 0 <= ny < N:
# if not visited[nx][ny] and grid[nx][ny] == '#':
# visited[nx][ny] = True
# stack.append((nx, ny))
# for i in range(M):
# for j in range(N):
# if grid[i][j] == '#' and not visited[i][j]:
# pieces += 1
# dfs(i, j)
# print(pieces)
# if __name__ == "__main__":
# main()
#про почистить зубы
# from collections import deque
# def main():
# N, S, V1, V2 = map(int, input().split())
# S -= 1
# V1 -= 1
# V2 -= 1
# graph = []
# for _ in range(N):
# row = list(map(int, input().split()))
# graph.append(row)
# def bfs(start, target):
# if start == target:
# return 0
# dist = [-1] * N
# dist[start] = 0
# q = deque([start])
# while q:
# u = q.popleft()
# for v in range(N):
# if graph[u][v] == 1 and dist[v] == -1:
# dist[v] = dist[u] + 1
# if v == target:
# return dist[v]
# q.append(v)
# return float('inf') # недостижим
# dist1 = bfs(S, V1)
# dist2 = bfs(S, V2)
# if dist1 < dist2:
# print(1)
# else:
# print(0)
# if __name__ == "__main__":
# main()