# Задача 8882340 (DFS)
data = input().split()
N = int(data[0])
M = int(data[1])
S = int(data[2])
matrix = []
for _ in range(N):
row = list(map(int, input().split()))
matrix.append(row)
adj = [[] for _ in range(N + 1)]
for j in range(M):
vertices = []
for i in range(N):
if matrix[i][j] == 1:
vertices.append(i + 1)
if len(vertices) == 2:
u, v = vertices
adj[u].append(v)
adj[v].append(u)
for i in range(1, N + 1):
adj[i].sort()
visited = [False] * (N + 1)
order = []
stack = [S]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
order.append(v)
for j in range(len(adj[v]) - 1, -1, -1):
to = adj[v][j]
if not visited[to]:
stack.append(to)
if len(order) == N:
print(' '.join(map(str, order)))
else:
print("НЕТ")
print("---")
# Задача 8882347 (BFS)
data = input().split()
N = int(data[0])
M = int(data[1])
S = int(data[2])
matrix = []
for _ in range(N):
row = list(map(int, input().split()))
matrix.append(row)
adj = [[] for _ in range(N + 1)]
for j in range(M):
vertices = []
for i in range(N):
if matrix[i][j] == 1:
vertices.append(i + 1)
if len(vertices) == 2:
u, v = vertices
adj[u].append(v)
adj[v].append(u)
for i in range(1, N + 1):
adj[i].sort()
visited = [False] * (N + 1)
order = []
queue = [S]
visited[S] = True
q_start = 0
while q_start < len(queue):
v = queue[q_start]
q_start += 1
order.append(v)
for to in adj[v]:
if not visited[to]:
visited[to] = True
queue.append(to)
if len(order) == N:
print(' '.join(map(str, order)))
else:
print("НЕТ")
print("---")
# Задача 8882349 (Турнир)
data = input().split()
n = int(data[0])
m = int(data[1])
adj = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
adj[u][v] = 1
is_tournament = True
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if adj[i][j] + adj[j][i] != 1:
is_tournament = False
break
if not is_tournament:
break
if is_tournament:
print("YES")
else:
print("NO")
print("---")
# Задача 8882343 (Полный граф)
data = input().split()
n = int(data[0])
m = int(data[1])
edges = set()
for _ in range(m):
u, v = map(int, input().split())
if u > v:
u, v = v, u
edges.add((u, v))
is_complete = True
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if (i, j) not in edges:
is_complete = False
break
if not is_complete:
break
if is_complete:
print("YES")
else:
print("NO")
print("---")
# Задача 8882342 (Кто первый)
data = input().split()
N = int(data[0])
S = int(data[1])
V1 = int(data[2])
V2 = int(data[3])
adj = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
row = list(map(int, input().split()))
for j in range(1, N + 1):
if row[j - 1] == 1:
adj[i].append(j)
def bfs(start, target):
dist = [-1] * (N + 1)
dist[start] = 0
queue = [start]
q_start = 0
while q_start < len(queue):
v = queue[q_start]
q_start += 1
for to in adj[v]:
if dist[to] == -1:
dist[to] = dist[v] + 1
queue.append(to)
if to == target:
return dist[to]
return -1
d1 = bfs(V1, S)
d2 = bfs(V2, S)
if d1 == -1 and d2 == -1:
print("infinity")
elif d1 == -1:
print("PI")
elif d2 == -1:
print("VI")
elif d1 < d2:
print("VI")
elif d2 < d1:
print("PI")
else:
print("fifth-fifth")
print("---")
# Задача 8882341 (Площадь комнаты)
N = int(input())
grid = []
for _ in range(N):
grid.append(list(input().strip()))
x, y = map(int, input().split())
x -= 1
y -= 1
visited = [[False] * N for _ in range(N)]
count = 0
queue = [(x, y)]
visited[x][y] = True
q_start = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q_start < len(queue):
cx, cy = queue[q_start]
q_start += 1
count += 1
for d in range(4):
nx, ny = cx + dx[d], cy + dy[d]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and grid[nx][ny] == '*':
visited[nx][ny] = True
queue.append((nx, ny))
print(count)
print("---")
# Задача 8882376 (Марио DFS)
data = input().split()
N = int(data[0])
S = int(data[1])
adj = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
line = input().strip()
if line:
neighbors = list(map(int, line.split()))
neighbors.sort()
adj[i] = neighbors
visited = [False] * (N + 1)
order = []
stack = [S]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
order.append(v)
for j in range(len(adj[v]) - 1, -1, -1):
to = adj[v][j]
if not visited[to]:
stack.append(to)
if len(order) == N:
print(' '.join(map(str, order)))
else:
print("HET")
print("---")
# Задача 8882377 (Встреча башен)
data = input().split()
n = int(data[0])
m = int(data[1])
s1, s2 = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
def bfs(start):
dist = [-1] * (n + 1)
dist[start] = 0
queue = [start]
q_start = 0
while q_start < len(queue):
v = queue[q_start]
q_start += 1
for to in adj[v]:
if dist[to] == -1:
dist[to] = dist[v] + 1
queue.append(to)
return dist
dist1 = bfs(s1)
dist2 = bfs(s2)
min_time = 10**9
best_city = -1
for city in range(1, n + 1):
if dist1[city] != -1 and dist2[city] != -1:
time = dist1[city]
if dist2[city] > time:
time = dist2[city]
if time < min_time or (time == min_time and city < best_city):
min_time = time
best_city = city
if best_city == -1:
print(-1)
else:
print(min_time)
print(best_city)
print("---")
# Задача 8882378 (Пещеры)
N = int(input())
grid = []
for _ in range(N):
grid.append(list(input().strip()))
visited = [[False] * N for _ in range(N)]
count = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(N):
for j in range(N):
if grid[i][j] == '.' and not visited[i][j]:
count += 1
queue = [(i, j)]
visited[i][j] = True
q_start = 0
while q_start < len(queue):
x, y = queue[q_start]
q_start += 1
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and grid[nx][ny] == '.':
visited[nx][ny] = True
queue.append((nx, ny))
print(count)
print("---")
# Задача 8882379 (Турнир)
data = input().split()
n = int(data[0])
m = int(data[1])
adj = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
adj[u][v] = 1
is_tournament = True
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if adj[i][j] + adj[j][i] != 1:
is_tournament = False
break
if not is_tournament:
break
if is_tournament:
print("YES")
else:
print("NO")
print("---")
# Задача 8882380 (Гонщик BFS)
data = input().split()
N = int(data[0])
S = int(data[1])
adj = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
line = input().strip()
if line:
neighbors = list(map(int, line.split()))
neighbors.sort()
adj[i] = neighbors
visited = [False] * (N + 1)
order = []
queue = [S]
visited[S] = True
q_start = 0
while q_start < len(queue):
v = queue[q_start]
q_start += 1
order.append(v)
for to in adj[v]:
if not visited[to]:
visited[to] = True
queue.append(to)
if len(order) == N:
print(' '.join(map(str, order)))
else:
print("HET")
print("---")
# Задача (Квест) - Время выхода
N, K, S = map(int, input().split())
exits = list(map(int, input().split()))
M = int(input())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
dist = [-1] * (N + 1)
dist[S] = 0
queue = [S]
q_start = 0
while q_start < len(queue):
v = queue[q_start]
q_start += 1
for to in adj[v]:
if dist[to] == -1:
dist[to] = dist[v] + 1
queue.append(to)
min_dist = 10**9
for exit_room in exits:
if dist[exit_room] != -1 and dist[exit_room] < min_dist:
min_dist = dist[exit_room]
if min_dist == 10**9:
print("НЕТ")
else:
d = min_dist
cycles = (d + 4) // 5
if cycles == 1:
time = d * 2
else:
time = (cycles - 1) * 20 + (d - (cycles - 1) * 5) * 2
print(time)