The main characters have been omitted to be short.

You are given a directed unweighted graph without loops with $n$ vertexes and a path in it (that path is not necessary simple) given by a sequence $p_1, p_2, \ldots, p_m$ of $m$ vertexes; for each $1 \leq i < m$ there is an arc from $p_i$ to $p_{i+1}$.

Define the sequence $v_1, v_2, \ldots, v_k$ of $k$ vertexes as good, if $v$ is a subsequence of $p$, $v_1 = p_1$, $v_k = p_m$, and $p$ is one of the shortest paths passing through the vertexes $v_1$, $\ldots$, $v_k$ in that order.

A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements. It is obvious that the sequence $p$ is good but your task is to find the shortest good subsequence.

If there are multiple shortest good subsequences, output any of them.

 


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 100$) — the number of vertexes in a graph. 

The next $n$ lines define the graph by an adjacency matrix: the $j$-th character in the $i$-st line is equal to $1$ if there is an arc from vertex $i$ to the vertex $j$ else it is equal to $0$. It is guaranteed that the graph doesn't contain loops.

The next line contains a single integer $m$ ($2 \le m \le 10^6$) — the number of vertexes in the path. 

The next line contains $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \le p_i \le n$) — the sequence of vertexes in the path. It is guaranteed that for any $1 \leq i < m$ there is an arc from $p_i$ to $p_{i+1}$.


-----Output-----

In the first line output a single integer $k$ ($2 \leq k \leq m$) — the length of the shortest good subsequence. In the second line output $k$ integers $v_1$, $\ldots$, $v_k$ ($1 \leq v_i \leq n$) — the vertexes in the subsequence. If there are multiple shortest subsequences, print any. Any two consecutive numbers should be distinct.


-----Examples-----
Input
4
0110
0010
0001
1000
4
1 2 3 4

Output
3
1 2 4 
Input
4
0110
0010
1001
1000
20
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Output
11
1 2 4 2 4 2 4 2 4 2 4 
Input
3
011
101
110
7
1 2 3 1 3 2 1

Output
7
1 2 3 1 3 2 1 
Input
4
0110
0001
0001
1000
3
1 2 4

Output
2
1 4 


-----Note-----

Below you can see the graph from the first example:

[Image]

The given path is passing through vertexes $1$, $2$, $3$, $4$. The sequence $1-2-4$ is good because it is the subsequence of the given path, its first and the last elements are equal to the first and the last elements of the given path respectively, and the shortest path passing through vertexes $1$, $2$ and $4$ in that order is $1-2-3-4$. Note that subsequences $1-4$ and $1-3-4$ aren't good because in both cases the shortest path passing through the vertexes of these sequences is $1-3-4$.

In the third example, the graph is full so any sequence of vertexes in which any two consecutive elements are distinct defines a path consisting of the same number of vertexes.

In the fourth example, the paths $1-2-4$ and $1-3-4$ are the shortest paths passing through the vertexes $1$ and $4$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Dynamic programming

Graph algorithms

Shortest paths


Solutions:
import sys, atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda : inp.readline().decode('ascii')
buf = BytesIO()
print = lambda s: buf.write(s.encode('ascii'))
atexit.register(lambda : sys.__stdout__.buffer.write(buf.getvalue()))
n = int(input())
inf = 200
g = []
g = [[0] * n for i in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		g[i][j] = 1 if int(s[j]) else inf
		if i == j:
			g[i][j] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[k][j] + g[i][k])
m = int(input())
p = list(map(int, input().split()))
ans = [p[0]]
for i in range(1, m - 1):
	if g[ans[-1] - 1][p[i + 1] - 1] - g[ans[-1] - 1][p[i] - 1] != 1:
		ans.append(p[i])
ans.append(p[-1])
print(str(len(ans)))
print('\n')
print(' '.join((str(i) for i in ans)))


import sys

def input():
	return sys.stdin.readline()[:-1]
n = int(sys.stdin.readline())
s = [input() for _ in range(n)]
d = [[pow(10, 30)] * n for i in range(n)]
for i in range(n):
	for j in range(n):
		if s[i][j] == '1':
			d[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
m = int(sys.stdin.readline())
p = list(map(int, sys.stdin.readline().split()))
ans = [p[0]]
cur = 1
while cur < m - 1:
	if ans[-1] == p[cur + 1]:
		ans.append(p[cur])
	elif d[ans[-1] - 1][p[cur] - 1] + d[p[cur] - 1][p[cur + 1] - 1] > d[ans[-1] - 1][p[cur + 1] - 1]:
		ans.append(p[cur])
	cur += 1
ans.append(p[-1])
print(len(ans))
print(*ans)


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
n = int(input())
d = defaultdict(set)
for _ in range(n):
	z = input()
	for i in range(n):
		if z[i] == '1':
			d[_ + 1].add(i + 1)
m = int(input())
z = listin()
ans = [z[0]]
for i in range(1, m - 1):
	if z[i] in d[ans[-1]] and z[i + 1] in d[z[i]] and (z[i + 1] not in d[ans[-1]]) and (ans[-1] != z[i + 1]):
		pass
	else:
		ans.append(z[i])
ans.append(z[-1])
print(len(ans))
print(*ans)


n = int(input())
grap = [[] for _ in range(n)]
for i in range(n):
	l = input()
	for j in range(n):
		if l[j] == '1':
			grap[i].append(j)
dist = [[-1] * n for _ in range(n)]
for i in range(n):
	dist[i][i] = 0
	l = [i]
	while len(l) > 0:
		l2 = []
		for j in l:
			for k in grap[j]:
				if dist[i][k] == -1:
					dist[i][k] = dist[i][j] + 1
					l2.append(k)
		l = l2
m = int(input())
p = list(map(int, input().split()))
res = 2
rt = [str(p[0])]
(i, j) = (0, 1)
while j < m:
	if dist[p[i] - 1][p[j] - 1] < j - i:
		res += 1
		i = j - 1
		rt.append(str(p[j - 1]))
	j += 1
rt.append(str(p[-1]))
print(res)
print(' '.join(rt))


import os, sys
from io import BytesIO, IOBase

def main():
	inf = float('inf')
	n = int(input())
	dis = [[inf] * n for _ in range(n)]
	adj = [list(map(int, input().strip())) for _ in range(n)]
	for i in range(n):
		dis[i][i] = 0
	for i in range(n):
		for j in range(n):
			if adj[i][j]:
				dis[i][j] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
	m = int(input())
	p = list(map(lambda xx: int(xx) - 1, input().split()))
	prev = [-1] * m
	dp = [1] + [inf] * (m - 1)
	for i in range(1, m):
		(v, mini, ind) = (p[i], inf, -1)
		for j in range(n):
			z = dis[j][v]
			if z > i or p[i - z] != j or dp[i - z] >= mini:
				continue
			(mini, ind) = (dp[i - z], i - z)
		(dp[i], prev[i]) = (mini + 1, ind)
	print(dp[-1])
	(ans, x) = ([], m - 1)
	while x != -1:
		ans.append(p[x] + 1)
		x = prev[x]
	print(*reversed(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdout
import heapq
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : list(map(int, input().split()))
DBG = True
BIG = 999999999
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)

def setc2c():
	for c1 in range(n):
		dist = [BIG] * n
		dist[c1] = 0
		hp = [(0, c1)]
		while len(hp) > 0:
			(curlen, curloc) = heapq.heappop(hp)
			if curlen > dist[curloc]:
				continue
			for nxtloc in dst[curloc]:
				newdist = dist[curloc] + 1
				if newdist < dist[nxtloc]:
					dist[nxtloc] = newdist
					heapq.heappush(hp, (newdist, nxtloc))
		for c2 in range(n):
			c2c[c1][c2] = dist[c2]
n = inn()
dst = [[] for i in range(n)]
c2c = [[0] * n for i in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			dst[i].append(j)
m = inn()
p = [x - 1 for x in inl()]
setc2c()
v = [p[0]]
curv = p[0]
curi = 0
for i in range(1, m):
	if c2c[curv][p[i]] < i - curi:
		v.append(p[i - 1])
		curv = p[i - 1]
		curi = i - 1
v.append(p[m - 1])
k = len(v)
print(k)
for i in range(k):
	printn((' ' if i > 0 else '') + str(v[i] + 1))
print('')


def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
n = int(input())
g = [list(input()) for _ in range(n)]
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if g[i][j] == '1':
			d[i][j] = 1
warshall_floyd(d)
m = int(input())
arr = list(map(int, input().split()))
for i in range(m):
	arr[i] -= 1
ans = [arr[0]]
pos1 = 0
pos2 = 1
pos3 = 2
for i in range(m - 2):
	(a, b, c) = (arr[pos1], arr[pos2], arr[pos3])
	if a != c:
		if d[a][b] + d[b][c] > d[a][c]:
			ans.append(b)
			pos1 = pos2
			pos2 = pos1 + 1
			pos3 = pos2 + 1
		else:
			pos2 += 1
			pos3 += 1
	else:
		ans.append(b)
		pos1 = pos2
		pos2 = pos1 + 1
		pos3 = pos2 + 1
ans.append(arr[-1])
l = len(ans)
for i in range(l):
	ans[i] += 1
print(l)
print(*ans)


from collections import defaultdict

def bfs(root):
	bool = [False] * (n + 1)
	queue = [root]
	bool[root] = True
	level = defaultdict(int)
	level[root] = 0
	while queue:
		z = queue.pop(0)
		for i in hash[z]:
			if bool[i] == False:
				bool[i] = True
				level[i] += 1 + level[z]
				queue.append(i)
	return level
hash = defaultdict(list)
n = int(input())
l = []
for i in range(n):
	k = list(input())
	l.append(k)
for i in range(n):
	for j in range(n):
		if l[i][j] == '1':
			hash[i + 1].append(j + 1)
n1 = int(input())
la = list(map(int, input().split()))
root = la[0]
full = {}
for i in range(1, n + 1):
	full[i] = bfs(i)
ans = [la[0]]
j = 0
while j < len(la):
	k = j + 1
	while k < len(la):
		if full[la[j]][la[k]] == k - j:
			k += 1
		else:
			break
	if k == j:
		ans.append(la[j])
		j += 1
	else:
		ans.append(la[k - 1])
		j = k - 1
		if j == len(la) - 1:
			break
print(len(ans))
print(*ans)


import sys
input = sys.stdin.readline

def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
n = int(input())
A = [input()[:-1] for _ in range(n)]
m = int(input())
if m == 2:
	p = list(map(int, input().split()))
	print(2)
	print(*p)
	exit()
p = list(map(lambda x: x - 1, map(int, input().split())))
d = [[10 ** 18] * n for _ in range(n)]
for i in range(n):
	d[i][i] = 0
for i in range(n):
	for j in range(n):
		if A[i][j] == '1':
			d[i][j] = 1
d = warshall_floyd(d)
s = 0
t = 2
ans = [p[s]]
while t < m:
	if t - s > d[p[s]][p[t]]:
		ans.append(p[t - 1])
		s = t - 1
	t += 1
ans.append(p[-1])
ans = list(map(lambda x: x + 1, ans))
print(len(ans))
print(*ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
n = inp()
g = [[INF] * n for _ in range(n)]
for i in range(n):
	s = sys.stdin.readline()
	s = s[:n]
	for j in range(n):
		if i == j:
			g[i][j] = 0
		if s[j] == '1':
			g[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
m = inp()
p = inpl()
l = 0
r = 1
res = [p[0]]
while r < m:
	ln = r + 1 - l
	if r + 1 == m:
		res.append(p[r])
		break
	L = p[l] - 1
	R = p[r + 1] - 1
	if g[L][R] != ln:
		res.append(p[r])
		l = r
	r += 1
print(len(res))
print(*res)


n = int(input())
dis = []
for i in range(n):
	a = list(map(int, input()))
	for j in range(n):
		if a[j] == 0:
			a[j] = 200
	a[i] = 0
	dis.append(a)
for k in range(n):
	for i in range(n):
		for j in range(n):
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
m = int(input())
a = list(map(int, input().split()))
ans = [0]
for i in range(1, m):
	if dis[a[ans[-1]] - 1][a[i] - 1] != i - ans[-1]:
		ans.append(i - 1)
ans.append(m - 1)
print(len(ans))
for i in ans:
	print(a[i], end=' ')
print()


gi = lambda : list(map(int, input().split()))
(n,) = gi()
g = [list(map(int, list(input()))) for _ in range(n)]
(lenp,) = gi()
p = gi()
ans = p[:]
lenans = lenp
k = 1
while k < lenp - 1:
	if g[ans[k - 1] - 1][ans[k + 1] - 1] == 0 and ans[k - 1] != ans[k + 1]:
		p[k] = -1
		ans[k] = ans[k - 1]
		lenans -= 1
		k += 1
	k += 1
print(lenans)
for k in range(lenp):
	if p[k] != -1:
		print(ans[k], end=' ')


from heapq import heapify, heappush as hpush, heappop as hpop
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
	s = input()
	for j in range(N):
		if s[j] == '1':
			X[i].append((j, 1))

def dijkstra(n, E, i0=0):
	h = [[0, i0]]
	D = [-1] * n
	done = [0] * n
	D[i0] = 0
	while h:
		(d, i) = hpop(h)
		done[i] = 1
		for (j, w) in E[i]:
			nd = d + w
			if D[j] < 0 or D[j] >= nd:
				if done[j] == 0:
					hpush(h, [nd, j])
					D[j] = nd
	return [d if d >= 0 else 1 << 50 for d in D]
Y = []
for i in range(N):
	Y.append(dijkstra(N, X, i))
M = int(input())
V = [int(a) - 1 for a in input().split()]
a = 0
b = 1
t = Y[V[a]][V[b]]
ANS = [V[a] + 1]
while b < M:
	if Y[V[a]][V[b]] < t:
		a = b - 1
		ANS.append(V[a] + 1)
		t = Y[V[a]][V[b]]
	elif b == M - 1:
		break
	else:
		t += Y[V[b]][V[b + 1]]
		b += 1
ANS.append(V[M - 1] + 1)
print(len(ANS))
print(*ANS)


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, list(input()))))
p = int(input())
b = list(map(int, input().split()))
for i in range(n):
	for j in range(n):
		if i != j and a[i][j] == 0:
			a[i][j] = 10 ** 10
for k in range(n):
	for i in range(n):
		for j in range(n):
			a[i][j] = min(a[i][j], a[i][k] + a[k][j])
c = []
for i in range(p):
	if i == 0 or i == p - 1:
		c.append(b[i])
		continue
	x = c[-1] - 1
	if a[x][b[i] - 1] + a[b[i] - 1][b[i + 1] - 1] == a[x][b[i + 1] - 1]:
		continue
	c.append(b[i])
print(len(c))
print(*c)


N = int(1000000.0 + 3)
n = int(input())
dis = list(([N] * n for _ in range(n)))
for i in range(n):
	for j in range(n):
		if i == j:
			dis[i][j] = 0
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			dis[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
m = int(input())
arr = list(map(int, input().split()))
for i in range(m):
	arr[i] -= 1
(e, cnt) = (m - 1, 0)
for i in range(m - 3, -1, -1):
	(x, y, z) = (arr[i], arr[i + 1], arr[e])
	if dis[x][z] < dis[x][y] + dis[y][z]:
		e = i + 1
	else:
		arr[i + 1] = -1
		cnt += 1
print(m - cnt)
print(*[i + 1 for i in arr if i != -1])


from collections import deque
N = int(input())
Edge = [list(map(int, input().strip())) for _ in range(N)]
dist = []
inf = 10 ** 9
for i in range(N):
	d = [inf] * N
	d[i] = 0
	Q = deque([i])
	unused = set(range(N))
	unused.remove(i)
	while Q:
		vn = Q.pop()
		for vf in unused.copy():
			if Edge[vn][vf]:
				unused.remove(vf)
				d[vf] = 1 + d[vn]
				Q.appendleft(vf)
	dist.append(d)
M = int(input())
V = tuple([int(x) - 1 for x in input().split()])
Ans = [V[0]]
for v in V[1:]:
	while len(Ans) > 1 and dist[Ans[-2]][Ans[-1]] + dist[Ans[-1]][v] == dist[Ans[-2]][v]:
		Ans.pop()
	Ans.append(v)
Ans = [a + 1 for a in Ans]
print(len(Ans))
print(*Ans)


def floyd(n, dist):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
n = int(input())
graph = [[0] * n for _ in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		graph[i][j] = int(s[j]) if s[j] != '0' or i == j else float('+inf')
m = int(input())
path = [x - 1 for x in list(map(int, input().split()))]
floyd(n, graph)
ans = [path[0]]
last = 0
for i in range(1, m):
	if i - last > graph[ans[-1]][path[i]]:
		ans.append(path[i - 1])
		last = i - 1
ans.append(path[-1])
print(len(ans))
print(*[x + 1 for x in ans])


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
n = int(input())
inf = 200
g = []
g = [[0] * n for i in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		g[i][j] = 1 if int(s[j]) else inf
		if i == j:
			g[i][j] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[k][j] + g[i][k])
m = int(input())
p = list(map(int, input().split()))
ans = [p[0]]
for i in range(1, m - 1):
	if g[ans[-1] - 1][p[i + 1] - 1] - g[ans[-1] - 1][p[i] - 1] != 1:
		ans.append(p[i])
ans.append(p[-1])
print(str(len(ans)))
print('\n')
print(' '.join((str(i) for i in ans)))


n = int(input())
a = [0]
for i in range(n):
	a.append(list(input()))
x = int(input())
b = list(map(int, input().split()))
if x == 2:
	print(2)
	print(*b)
	exit()
st = [b[0]]
st1 = [b[0]]
k = b[1]
for i in range(1, n + 1):
	a[i][i - 1] = '1'
pr = []
pr.append(b[0])
for j in range(2, x):
	for l in st1:
		if a[l][b[j] - 1] == '1':
			st.append(k)
			st = [k]
			st1 = [k]
			pr.append(k)
			k = b[j]
			break
	else:
		st1.append(b[j])
		k = b[j]
pr.append(b[-1])
print(len(pr))
print(*pr)


import sys
input = sys.stdin.readline
INF = 10 ** 12
n = int(input())
edge = [[] for _ in range(n)]
for i in range(n):
	line = input().rstrip()
	for (j, ch) in enumerate(line):
		if i == j:
			edge[i].append(0)
		elif ch == '1':
			edge[i].append(1)
		else:
			edge[i].append(INF)
m = int(input())
a = [int(item) for item in input().split()]
if m == 2:
	print(2)
	print(' '.join([str(item) for item in a]))
	exit()
for k in range(n):
	for i in range(n):
		for j in range(n):
			edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j])
frm_id = 0
mid_id = 1
to_id = 2
ans_num = 0
ans = [a[frm_id]]
ans_num += 1
while to_id < len(a):
	frm = a[frm_id] - 1
	mid = a[mid_id] - 1
	to = a[to_id] - 1
	if frm == to or not edge[frm][mid] + edge[mid][to] == edge[frm][to]:
		ans.append(mid + 1)
		ans_num += 1
		frm_id = mid_id
		to_id += 1
		mid_id += 1
	else:
		to_id += 1
		mid_id += 1
ans.append(to + 1)
ans_num += 1
print(ans_num)
print(' '.join([str(item) for item in ans]))


n = int(input())
G = [[] for _ in range(n)]
for i in range(n):
	l = input()
	for j in range(n):
		if l[j] == '1':
			G[i].append(j)
ds = [[-1] * n for _ in range(n)]
for i in range(n):
	ds[i][i] = 0
	l = [i]
	while len(l) > 0:
		l2 = []
		for j in l:
			for k in G[j]:
				if ds[i][k] == -1:
					ds[i][k] = ds[i][j] + 1
					l2.append(k)
		l = l2
m = int(input())
p = list(map(int, input().split()))
res = 2
vs = [str(p[0])]
(i, j) = (0, 1)
while j < m:
	if ds[p[i] - 1][p[j] - 1] < j - i:
		res += 1
		i = j - 1
		vs.append(str(p[j - 1]))
	j += 1
vs.append(str(p[-1]))
print(res)
print(' '.join(vs))


from sys import stdin
input = stdin.readline

def floyd(a, n):
	for i in range(n):
		for j in range(n):
			if i != j and a[i][j] == 0:
				a[i][j] = 10 ** 18
	for k in range(n):
		for i in range(n):
			for j in range(n):
				a[i][j] = min(a[i][j], a[i][k] + a[k][j])
n = int(input())
a = []
for i in range(n):
	r = list(input())
	a.append(list(map(int, r[:len(r) - 1])))
floyd(a, n)
m = int(input())
t = list(map(int, input().split()))
s = []
for i in range(m):
	if i == 0 or i == m - 1:
		s.append(t[i])
		continue
	x = s[-1] - 1
	if a[x][t[i] - 1] + a[t[i] - 1][t[i + 1] - 1] == a[x][t[i + 1] - 1]:
		continue
	s.append(t[i])
print(len(s))
print(*s)


n = int(input())
adj = []
for i in range(n):
	adj.append(str(input()))
dist = [[999999999999999999999999999 for i in range(n)] for j in range(n)]
for i in range(n):
	for j in range(n):
		if i == j:
			dist[i][j] = 0
		elif adj[i][j] == '1':
			dist[i][j] = 1
m = int(input())
p = list(map(int, input().split()))
for i in range(m):
	p[i] -= 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
last_i = 0
ans = []
ans.append(0)
for i in range(1, m - 1):
	if dist[p[last_i]][p[i + 1]] != i + 1 - last_i:
		last_i = i
		ans.append(i)
print(len(ans) + 1)
for i in ans:
	print(p[i] + 1, end=' ')
print(p[-1] + 1)


from sys import setcheckinterval, stdin
setcheckinterval(1000)
iin = lambda : int(stdin.readline())
lin = lambda : list(map(int, stdin.readline().split()))

def BFS(s, adj):
	level = {s: 0}
	parent = {s: None}
	lv = 1
	u = [s]
	while u:
		nextu = []
		for i in u:
			for v in adj[i]:
				if v not in parent:
					parent[v] = i
					level[v] = lv
					nextu.append(v)
		lv += 1
		u = nextu.copy()
	return level
n = iin()
adj = [[] for i in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			adj[i].append(j)
m = iin()
p = lin()
sol = dict()
pp = [BFS(i, adj) for i in range(n)]
i = 1
x = 0
ans = [p[0]]
while i < m:
	if pp[p[x] - 1][p[i] - 1] == i - x:
		i += 1
	else:
		ans.append(p[i - 1])
		x = i - 1
ans.append(p[-1])
print(len(ans))
print(*ans)


import math
import sys
import collections

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
INF = 1000
n = ii()
d = [[0] * n for i in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			d[i][j] = int(s[j])
		elif i != j:
			d[i][j] = INF
		else:
			d[i][j] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
m = ii()
path = li()
ans = [path[0]]
prev = 0
for i in range(1, m):
	if d[path[prev] - 1][path[i] - 1] < i - prev:
		ans.append(path[i - 1])
		prev = i - 1
ans.append(path[-1])
print(len(ans))
print(' '.join(map(str, ans)))


import math

def concat_paths(p1, p2):
	result = []
	for pp1 in p1:
		for pp2 in p2:
			result.append(pp1 + pp2[1:])
	return result

def main():
	n = int(input())
	d = []
	for i in range(n):
		dd = []
		s = input()
		for j in range(n):
			if s[j] == '0':
				dd.append(False)
			else:
				dd.append(True)
		d.append(dd)
	m = int(input())
	p = [int(x) for x in input().split()]
	dist = []
	for i in range(n):
		ddist = []
		for j in range(n):
			ddist.append([])
		dist.append(ddist)
	for i in range(n):
		for j in range(n):
			if d[i][j]:
				dist[i][j].append([i, j])
	for k in range(n):
		for i in range(n):
			if i == k:
				continue
			for j in range(n):
				if j == i or j == k:
					continue
				mindist = -1
				if len(dist[i][j]) > 0:
					mindist = len(dist[i][j][0])
				newdist = -1
				if len(dist[i][k]) > 0 and len(dist[k][j]) > 0:
					newdist = len(dist[i][k][0]) + len(dist[k][j][0]) - 1
				if newdist > 0:
					if newdist == mindist:
						dist[i][j] += concat_paths(dist[i][k], dist[k][j])
					elif mindist < 0 or mindist > newdist:
						dist[i][j] = concat_paths(dist[i][k], dist[k][j])
	trie = dict()
	for i in range(n):
		t = dict()
		for j in range(n):
			for path in dist[i][j]:
				tt = t
				for ind in range(1, len(path)):
					if path[ind] in tt:
						ttt = tt[path[ind]]
						tt = ttt
					else:
						tt[path[ind]] = dict()
						tt = tt[path[ind]]
		trie[i] = t
	for i in range(len(p)):
		p[i] -= 1
	result = [p[0]]
	now = trie[p[0]]
	ind = 0
	while ind < len(p):
		v = set()
		while ind + 1 < len(p) and p[ind + 1] in now and (p[ind + 1] not in v):
			now = now[p[ind + 1]]
			v.add(p[ind + 1])
			ind += 1
		result.append(p[ind])
		now = trie[p[ind]]
		if ind == len(p) - 1:
			break
	print(len(result))
	print(' '.join([str(x + 1) for x in result]))
main()


nodes = int(input())
dist = {}
for i in range(1, nodes + 1):
	for j in range(1, nodes + 1):
		dist[i, j] = float('inf')
for i in range(nodes):
	lst = input()
	for j in range(len(lst)):
		if lst[j] == '1':
			dist[i + 1, j + 1] = 1
n = input()
path = [int(x) for x in input().split()]
for n in range(1, nodes + 1):
	dist[n, n] = 0
for i in range(1, nodes + 1):
	for j in range(1, nodes + 1):
		for k in range(1, nodes + 1):
			if dist[j, k] > dist[j, i] + dist[i, k]:
				dist[j, k] = dist[j, i] + dist[i, k]
final = []
final.append(0)
for i in range(1, len(path)):
	if dist[path[final[-1]], path[i]] < i - final[-1]:
		final.append(i - 1)
final.append(len(path) - 1)
print(len(final))
print(' '.join([str(path[x]) for x in final]))


n = int(input())
nei = []
for _ in range(n):
	s = input()
	nei.append(list((int(c) for c in s)))
m = int(input())
p = list([int(x) - 1 for x in input().split()])
shortest = []
for i in range(n):
	vals = []
	for (j, con) in enumerate(nei[i]):
		if i == j:
			vals.append(0)
		elif con:
			vals.append(1)
		else:
			vals.append(10 ** 6)
	shortest.append(vals)
for k in range(n):
	for i in range(n):
		for j in range(n):
			shortest[i][j] = min(shortest[i][j], shortest[i][k] + shortest[k][j])
seq = [p[0]]
dist = 0
for (prev, cur) in zip(p, p[1:]):
	dist += shortest[prev][cur]
	if shortest[seq[-1]][cur] < dist:
		dist = shortest[prev][cur]
		seq.append(prev)
seq.append(p[-1])
print(len(seq))
print(*[val + 1 for val in seq])


MOD = 10 ** 9 + 7
I = lambda : list(map(int, list(input())))
n = int(input())
g = []
for i in range(n):
	g.append(I())
m = int(input())
p = [int(i) - 1 for i in input().split()]
d = g[:]
for i in range(n):
	for j in range(n):
		if not d[i][j] and i != j:
			d[i][j] = 1000
for i in range(n):
	for j in range(n):
		for k in range(n):
			d[j][k] = min(d[j][k], d[j][i] + d[i][k])
ans = [1] * m
if m == 2:
	print(len(p))
	print(*[i + 1 for i in p])
	exit()
f = m - 3
l = m - 1
while f >= 0 and f + 1 < l:
	k = d[p[f]][p[l]]
	if k == l - f:
		ans[f + 1] = 0
		f -= 1
	else:
		l -= 1
		while f + 1 == l or ans[l] == 0:
			if f + 1 == l:
				f -= 1
			else:
				l -= 1
print(sum(ans))
for i in range(m):
	if ans[i]:
		print(p[i] + 1, end=' ')


n = int(input())
a = []
t = 0
b = 0
for i in range(n):
	t = input()
	b = []
	for j in range(n):
		b.append(int(t[j]))
		if i != j and t[j] == '0':
			b[j] = 10 ** 9
	a.append(b)
for k in range(n):
	for i in range(n):
		for j in range(n):
			a[i][j] = min(a[i][j], a[i][k] + a[k][j])
m = int(input())
p = list(map(int, input().split()))
i = 1
maps = [p[0]]
while i < m - 1:
	if a[maps[-1] - 1][p[i] - 1] + 1 != a[maps[-1] - 1][p[i + 1] - 1]:
		maps.append(p[i])
	i += 1
maps.append(p[m - 1])
print(len(maps))
print(*maps)


def floyd_warshall(graph):
	n = len(graph)
	dist = [[float('inf') for _ in range(n)] for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if i == j:
				dist[i][j] = 0
			elif graph[i][j]:
				dist[i][j] = 1
	for thru in range(n):
		for i in range(n):
			for j in range(n):
				candidate = dist[i][thru] + dist[thru][j]
				if candidate < dist[i][j]:
					dist[i][j] = candidate
	return dist

def solve(graph, seq):
	dist = floyd_warshall(graph)
	result = [seq[0]]
	count = 0
	for (i, current) in enumerate(seq):
		if dist[result[-1] - 1][current - 1] < count:
			result.append(seq[i - 1])
			count = 2
		else:
			count += 1
	result.append(seq[-1])
	return result
n = int(input())
graph = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
	row = input()
	for j in range(n):
		graph[i][j] = int(row[j])
m = int(input())
seq = list(map(int, input().split()))[:m]
solution = solve(graph, seq)
print(len(solution))
print(' '.join([str(x) for x in solution]))


def naiveSolve():
	return

def floyd_warshall(n, edges):
	dist = [[0 if i == j else float('inf') for i in range(n)] for j in range(n)]
	pred = [[None] * n for _ in range(n)]
	for (u, v, d) in edges:
		dist[u][v] = d
		pred[u][v] = u
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dist[i][k] + dist[k][j] < dist[i][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
					pred[i][j] = pred[k][j]
	return (dist, pred)
from collections import deque

def main():
	n = int(input())
	adj1 = []
	for _ in range(n):
		adj1.append(input())
	m = int(input())
	p = readIntArr()
	for i in range(m):
		p[i] -= 1
	edges = []
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if adj1[i][j] == '1':
				edges.append([i, j, 1])
	(dist, _) = floyd_warshall(n, edges)
	q = deque()
	q.append(0)
	prevNode = [-1] * m
	while q:
		node = q.popleft()
		for nex in range(node + 1, min(m, node + 101)):
			if prevNode[nex] != -1:
				continue
			if nex - node == dist[p[node]][p[nex]]:
				prevNode[nex] = node
				q.append(nex)
	pathReversed = [m - 1]
	node = m - 1
	while node != 0:
		node = prevNode[node]
		pathReversed.append(node)
	path = reversed(pathReversed)
	ans = [p[x] + 1 for x in path]
	print(len(ans))
	oneLineArrayPrint(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
from collections import defaultdict
graph = defaultdict(list)
n = int(sys.stdin.readline())
dp = [[0 for _ in range(n)] for x in range(n)]
for i in range(n):
	s = sys.stdin.readline()[:-1]
	for j in range(n):
		if s[j] == '1':
			dp[i][j] = 1
		else:
			dp[i][j] = float('inf')
for i in range(n):
	dp[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			if dp[i][k] + dp[k][j] < dp[i][j]:
				dp[i][j] = dp[i][k] + dp[k][j]
	nex = [[i for i in dp[j]] for j in range(n)]
m = int(sys.stdin.readline())
p = list(map(int, sys.stdin.readline().split()))
ans = [p[0]]
last = 0
for i in range(1, m):
	if dp[ans[-1] - 1][p[i] - 1] == i - last:
		pass
	else:
		last = i - 1
		ans.append(p[i - 1])
(i, last) = (1, 0)
ans.append(p[-1])
print(len(ans))
print(*ans)


n = int(input())
mat = []
for _ in range(n):
	mat.append([int(i) for i in input()])
short = []
for i in range(n):
	short.append([-1] * n)
for i in range(n):
	layer = {i}
	cnt = 1
	sht = short[i]
	sht[i] = 0
	while len(layer) > 0:
		new = set()
		for v in layer:
			for j in range(n):
				if mat[v][j] and sht[j] == -1:
					sht[j] = cnt
					new.add(j)
		cnt += 1
		layer = new
ln = int(input())
path = [int(i) - 1 for i in input().split()]
lastv = path[0]
ans = [str(lastv + 1)]
dist = 1
for i in range(1, ln):
	v1 = path[i]
	if dist != short[lastv][v1]:
		dist = 1
		lastv = path[i - 1]
		ans.append(str(lastv + 1))
	dist += 1
ans.append(str(path[-1] + 1))
print(len(ans))
print(' '.join(ans))


from collections import defaultdict
from math import inf

class Graph:

	def __init__(self, n):
		self.Matrix = [[inf for j in range(n)] for i in range(n)]
		self.vertices = n

	def addEdge(self, Matrix):
		for i in range(self.vertices):
			for j in range(self.vertices):
				if Matrix[i][j] == 1:
					self.Matrix[i][j] = 1

	def Floyd_Warshall(self):
		for i in range(self.vertices):
			self.Matrix[i][i] = 0
		for k in range(self.vertices):
			for i in range(self.vertices):
				for j in range(self.vertices):
					self.Matrix[i][j] = min(self.Matrix[i][j], self.Matrix[i][k] + self.Matrix[k][j])

	def distance(self, a, b):
		return self.Matrix[a][b]

	def show(self):
		printMatrix(self.Matrix)

def printMatrix(matrix):
	s = [[str(e) for e in row] for row in matrix]
	lens = [max(map(len, col)) for col in zip(*s)]
	fmt = '\t'.join(('{{:{}}}'.format(x) for x in lens))
	table = [fmt.format(*row) for row in s]
	print('_________________')
	print('\n'.join(table))
	print('`````````````````')
N = int(input())
G = Graph(N)
Matrix = []
for i in range(N):
	temp = input()
	t = [int(i) for i in temp]
	Matrix.append(t)
G.addEdge(Matrix)
G.Floyd_Warshall()
m = int(input())
List = [int(x) for x in input().split()]
ans = [List[0]]
last = 1
for i in range(1, m):
	if G.distance(ans[-1] - 1, List[i] - 1) < i + 1 - last:
		ans.append(List[i - 1])
		last = i
ans.append(List[-1])
print(len(ans))
print(*ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
n = int(input())
adj = []
for s in range(n):
	v0 = [int(k) for k in input()]
	adj.append(v0)
m = int(input())
vals = [int(k) - 1 for k in input().split()]
dist = [[0 for s in range(n)] for b in range(n)]
for b in range(n):
	queue = deque([b])
	vis = set([b])
	cv = 0
	pr = 1
	while len(queue) > 0:
		v0 = queue.popleft()
		for s in range(len(adj[v0])):
			if adj[v0][s] == 1 and (not s in vis):
				queue.append(s)
				vis.add(s)
		dist[b][v0] = cv
		pr -= 1
		if pr == 0:
			cv += 1
			pr += len(queue)
ans = [vals[0]]
prev = 0
for s in range(1, len(vals)):
	d1 = s - prev
	d2 = dist[ans[-1]][vals[s]]
	if d1 > d2:
		ans.append(vals[s - 1])
		prev = s - 1
if prev != m - 1:
	ans.append(vals[-1])
ans = [k + 1 for k in ans]
print(len(ans))
print(*ans)


from sys import stdin
input = stdin.readline
a = []
n = int(input())
for _ in range(n):
	s = input()
	a.append(s)
m = int(input())
b = list(map(int, input().split()))
c = [0] * m
k = 0
for i in range(1, m - 1):
	if k == 1:
		k = 0
		continue
	if a[b[i - 1] - 1][b[i + 1] - 1] == '0' and b[i - 1] != b[i + 1]:
		k = 1
		c[i] = 1
print(c.count(0))
for i in range(m):
	if c[i] == 0:
		print(b[i], end=' ')


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
INF = 1000000000.0
ad = []

def floydWarshall(V):
	for k in range(V):
		for i in range(V):
			for j in range(V):
				ad[i][j] = min(ad[i][j], ad[i][k] + ad[k][j])
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
for _ in range(t):
	n = int(input())
	for i in range(n):
		l = list(input())
		l = l[:-1]
		for i in range(n):
			if l[i] == 48:
				l[i] = int(INF)
			else:
				l[i] = 1
		ad.append(l)
	floydWarshall(n)
	for i in range(n):
		ad[i][i] = int(INF)
	m = int(input())
	s = []
	l = [int(x) for x in input().split()]
	prev = l[0]
	i = 0
	while i < m:
		j = i + 1
		while j < m:
			if j - i == ad[l[i] - 1][l[j] - 1]:
				j += 1
				continue
			else:
				break
		s.append(l[i])
		if j == m:
			s.append(l[j - 1])
			break
		i = j - 1
	print(len(s))
	print(*s)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = [list(map(lambda x: 1 if x == '1' else 101, input().rstrip())) for _ in range(n)]
	for i in range(n):
		a[i][i] = 0
	m = int(input())
	b = list(map(int, input().split()))
	for k in range(n):
		for i in range(n):
			for j in range(n):
				a[i][j] = min(a[i][j], a[i][k] + a[k][j])
	(ans, i) = ([], 0)
	while i < m:
		j = i + 1
		while j < m and j - i == a[b[i] - 1][b[j] - 1]:
			j += 1
		ans.append(b[i])
		if j == m:
			break
		i = j - 1
	ans.append(b[-1])
	print(len(ans))
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def bfs(s):
	q = [s]
	visited[s] = True
	while q:
		s = q.pop(0)
		for i in range(n):
			if adj[s][i] == '1':
				if not visited[i]:
					paths[j][i] = paths[j][s] + 1
					visited[i] = True
					q.append(i)
n = int(input())
adj = [None] * n
for i in range(n):
	adj[i] = input()
m = int(input())
p = [int(o) for o in input().split()]
paths = [dict() for i in range(n)]
for j in range(n):
	visited = [False] * n
	paths[j][j] = 0
	bfs(j)
stack = [p[0] - 1]
ans = [p[0]]
cur = 1
while cur < m - 1:
	if ans[-1] == p[cur + 1]:
		ans.append(p[cur])
	elif paths[ans[-1] - 1][p[cur] - 1] + paths[p[cur] - 1][p[cur + 1] - 1] > paths[ans[-1] - 1][p[cur + 1] - 1]:
		ans.append(p[cur])
	cur += 1
ans.append(p[-1])
print(len(ans))
print(*ans)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
dis = [[1000000000] * 101 for _i in range(101)]
n = int(rd())
for i in range(n + 1):
	dis[i][i] = 0
for i in range(1, n + 1):
	s = str(rd().strip())
	for j in range(n):
		if s[j] == '1':
			dis[i][j + 1] = 1
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
m = int(rd())
p = list(rrd())
ans = []
s = 0
pre = 0
l = 0
for i in p:
	if len(ans) == 0:
		s = i
		pre = i
		ans.append(i)
		continue
	if dis[s][i] == l + 1:
		pre = i
		l += 1
		continue
	else:
		ans.append(pre)
		s = pre
		pre = i
		l = 1
if s != pre:
	ans.append(pre)
print(len(ans))
print(*ans)


n = int(input())
inf = 10 ** 9
matrix = [list(map(lambda x: int(x) or inf, input())) for _ in range(n)]
for k in range(n):
	for i in range(n):
		for j in range(n):
			if matrix[i][j] > matrix[i][k] + matrix[k][j]:
				matrix[i][j] = matrix[i][k] + matrix[k][j]
for i in range(n):
	matrix[i][i] = 0
m = int(input())
path = list(map(lambda x: int(x) - 1, input().split()))
ans = [path[0]]
dist = 0
for i in range(1, m):
	dist += 1
	if dist != matrix[ans[-1]][path[i]]:
		ans.append(path[i - 1])
		dist = 1
ans.append(path[-1])
print(len(ans))
print(*map(lambda x: x + 1, ans))


import sys, atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda : inp.readline().decode('ascii')
buf = BytesIO()
sys.stdout.write = lambda s: buf.write(s.encode('ascii'))
atexit.register(lambda : sys.__stdout__.buffer.write(buf.getvalue()))
n = int(input())
A = [[int(c) for c in input().strip()] for i in range(n)]

def out(i):
	return sum(A[i])
m = int(input())
P = [int(x) - 1 for x in input().split()]

def floyd_warshall(n, edges):
	dist = [[0 if i == j else float('inf') for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			if A[i][j]:
				dist[i][j] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dist[i][k] + dist[k][j] < dist[i][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
	return dist
dist = floyd_warshall(n, A)
Q = [P[0]]
i = 1
d = 1
while i < m:
	while i < m and dist[Q[-1]][P[i]] >= d:
		i += 1
		d += 1
	Q.append(P[i - 1])
	d = 1
print(len(Q))
print(*[x + 1 for x in Q])


R = lambda : map(int, input().split())
n = int(input())
L = []
for i in range(n):
	L.append([int(j) for j in input()])
for i in range(n):
	for j in range(n):
		if i != j and L[i][j] == 0:
			L[i][j] = 10 ** 9
for k in range(n):
	for i in range(n):
		for j in range(n):
			L[i][j] = min(L[i][j], L[i][k] + L[k][j])
m = int(input())
A = list(R())
i = 1
res = [A[0]]
while i < m - 1:
	if L[res[-1] - 1][A[i] - 1] + 1 != L[res[-1] - 1][A[i + 1] - 1]:
		res.append(A[i])
	i += 1
res.append(A[m - 1])
print(len(res))
print(*res)


n = int(input())
INF = 10 ** 18
g = [[INF for i in range(n)] for _ in range(n)]
for i in range(n):
	s = input().rstrip()
	for j in range(n):
		if s[j] == '1':
			g[i][j] = 1
	g[i][i] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			g[i][j] = min(g[i][j], g[i][k] + g[k][j])
m = int(input())
p = [int(i) - 1 for i in input().split()]
ptr = 1
ans = [p[0]]
while ptr + 1 < len(p):
	s = ans[-1]
	if g[s][p[ptr]] + 1 != g[s][p[ptr + 1]]:
		ans.append(p[ptr])
	ptr += 1
ans.append(p[-1])
print(len(ans))
for i in ans:
	print(i + 1, end=' ')


n = int(input())
g = []

def bfs(src):
	q = []
	dist = []
	visited = []
	for i in range(n):
		visited.append(False)
		dist.append(1e+18)
	dist[src] = 0
	visited[src] = True
	q.append(src)
	while q:
		src = q.pop(0)
		for i in g[src]:
			if visited[i] == False:
				visited[i] = True
				dist[i] = dist[src] + 1
				q.append(i)
	return dist
for i in range(n):
	t = input()
	g.append([])
	for j in range(len(t)):
		if t[j] == '1':
			g[i].append(j)
m = int(input())
p = list(map(int, input().split()))
for i in range(m):
	p[i] -= 1
dist = []
for i in range(n):
	dist.append(bfs(i))
ans = [p[0]]
k = 0
for i in range(1, m):
	if dist[ans[-1]][p[i]] == 1e+18 or dist[ans[-1]][p[i]] < i - k:
		ans.append(p[i - 1])
		k = i - 1
ans.append(p[-1])
l = len(ans)
for i in range(l):
	ans[i] += 1
	ans[i] = str(ans[i])
print(len(ans))
print(' '.join(ans))


import sys
MOD = pow(10, 9) + 7
INF = 999999999999999

def IN(f=0):
	if f == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())

def floydWarshall(graph, V):
	dist = []
	for i in range(V):
		dist.append(graph[i].copy())
	for k in range(V):
		for i in range(V):
			for j in range(V):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist
n = int(input())
a = []
for i in range(n):
	t = list(input())
	t = [int(j) for j in t]
	a.append(t)
for i in range(n):
	for j in range(n):
		if i != j and a[i][j] == 0:
			a[i][j] = INF
f = floydWarshall(a, n)
m = IN(1)
s = IN()
p = [s[0]]
i = 1
j = 0
while i < len(s) - 1:
	ab = f[p[j] - 1][s[i] - 1]
	bc = f[s[i] - 1][s[i + 1] - 1]
	ac = f[p[j] - 1][s[i + 1] - 1]
	if ab + bc != ac:
		p.append(s[i])
		j += 1
		i += 1
	else:
		i += 1
p.append(s[-1])
print(len(p))
print(*p)


from collections import deque
n = int(input())
graph = [list([bit == '1' for bit in list(input())]) for _ in range(n)]
m = int(input())
way = list([int(i) - 1 for i in input().split()])

def dfs(start):
	queue = deque([start])
	d = [-1] * n
	d[start] = 0
	while len(queue) != 0:
		u = queue[0]
		queue.popleft()
		for v in range(n):
			if graph[u][v] and d[v] == -1:
				d[v] = d[u] + 1
				queue.append(v)
	return d
minpath = list(map(dfs, list(range(n))))
good = [way[0]]
checkp = way[0]
for i in range(1, m):
	prev = way[i - 1]
	if minpath[checkp][way[i]] != minpath[checkp][prev] + 1:
		good.append(prev)
		checkp = prev
good.append(way[-1])
print(len(good))
print(' '.join([str(p + 1) for p in good]))


from collections import deque
n = int(input())
adj_m = ['0' * (n + 1)]
for i in range(n):
	adj_m.append('0' + str(input()))
adj_l = [[] for i in range(n + 1)]
total = int(input())
path = list(map(int, input().split()))
queue = deque()
dollar = [[10000000 for j in range(n + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
	queue = deque()
	valued = [1000000 for j in range(n + 1)]
	valued[i] = 0
	visited = [False for j in range(n + 1)]
	for j in range(1, n + 1):
		if adj_m[i][j] == str(1):
			queue.append(j)
			valued[j] = min(valued[j], valued[i] + 1)
			dollar[i][j] = valued[j]
	visited[i] = True
	while queue:
		q = queue.popleft()
		if visited[q] == True:
			continue
		visited[q] = True
		for j in range(1, n + 1):
			if adj_m[q][j] == str(1):
				valued[j] = min(valued[j], valued[q] + 1)
				dollar[i][j] = valued[j]
				if visited[j] == False:
					queue.append(j)
ans = [True for i in range(total + 1)]
dp = [0 for i in range(total + 1)]
for i in range(0, total - 1):
	dp[i + 1] = dollar[path[i]][path[i + 1]]
	dp[i + 1] += dp[i]
i = 0
j = 0
count = 0
while j < total:
	j = i + 2
	while j < total:
		if dp[j - i] == dollar[path[i]][path[j]]:
			ans[j] = False
			count += 1
			j += 1
		else:
			i = j - 1
			break
print(total - count)
for i in range(total):
	if ans[i + 1] == True:
		print(path[i], end=' ')


n = int(input())
dist = []
for i in range(n):
	s = input()
	tem = []
	for j in s:
		if j == '0':
			tem.append(101)
		else:
			tem.append(1)
	dist.append(tem)
m = int(input())
p = list(map(int, input().split()))
for k in range(0, n):
	for i in range(0, n):
		for j in range(0, n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ind = [1] * m
count = 0
t = 0
for i in range(1, m - 1):
	if dist[p[t] - 1][p[i + 1] - 1] == i - t + 1 and p[t] != p[i + 1]:
		ind[i] = 0
		count += 1
	else:
		t = i
print(m - count)
for i in range(m):
	if ind[i] == 1:
		print(p[i], end=' ')


n = int(input())
l = []
p = []
ans = []
for i in range(n):
	l.append(list(map(int, input())))
for i in range(n):
	for j in range(n):
		if i != j and l[i][j] == 0:
			l[i][j] = 9999999
for k in range(n):
	for i in range(n):
		for j in range(n):
			if l[i][j] > l[i][k] + l[k][j]:
				l[i][j] = l[i][k] + l[k][j]
m = int(input())
p = list(map(int, input().split(' ')))
ans.append(p[0])
dis = 0
for i in range(1, m):
	dis = dis + l[p[i - 1] - 1][p[i] - 1]
	if dis > l[ans[len(ans) - 1] - 1][p[i] - 1]:
		ans.append(p[i - 1])
		dis = l[ans[len(ans) - 1] - 1][p[i] - 1]
ans.append(p[m - 1])
print(len(ans))
for i in ans:
	print(i, end=' ')


def floyd(g):
	n = len(g)
	for k in range(n):
		for i in range(n):
			if g[i][k] is None:
				continue
			for j in range(n):
				if g[k][j] is None:
					continue
				cand = g[i][k] + g[k][j]
				if g[i][j] is None or g[i][j] > cand:
					g[i][j] = cand
n = int(input())
g = []
for i in range(n):
	s = [None if d == '0' else 1 for d in input()]
	g.append(s)
m = int(input())
p = map(int, input().split())
p = [x - 1 for x in p]
floyd(g)
ans = [p[0]]
cI = 0
for i in range(1, m):
	d = i - cI
	dMin = g[p[cI]][p[i]]
	if d != dMin:
		cI = i - 1
		skip = False
		if ans[-1] == p[cI]:
			ans.append(p[cI - 1])
			if g[p[cI - 1]][p[i]] == 2:
				skip = True
				cI -= 1
		if not skip:
			ans.append(p[cI])
ans.append(p[-1])
print(len(ans))
print(' '.join([str(x + 1) for x in ans]), end='')
print(' ')


n = int(input())
gr = list()
for _ in range(n):
	gr.append(list(map(lambda x: [10000000000, 1][int(x)], input())))
m = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
for k in range(n):
	for i in range(n):
		for j in range(n):
			gr[i][j] = min(gr[i][j], gr[i][k] + gr[k][j])
skip = [[[0 for _ in range(n)] for __ in range(n)] for ___ in range(n)]
for i in range(n):
	for k in range(n):
		for j in range(n):
			skip[i][k][j] = [0, gr[i][j] == gr[i][k] + gr[k][j]][i != j]
ans = [p[0]]
for v in range(len(p[1:-1])):
	if not skip[ans[-1]][p[v + 1]][p[v + 2]]:
		ans.append(p[v + 1])
ans.append(p[-1])
ans = list(map(lambda x: x + 1, ans))
print(len(ans))
for i in ans:
	print(i, end=' ')


n = int(input())
edges = [[] for i in range(n)]
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			edges[i].append(j)
m = int(input())
path = [int(i) - 1 for i in input().split()]
dist = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	visited = [-1 for j in range(n)]
	visited[0] = i
	act = 0
	num_visited = 1
	while act < num_visited:
		for neigh in edges[visited[act]]:
			if neigh not in visited:
				dist[i][neigh] = dist[i][visited[act]] + 1
				visited[num_visited] = neigh
				num_visited += 1
		act += 1
ans = [path[0]]
act = 0
for i in range(1, m):
	if dist[ans[-1]][path[i]] < i - act:
		act = i - 1
		ans.append(path[i - 1])
ans.append(path[-1])
print(len(ans))
print(' '.join([str(i + 1) for i in ans]))


n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, list(input()))))
m = int(input())
b = list(map(int, input().split()))
for i in range(n):
	for j in range(n):
		if i != j and a[i][j] == 0:
			a[i][j] = 10 ** 18
for k in range(n):
	for i in range(n):
		for j in range(n):
			a[i][j] = min(a[i][j], a[i][k] + a[k][j])
ans = []
for i in range(m):
	if i == 0 or i == m - 1:
		ans.append(b[i])
		continue
	x = ans[-1] - 1
	if a[x][b[i] - 1] + a[b[i] - 1][b[i + 1] - 1] == a[x][b[i + 1] - 1]:
		continue
	ans.append(b[i])
print(len(ans))
print(*ans)


from collections import deque
n = int(input())
adj = []
for _ in range(n):
	l = input()
	adjline = []
	for i in range(n):
		if l[i] == '1':
			adjline.append(i)
	adj.append(adjline)
dist = [[-1] * n for _ in range(n)]
for i in range(n):
	dist[i][i] = 0
	dq = deque()
	dq.append(i)
	while dq:
		j = dq.popleft()
		dj = dist[i][j]
		for k in adj[j]:
			if dist[i][k] == -1:
				dist[i][k] = dj + 1
				dq.append(k)
m = int(input())
pp = map(int, input().split())
lv = next(pp)
vv = [lv]
dv = 0
lp = lv
for p in pp:
	dv += 1
	if dv > dist[lv - 1][p - 1]:
		vv.append(lp)
		lv = lp
		dv = 1
	lp = p
vv.append(lp)
print(len(vv))
print(*vv)


N = int(input())
E = [[N ** 2] * N for i in range(N)]
for i in range(N):
	(*X,) = map(int, input())
	for j in range(N):
		if X[j]:
			E[i][j] = 1
	E[i][i] = 0
for k in range(N):
	for i in range(N):
		for j in range(N):
			E[i][j] = min(E[i][j], E[i][k] + E[k][j])
M = int(input())
(*S,) = map(int, input().split())
v = S[0] - 1
prv = 0
L = [v + 1]
for i in range(1, M):
	w = S[i] - 1
	if i - prv != E[v][w]:
		v = S[i - 1] - 1
		prv = i - 1
		L.append(v + 1)
L.append(S[-1])
print(len(L))
print(*L)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
adj = []
graph = defaultdict(list)
for i in range(n):
	adj.append(list(input()))
	adj[i][i] = '1'
for i in range(n):
	for j in range(n):
		if adj[i][j] == '1':
			graph[i].append(j)
short = [[999999999999 for i in range(n)] for j in range(n)]
visited = [False] * n

def bfs(v):
	short[v][v] = 0
	p = v
	stack = deque([])
	visited[v] = True
	stack.append((v, v, 0))
	while len(stack) > 0:
		v = stack.popleft()
		for i in graph[v[0]]:
			if visited[i] == False:
				visited[i] = True
				short[p][i] = min(short[p][i], v[2] + 1)
				stack.append((i, p, v[2] + 1))
for i in range(n):
	visited = [False] * n
	bfs(i)
n = int(input())
l = list(map(int, input().split()))
ans = [l[0]]
last = l[0] - 1
for i in range(1, n - 1):
	if short[last][l[i + 1] - 1] == short[last][l[i] - 1] + 1:
		continue
	else:
		ans.append(l[i])
		last = l[i] - 1
ans.append(l[-1])
print(len(ans))
print(*ans)


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	graph = [[int(a) for a in list(input().rstrip())] for _ in range(N)]
	M = int(input())
	P = list(map(int, input().split()))
	INF = 10 ** 16
	dp = [[None] * N for _ in range(N)]
	for i in range(N):
		for j in range(N):
			if i == j:
				dp[i][j] = 0
			elif graph[i][j] == 0:
				dp[i][j] = INF
			else:
				dp[i][j] = 1
	for k in range(N):
		for i in range(N):
			for j in range(N):
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
	ans = [P[0]]
	last = 0
	for i in range(1, M):
		(p0, p1) = (P[i - 1], P[i])
		if dp[ans[-1] - 1][p1 - 1] < i + 1 - last:
			ans.append(p0)
			last = i
	ans.append(P[M - 1])
	ans = ans[1:]
	print(len(ans))
	print(' '.join([str(a) for a in ans]))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = [input() for _ in range(n)]
	m = N()
	parr = RLL()
	path = [[INF] * (n + 1) for _ in range(n + 1)]
	for i in range(n):
		for j in range(n):
			if arr[i][j] == '1':
				path[i + 1][j + 1] = 1
			path[i + 1][i + 1] = 0
	for k in range(1, n + 1):
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				path[i][j] = min(path[i][k] + path[k][j], path[i][j])
	res = [parr[0]]
	now = 0
	for i in range(1, m):
		now += 1
		if now != path[res[-1]][parr[i]]:
			res.append(parr[i - 1])
			now = 1
	res += [parr[-1]]
	print(len(res))
	print(*res)
main()


n = int(input())
s = [None] * n
for i in range(n):
	s[i] = input()
d = [[pow(10, 30)] * n for i in range(n)]
for i in range(n):
	for j in range(n):
		if s[i][j] == '1':
			d[i][j] = 1
for k in range(n):
	for i in range(n):
		for j in range(n):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
m = int(input())
p = [int(o) for o in input().split()]
ans = [p[0]]
cur = 1
while cur < m - 1:
	if ans[-1] == p[cur + 1]:
		ans.append(p[cur])
	elif d[ans[-1] - 1][p[cur] - 1] + d[p[cur] - 1][p[cur + 1] - 1] > d[ans[-1] - 1][p[cur + 1] - 1]:
		ans.append(p[cur])
	cur += 1
ans.append(p[-1])
print(len(ans))
print(*ans)


import sys

def main():
	INF = int(1000000000.0)
	n = int(sys.stdin.readline())
	g = [[]] * n
	for i in range(n):
		s = sys.stdin.readline().strip()
		sg = list(map(int, list(s)))
		g[i] = sg
	m = int(sys.stdin.readline())
	p = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
	for i in range(n):
		for j in range(n):
			if i != j and g[i][j] == 0:
				g[i][j] = INF
	for k in range(n):
		for i in range(n):
			for j in range(n):
				g[i][j] = min(g[i][j], g[i][k] + g[k][j])
	MAXM = int(1000000.0)
	p_len = len(p)
	ans = [0] * p_len
	ans_ind = 0
	ind = 0
	while ind < p_len:
		cur = p[ind]
		ans[ans_ind] = cur
		ans_ind += 1
		new = ind + 1
		while new < p_len and g[cur][p[new]] == new - ind:
			new += 1
		if new == p_len:
			ans[ans_ind] = p[-1]
			ans_ind += 1
			break
		if g[cur][p[new]] != new - ind:
			new -= 1
		ind = new
	ans = [x + 1 for x in ans[:ans_ind]]
	print(len(ans))
	print(' '.join(map(str, ans[:ans_ind])))
main()


import sys
input = lambda : sys.stdin.readline().strip()
n = int(input())
d = []
for i in range(n + 1):
	d.append([])
	for j in range(n + 1):
		d[-1].append(0)
for i in range(1, n + 1):
	s = input()
	for j in range(1, n + 1):
		if i != j:
			if s[j - 1] == '0':
				d[i][j] = sys.maxsize
			else:
				d[i][j] = 1
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			d[i][j] = min(d[i][k] + d[k][j], d[i][j])
m = int(input())
ls = list(map(int, input().split()))
ans = [ls[0]]
cur = 0
for i in range(1, m):
	if d[ans[-1]][ls[i]] < i - cur:
		ans.append(ls[i - 1])
		cur = i - 1
ans.append(ls[-1])
print(len(ans))
for i in ans:
	print(i, end=' ')
print()


from collections import defaultdict
graph = defaultdict(set)
n = int(input())
for _ in range(n):
	adj = input()
	graph[_ + 1] = set()
	for (i, c) in enumerate(adj):
		if c == '1':
			graph[_ + 1].add(i + 1)
floyd = defaultdict(dict)
nodes = list(graph)
inf = float('inf')
for n in nodes:
	for n2 in nodes:
		if n == n2:
			floyd[n][n2] = 0
		elif n2 in graph[n]:
			floyd[n][n2] = 1
		else:
			floyd[n][n2] = inf
for k in nodes:
	for i in nodes:
		for j in nodes:
			floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j])
m = int(input())
path = list(map(int, input().split()))
ans = [path[0]]
current = 0
i = 1
while i < m:
	if floyd[path[current]][path[i]] == i - current:
		i += 1
	else:
		ans.append(path[i - 1])
		current = i - 1
ans.append(path[-1])
print(len(ans))
print(*ans)


import sys

def main():

	def input():
		return sys.stdin.readline()[:-1]
	n = int(input())
	G = [''] * n
	for k in range(n):
		G[k] = input()
	D = [[float('inf')] * n for k in range(n)]
	for k in range(n):
		D[k][k] = 0
	for k in range(n):
		for m in range(n):
			if G[k][m] == '1':
				D[k][m] = 1
	for k in range(n):
		for l in range(n):
			for m in range(n):
				D[l][m] = min(D[l][m], D[l][k] + D[k][m])
	m = int(input())
	p = list(map(int, input().split()))
	s = 0
	e = 1
	kyori = 1
	ans = [p[0]]
	while e < m:
		if D[p[s] - 1][p[e] - 1] < kyori:
			ans += [p[e - 1]]
			kyori = 1
			s = e - 1
			e = s + 1
		else:
			kyori += 1
			e += 1
	ans += [p[-1]]
	print(len(ans))
	print(*ans)
main()


def gns():
	return list(map(int, input().split()))
n = int(input())
mp = []
for i in range(n):
	mp.append(input())

def bfs(i):
	nxt = [i]
	ans = [None] * n
	ans[i] = 0
	v = [False] * n
	v[i] = True
	p = 0
	while len(nxt) > 0:
		p += 1
		nxt_ = []
		for ni in nxt:
			for nn in range(n):
				if v[nn] or mp[ni][nn] == '0':
					continue
				v[nn] = True
				ans[nn] = p
				nxt_.append(nn)
		nxt = nxt_
	return ans
dis = [None] * n
for i in range(n):
	dis[i] = bfs(i)
m = int(input())
ms = gns()
ms = [x - 1 for x in ms]
ans = [ms[0]]
l = ms[0]
for i in range(1, m - 1):
	c = ms[i]
	cn = ms[i + 1]
	if dis[l][cn] <= dis[l][c]:
		ans.append(c)
		l = c
ans.append(ms[-1])
ans = [x + 1 for x in ans]
print(len(ans))
print(' '.join(map(str, ans)))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
import bisect as bs

def floyd_warshall(n, edges):
	dist = [[0 if i == j else float('inf') for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			if A[i][j]:
				dist[i][j] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dist[i][k] + dist[k][j] < dist[i][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
	return dist
n = int(input())
adj = [set() for i in range(n)]
A = [0] * n
for i in range(n):
	k = 0
	s = list(map(int, list(input())[:-1]))
	A[i] = s
	for j in s:
		if j == 1:
			adj[i].add(k)
		k += 1
m = int(input())
it = list(map(int, input().split()))
it = [i - 1 for i in it]
ss = {}
j = 0
for i in it:
	try:
		ss[i].append(j)
	except:
		ss[i] = [j]
	j += 1
p = [it[0]]
dp = [10 ** 6 + 5] * m
sh = {}
pp = {}
sh = floyd_warshall(n, A)
p = [it[0] + 1]
ind = 1
while ind < m:
	d = 2
	while ind < m and sh[p[-1] - 1][it[ind]] + 1 >= d:
		ind += 1
		d += 1
	p.append(it[ind - 1] + 1)
	d = 1
print(len(p))
print(*p)


from sys import stdin, stdout
from collections import defaultdict
import math
import copy
N = int(input())
data = []
diff_paths = {}
for s in range(N):
	for d in range(N):
		if s == d:
			diff_paths[s + 1, d + 1] = 0
		else:
			diff_paths[s + 1, d + 1] = 9999
for i in range(N):
	s = input()
	data.append(s)
	for j in range(N):
		if s[j] == '1':
			diff_paths[i + 1, j + 1] = 1
V = int(input())
arr = [int(x) for x in stdin.readline().split()]
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if diff_paths[i, j] > diff_paths[i, k] + diff_paths[k, j]:
				diff_paths[i, j] = diff_paths[i, k] + diff_paths[k, j]
ans = [arr[0]]
start = arr[0]
L = 0
for i in range(1, V):
	end = arr[i]
	if diff_paths[start, end] == L + 1:
		L += 1
	else:
		ans.append(arr[i - 1])
		start = arr[i - 1]
		L = 1
ans.append(arr[-1])
print(len(ans))
print(*ans)


import sys
import copy
input = sys.stdin.readline
n = int(input())
EDGE = [list(map(int, list(input().strip()))) for i in range(n)]
m = int(input())
P = list(map(int, input().split()))
Distance = copy.deepcopy(EDGE)
for i in range(n):
	for j in range(n):
		if Distance[i][j] == 0 and i != j:
			Distance[i][j] = float('inf')
for k in range(n):
	for i in range(n):
		for j in range(n):
			length = Distance[i][k] + Distance[k][j]
			if Distance[i][j] > length:
				Distance[i][j] = length
ANS = [P[0]]
NOW = 0
i = 1
while i < m:
	if Distance[P[NOW] - 1][P[i] - 1] == i - NOW:
		i += 1
	else:
		ANS.append(P[i - 1])
		NOW = i - 1
ANS.append(P[-1])
print(len(ANS))
print(*ANS)


def do():
	n = int(input())
	graph = [[0] * n for _ in range(n)]
	for i in range(n):
		tmp = [int(c) for c in input()]
		for j in range(len(tmp)):
			graph[i][j] = 1 if tmp[j] == 1 else float('inf')
	n_path = int(input())
	path = [int(c) - 1 for c in input().split(' ')]
	dis = [[float('inf')] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if i == j:
				dis[i][i] = 0
			else:
				dis[i][j] = graph[i][j]
	for k in range(n):
		for i in range(n):
			if i != k:
				for j in range(n):
					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
	res = [path[0]]
	cur = 0
	for i in range(1, n_path):
		cur += dis[path[i - 1]][path[i]]
		if cur > dis[res[-1]][path[i]]:
			res.append(path[i - 1])
			cur = dis[res[-1]][path[i]]
	if path[-1] != res[-1]:
		res.append(path[-1])
	print(len(res))
	print(' '.join([str(c + 1) for c in res]))
do()


n = int(input())
d = []
for i in range(n):
	d += [[int(i) for i in input()]]
inf = 200
for i in range(n):
	for j in range(n):
		if d[i][j] == 0 and i != j:
			d[i][j] = inf
for k in range(n):
	for j in range(n):
		for i in range(n):
			d[i][j] = min(d[i][j], d[i][k] + d[k][j])
m = int(input())
p = list(map(int, input().split()))
path = [p[0]]
j = 0
k = 0
i = 0
while i <= m - 1:
	if d[p[j] - 1][p[i] - 1] == i - j:
		k = i
		i += 1
	elif j != k:
		path.append(p[k])
		j = k
		i -= 1
path.append(p[m - 1])
print(len(path))
print(' '.join(map(str, path)))


import math
from sys import stdin, stdout
n = int(stdin.readline().strip())
adj_mtr = []
for i in range(n):
	adj_mtr.append(list(map(int, list(stdin.readline().strip()))))
for i in range(n):
	for j in range(n):
		if adj_mtr[i][j] == 0:
			adj_mtr[i][j] = math.inf
for k in range(n):
	for i in range(n):
		for j in range(n):
			adj_mtr[i][j] = min(adj_mtr[i][j], adj_mtr[i][k] + adj_mtr[k][j])
lpath = int(stdin.readline().strip())
path = list(map(int, stdin.readline().strip().split(' ')))
for i in range(len(path)):
	path[i] -= 1
ansarr = [path[0]]
start_ptr = 0
end_ptr = 1
pltn = 0
while end_ptr < len(path):
	if adj_mtr[path[start_ptr]][path[end_ptr]] < pltn + 1 or (adj_mtr[path[start_ptr]][path[end_ptr]] == pltn + 1 and path[start_ptr] == path[end_ptr]):
		ansarr.append(path[end_ptr - 1])
		start_ptr = end_ptr - 1
		pltn = 0
	else:
		end_ptr += 1
		pltn += 1
ansarr.append(path[-1])
for i in range(len(ansarr)):
	ansarr[i] += 1
stdout.write(str(len(ansarr)) + '\n')
for i in ansarr:
	stdout.write(str(i) + ' ')


import sys
n = int(sys.stdin.readline().strip())
A = []
for i in range(0, n):
	A.append(sys.stdin.readline().strip())
D = [[-200 for i in range(0, n)] for j in range(0, n)]
L = []
L2 = []
for i in range(0, n):
	D[i][i] = 0
	L.append([i, i])
for i in range(0, n):
	while len(L) > 0:
		(x, y) = L.pop()
		for j in range(0, n):
			if A[y][j] == '1' and D[x][j] == -200:
				D[x][j] = i + 1
				L2.append([x, j])
	L = L2[:]
	L2 = []
m = int(sys.stdin.readline().strip())
p = list(map(int, sys.stdin.readline().strip().split()))
k = 1
ans = []
i = 0
j = 1
while j < m - 1:
	if D[p[i] - 1][p[j + 1] - 1] == j + 1 - i:
		j = j + 1
	else:
		ans.append(p[i])
		i = j
		j = j + 1
ans.append(p[i])
if i != m - 1:
	ans.append(p[m - 1])
print(len(ans))
print(' '.join(list(map(str, ans))))


def path(s):
	s1 = {s}
	s2 = set()
	used = [0] * (n + 1)
	used[s] = 1
	ans = 0
	while s1:
		ans += 1
		for v in s1:
			for u in graph[v]:
				if used[u] == 0:
					paths[s][u] = ans
					used[u] = 1
					s2.add(u)
		s1 = s2
		s2 = set()
n = int(input())
A = [list(map(int, input())) for _ in range(n)]
graph = {i: set() for i in range(1, n + 1)}
for i in range(n):
	for j in range(n):
		if A[i][j]:
			graph[i + 1].add(j + 1)
m = int(input())
P = list(map(int, input().split()))
paths = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
	path(i)
u = 0
v = P[0]
ans = []
while u < m - 1:
	ans.append(P[u])
	l = u
	r = min(m, u + n + 1)
	while r - l > 1:
		mid = (l + r) // 2
		if paths[P[u]][P[mid]] == mid - u:
			l = mid
		else:
			r = mid
	u = l
ans.append(P[-1])
print(len(ans))
print(*ans)


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
n = int(input())
dist = []
for i in range(n):
	dist.append(list(map(lambda x: 1 if x == '1' else 200, input())))
m = int(input())
p = list(map(int, input().split()))

def solve(n, dist, m, p):
	for i in range(n):
		dist[i][i] = 0
	for t in range(n):
		for i in range(n):
			for j in range(n):
				dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j])
	prev = 0
	cur = 1
	a = p[prev]
	res = [a]
	while cur < m:
		if cur - prev == 1 and p[prev] == p[cur]:
			res.append(p[cur])
			prev = cur
			cur += 1
			continue
		b = p[cur]
		if dist[a - 1][b - 1] != cur - prev:
			res.append(p[cur - 1])
			prev = cur - 1
			cur -= 1
			a = p[prev]
		cur += 1
	res.append(p[cur - 1])
	return res
res = solve(n, dist, m, p)
print(str(len(res)) + '\n')
print(' '.join(map(str, res)))


def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
n = int(input())
g = [list(input()) for _ in range(n)]
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if g[i][j] == '1':
			d[i][j] = 1
warshall_floyd(d)
m = int(input())
arr = list(map(int, input().split()))
for i in range(m):
	arr[i] -= 1
ans = [arr[0]]
pos1 = 0
pos2 = 1
pos3 = 2
for i in range(m - 2):
	(u, w, v) = (arr[pos1], arr[pos2], arr[pos3])
	if u == v or d[u][w] + d[w][v] > d[u][v]:
		ans.append(w)
		pos1 = pos2
		pos2 = pos1 + 1
		pos3 = pos2 + 1
	else:
		pos2 += 1
		pos3 += 1
ans.append(arr[-1])
l = len(ans)
for i in range(l):
	ans[i] += 1
print(l)
print(*ans)


n = int(input())
distance = [[1000000 for _ in range(n)] for _ in range(n)]
adjMatrix = [[] for _ in range(n)]
for i in range(n):
	adjMatrix[i] = [int(x) for x in input()]
length = int(input())
path = [int(x) - 1 for x in input().split()]
for i in range(n):
	for k in range(n):
		if adjMatrix[i][k] == 1:
			distance[i][k] = 1
for i in range(n):
	for k in range(n):
		for j in range(n):
			distance[k][j] = min(distance[k][j], distance[k][i] + distance[i][j])
answer = []
answer.append(path[0])
leng = 1
for i in range(1, len(path)):
	if distance[answer[-1]][path[i]] >= leng and answer[-1] != path[i]:
		leng += 1
	else:
		leng = 2
		answer.append(path[i - 1])
answer.append(path[-1])
print(len(answer))
for i in answer:
	print(i + 1, end=' ')


import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n):
		self.n = n
		self.graph = [[] for i in range(n)]

	def bfs(self, root):
		queue = [root, -1]
		queue = deque(queue)
		vis = [0] * n
		d = [0] * n
		t = 1
		while len(queue) != 1:
			element = queue.popleft()
			if element == -1:
				queue.append(-1)
				t += 1
				continue
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					d[i] = t
					vis[i] = 1
		return d
n = int(input())
g = Graph(n)
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			g.graph[i].append(j)
k = int(input())
a = list(map(int, input().split()))
dist = []
for i in range(n):
	dist.append(g.bfs(i))
i = 1
root = a[0] - 1
d = 1
count = 1
ans = [a[0]]
while i < k:
	if dist[root][a[i] - 1] != d:
		count += 1
		root = a[i - 1] - 1
		ans.append(a[i - 1])
		d = 1
	else:
		i += 1
		d += 1
ans.append(a[-1])
count += 1
print(count)
print(*ans)