The map of Bertown can be represented as a set of $n$ intersections, numbered from $1$ to $n$ and connected by $m$ one-way roads. It is possible to move along the roads from any intersection to any other intersection. The length of some path from one intersection to another is the number of roads that one has to traverse along the path. The shortest path from one intersection $v$ to another intersection $u$ is the path that starts in $v$, ends in $u$ and has the minimum length among all such paths.

Polycarp lives near the intersection $s$ and works in a building near the intersection $t$. Every day he gets from $s$ to $t$ by car. Today he has chosen the following path to his workplace: $p_1$, $p_2$, ..., $p_k$, where $p_1 = s$, $p_k = t$, and all other elements of this sequence are the intermediate intersections, listed in the order Polycarp arrived at them. Polycarp never arrived at the same intersection twice, so all elements of this sequence are pairwise distinct. Note that you know Polycarp's path beforehand (it is fixed), and it is not necessarily one of the shortest paths from $s$ to $t$.

Polycarp's car has a complex navigation system installed in it. Let's describe how it works. When Polycarp starts his journey at the intersection $s$, the system chooses some shortest path from $s$ to $t$ and shows it to Polycarp. Let's denote the next intersection in the chosen path as $v$. If Polycarp chooses to drive along the road from $s$ to $v$, then the navigator shows him the same shortest path (obviously, starting from $v$ as soon as he arrives at this intersection). However, if Polycarp chooses to drive to another intersection $w$ instead, the navigator rebuilds the path: as soon as Polycarp arrives at $w$, the navigation system chooses some shortest path from $w$ to $t$ and shows it to Polycarp. The same process continues until Polycarp arrives at $t$: if Polycarp moves along the road recommended by the system, it maintains the shortest path it has already built; but if Polycarp chooses some other path, the system rebuilds the path by the same rules.

Here is an example. Suppose the map of Bertown looks as follows, and Polycarp drives along the path $[1, 2, 3, 4]$ ($s = 1$, $t = 4$):

Check the picture by the link

http://tk.codeforces.com/a.png

When Polycarp starts at $1$, the system chooses some shortest path from $1$ to $4$. There is only one such path, it is $[1, 5, 4]$;

Polycarp chooses to drive to $2$, which is not along the path chosen by the system. When Polycarp arrives at $2$, the navigator rebuilds the path by choosing some shortest path from $2$ to $4$, for example, $[2, 6, 4]$ (note that it could choose $[2, 3, 4]$);

Polycarp chooses to drive to $3$, which is not along the path chosen by the system. When Polycarp arrives at $3$, the navigator rebuilds the path by choosing the only shortest path from $3$ to $4$, which is $[3, 4]$;

Polycarp arrives at $4$ along the road chosen by the navigator, so the system does not have to rebuild anything.

Overall, we get $2$ rebuilds in this scenario. Note that if the system chose $[2, 3, 4]$ instead of $[2, 6, 4]$ during the second step, there would be only $1$ rebuild (since Polycarp goes along the path, so the system maintains the path $[3, 4]$ during the third step).

The example shows us that the number of rebuilds can differ even if the map of Bertown and the path chosen by Polycarp stays the same. Given this information (the map and Polycarp's path), can you determine the minimum and the maximum number of rebuilds that could have happened during the journey?


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \le n \le m \le 2 \cdot 10^5$) — the number of intersections and one-way roads in Bertown, respectively.

Then $m$ lines follow, each describing a road. Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) denoting a road from intersection $u$ to intersection $v$. All roads in Bertown are pairwise distinct, which means that each ordered pair $(u, v)$ appears at most once in these $m$ lines (but if there is a road $(u, v)$, the road $(v, u)$ can also appear).

The following line contains one integer $k$ ($2 \le k \le n$) — the number of intersections in Polycarp's path from home to his workplace.

The last line contains $k$ integers $p_1$, $p_2$, ..., $p_k$ ($1 \le p_i \le n$, all these integers are pairwise distinct) — the intersections along Polycarp's path in the order he arrived at them. $p_1$ is the intersection where Polycarp lives ($s = p_1$), and $p_k$ is the intersection where Polycarp's workplace is situated ($t = p_k$). It is guaranteed that for every $i \in [1, k - 1]$ the road from $p_i$ to $p_{i + 1}$ exists, so the path goes along the roads of Bertown.


-----Output-----

Print two integers: the minimum and the maximum number of rebuilds that could have happened during the journey.


-----Examples-----

Input
6 9
1 5
5 4
1 2
2 3
3 4
4 1
2 6
6 4
4 2
4
1 2 3 4
Output
1 2
Input
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
7
1 2 3 4 5 6 7
Output
0 0
Input
8 13
8 7
8 6
7 5
7 4
6 5
6 4
5 3
5 2
4 3
4 2
3 1
2 1
1 8
5
8 7 5 2 1
Output
0 3


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths


Solutions:
import sys
input = sys.stdin.buffer.readline
from queue import deque
(n, m) = [int(x) for x in input().split()]
adj = [[] for _ in range(n + 1)]
rev = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	adj[u].append(v)
	rev[v].append(u)
k = int(input())
p = [int(x) for x in input().split()]
inf = float('inf')
sp = [inf for _ in range(n + 1)]
q = deque([[0, p[k - 1]]])
while q:
	(d, node) = q.popleft()
	if sp[node] == inf:
		sp[node] = d
		for nex in rev[node]:
			if sp[nex] == inf:
				q.append([d + 1, nex])
minn = 0
maxx = 0
for i in range(k - 1):
	node = p[i]
	nex = p[i + 1]
	if sp[node] - 1 != sp[nex]:
		minn += 1
		maxx += 1
	else:
		matches = 0
		for i in adj[node]:
			if sp[i] + 1 == sp[node]:
				matches += 1
		if matches > 1:
			maxx += 1
print('{} {}'.format(minn, maxx))


from collections import deque
from sys import stdin
(nV, nE) = map(int, stdin.readline().split())
g = [[] for _ in range(nV + 1)]
rev = [[] for _ in range(nV + 1)]
for _ in range(nE):
	(u, v) = map(int, stdin.readline().split())
	g[u].append(v)
	rev[v].append(u)
k = int(stdin.readline())
path = list(map(int, stdin.readline().split()))

def bfs(s, g):
	UNDEF = -1
	dist = [UNDEF] * (nV + 1)
	dist[s] = 0
	q = deque([s])
	while q:
		v = q.pop()
		for to in g[v]:
			if dist[to] == UNDEF:
				dist[to] = 1 + dist[v]
				q.appendleft(to)
	return dist
dist = bfs(path[-1], rev)
mn = mx = 0
prev = None
for v in path:
	if prev and dist[v] > dist[prev] - 1:
		mn += 1
		mx += 1
	if prev and dist[v] == dist[prev] - 1:
		for to in g[prev]:
			if to != v and dist[to] == dist[v]:
				mx += 1
				break
	prev = v
print('%d %d' % (mn, mx))


(n, m) = map(int, input().split())
Q = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	Q[v].append(u)
k = int(input())
p = [int(T) - 1 for T in input().split()]
W = [-1] * n
E = [0] * n
q = [(p[-1], 0)]
for (u, d) in q:
	if W[u] < 0:
		W[u] = d
		d += 1
		for v in Q[u]:
			q.append((v, d))
	elif W[u] == d:
		E[u] += 1
R = S = 0
for i in range(1, k):
	(u, v) = (p[i - 1], p[i])
	if W[u] <= W[v]:
		R += 1
		S += 1
	elif E[u]:
		S += 1
print(R, S)


from collections import deque

def bfs(source):
	dis = [-1] * n
	que = deque()
	que.append(source)
	dis[source] = 0
	while que:
		u = que.popleft()
		for v in g1[u]:
			if dis[v] == -1:
				dis[v] = dis[u] + g1[u][v]
				que.append(v)
	return dis
(n, m) = map(int, input().split())
g = [{} for i in range(n)]
g1 = [{} for i in range(n)]
for j in range(m):
	(u, v) = map(int, input().split())
	g[u - 1][v - 1] = 1
	g1[v - 1][u - 1] = 1
k = int(input())
p = list(map(int, input().split()))
d = bfs(p[-1] - 1)
ans1 = ans2 = 0
for i in range(1, k - 1):
	m = d[p[i] - 1]
	k1 = k2 = 0
	for j in g[p[i - 1] - 1]:
		if d[j] <= m and j != p[i] - 1 and (k1 == 0):
			ans1 += 1
			k1 = 1
		if d[j] < m:
			ans2 += 1
			k2 = 1
		if k1 == 1 and k2 == 1:
			break
print(ans2, ans1)


from collections import deque
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
inverse = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	inverse[v].append(u)
k = int(input())
way = list(map(int, input().split()))
s = way[0]
t = way[-1]
queue = deque()
queue.append(t)
d = [0] * (n + 1)
used = [False] * (n + 1)
used[t] = True
while len(queue):
	cur = queue[0]
	queue.popleft()
	for to in inverse[cur]:
		if not used[to]:
			d[to] = d[cur] + 1
			queue.append(to)
			used[to] = True
ans_max = 0
ans_min = 0
for i in range(k - 1):
	if d[way[i]] > d[way[i + 1]]:
		to_min = -1
		for to in graph[way[i]]:
			if to != way[i + 1] and d[to] <= d[way[i + 1]]:
				to_min = to
		if to_min != -1:
			ans_max += 1
	else:
		ans_max += 1
		ans_min += 1
print(ans_min, ans_max)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edges = [[] for i in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	edges[b - 1].append(a - 1)
k = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
pset = set(p)
prev = dict()
for i in range(k - 1):
	prev[p[i + 1]] = p[i]
prev[p[0]] = -1
s = p[0]
t = p[-1]
from collections import deque
d = deque()
d.append((t, 0))
LARGE = n + 100
firstP = [LARGE] * n
firstNP = [LARGE] * n
seen = set()
seen.add(t)
while d:
	(nex, time) = d.popleft()
	for adj in edges[nex]:
		if adj not in seen:
			seen.add(adj)
			d.append((adj, time + 1))
		if nex in pset and prev[nex] == adj:
			if firstP[adj] == LARGE:
				firstP[adj] = time
		elif firstNP[adj] == LARGE:
			firstNP[adj] = time
smol = 0
tol = 0
for i in range(k - 1):
	if firstP[p[i]] > firstNP[p[i]]:
		smol += 1
	if firstP[p[i]] >= firstNP[p[i]]:
		tol += 1
print(smol, tol)


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

def bfs(graph, root):
	visited = set()
	dist = [0] * (n + 1)
	queue = collections.deque([root])
	visited.add(root)
	while queue:
		vertex = queue.popleft()
		for neighbour in graph[vertex]:
			if neighbour not in visited:
				dist[neighbour] = dist[vertex] + 1
				visited.add(neighbour)
				queue.append(neighbour)
	return dist
graph1 = defaultdict(list)
graph2 = defaultdict(list)
(n, m) = map(int, input().split())
for i in range(m):
	(u, v) = map(int, input().split())
	graph1[u].append(v)
	graph2[v].append(u)
k = int(input())
path = [int(i) for i in input().split()]
output = bfs(graph2, path[-1])
(mina, maxa) = (0, 0)
for j in range(k - 1):
	if output[path[j]] <= k - (j + 1):
		l = []
		for i in graph1[path[j]]:
			l.append(output[i])
		min_ = min(l)
		freq = l.count(min(l))
		if output[path[j + 1]] == min_:
			if freq > 1:
				maxa += 1
		else:
			mina += 1
			maxa += 1
print(mina, maxa)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
g_n = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g_n[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
k = int(input())
path = list(map(int, input().split()))
q = deque()
distance = [-1 for _ in range(n)]
distance[path[k - 1] - 1] = 0
q.append(path[k - 1] - 1)
while len(q):
	u = q.popleft()
	for v in g[u]:
		if distance[v] == -1:
			distance[v] = distance[u] + 1
			q.append(v)
rebuild = 0
rebuild_max = 0
for i in range(1, k - 1):
	if distance[path[i] - 1] == distance[path[i - 1] - 1] - 1:
		for w in g_n[path[i - 1] - 1]:
			if w != path[i] - 1 and distance[w] == distance[path[i] - 1]:
				rebuild_max += 1
				break
	else:
		rebuild += 1
print(rebuild, rebuild + rebuild_max)


from collections import defaultdict, deque
from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
err = [tuple(map(int, input().split())) for _ in range(m)]
k = int(input())
prr = list(map(int, input().split()))
dct = defaultdict(lambda : [])
for (u, v) in err:
	dct[v].append(u)
lim = 10 ** 6
cdct = defaultdict(lambda : (lim, 0))
r = prr[-1]
viz = {r}
q = deque(viz)
cdct[r] = (0, 1)
while q:
	r = q.popleft()
	d = cdct[r][0]
	for c in dct[r]:
		if c not in viz:
			q.append(c)
			viz.add(c)
		(cd, cp) = cdct[c]
		if d + 1 <= cd:
			cdct[c] = (d + 1, cp + 1)
d = cdct[prr[0]][0] + 1
mn = 0
mx = 0
for (i, p) in enumerate(prr):
	cd = cdct[p]
	imn = int(cd[0] >= d)
	mn += imn
	d = cd[0]
	if imn and cdct[prr[i - 1]][1] == 1:
		mx += 1
	mx += int(cd[1] > 1)
print(mn, mx)


import sys
input = sys.stdin.readline
INF = 10 ** 17
(V, E) = map(int, input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
	(a, b) = map(int, input().split())
	graph[b - 1].append(a - 1)
K = int(input())
A = list(map(int, input().split()))
g = A[-1] - 1
D = [INF for _ in range(V)]
D[g] = 0
q = [g]
while q:
	qq = []
	for p in q:
		for np in graph[p]:
			if D[np] == INF:
				D[np] = D[p] + 1
				qq.append(np)
	q = qq
Way = [set() for _ in range(V)]
for p in range(V):
	for np in graph[p]:
		if D[np] == D[p] + 1:
			Way[np].add(p)
a1 = 0
a2 = 0
for i in range(K - 1):
	a = A[i]
	b = A[i + 1]
	if not b - 1 in Way[a - 1]:
		a2 += 1
	elif len(Way[a - 1]) > 1:
		a1 += 1
print(a2, a1 + a2)


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')

def getInt():
	return int(input())

def getStrs():
	return input().split()

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

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	(N, M) = getInts()
	G = [[] for _ in range(N)]
	for m in range(M):
		(u, v) = getInts()
		u -= 1
		v -= 1
		G[v].append(u)
	K = getInt()
	P = [p - 1 for p in getInts()]
	Q = dq([(P[-1], 0)])
	depth = [-1] * N
	depth[P[-1]] = 0
	count = [0] * N
	count[P[-1]] = 1
	while Q:
		(node, level) = Q.popleft()
		for neigh in G[node]:
			if depth[neigh] == -1:
				count[neigh] = 1
				depth[neigh] = level + 1
				Q.append((neigh, level + 1))
			elif depth[neigh] == level + 1:
				count[neigh] += 1
	ans = [0, 0]
	for i in range(K - 1):
		if depth[P[i + 1]] == depth[P[i]] - 1:
			if count[P[i]] > 1:
				ans[1] += 1
		else:
			ans[0] += 1
	print(ans[0], ans[0] + ans[1])
	return
solve()


from collections import defaultdict, deque
(n, m) = map(int, input().split())
adj = defaultdict(list)
rev = defaultdict(list)
dist = {}
for _ in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	rev[v].append(u)
int(input())
path = list(map(int, input().split()))
queue = deque([path[-1]])
dist[path[-1]] = 0
while queue:
	cur = queue.popleft()
	for neighbor in rev[cur]:
		if neighbor in dist:
			continue
		dist[neighbor] = dist[cur] + 1
		queue.append(neighbor)
(mini, maxi) = (0, 0)
for ind in range(1, len(path) - 1):
	cur = path[ind]
	pre = path[ind - 1]
	if dist[cur] + 1 == dist[pre]:
		for neighbor in adj[pre]:
			if cur != neighbor and dist[neighbor] == dist[cur]:
				maxi += 1
				break
	else:
		mini += 1
		maxi += 1
print(mini, maxi)


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

def bfs(start):
	Q = deque()
	Q.append(start)
	visit = [False] * n
	visit[start] = True
	while Q:
		u = Q.popleft()
		for v in adj2[u]:
			if not visit[v]:
				dist[v] = dist[u] + 1
				Q.append(v)
				visit[v] = True
(n, m) = map(int, input().split())
adj = [[] for i in range(n)]
adj2 = [[] for i in range(n)]
for _ in range(m):
	(u, v) = [int(i) - 1 for i in input().split()]
	adj[u].append(v)
	adj2[v].append(u)
k = int(input())
path = [int(i) - 1 for i in input().split()]
dist = [0] * n
bfs(path[k - 1])
(mn, mx) = (0, 0)
prev = path[0]
for i in range(1, k):
	cur = path[i]
	if dist[prev] < dist[cur] + 1:
		mn += 1
		mx += 1
	else:
		scnt = 0
		for v in adj[prev]:
			if dist[prev] == dist[v] + 1:
				scnt += 1
		if scnt > 1:
			mx += 1
	prev = cur
print(mn, mx)


import sys
from collections import deque
sys.setrecursionlimit(1 << 30)
(m, n) = [int(x) for x in input().strip().split()]
graph = [[] for x in range(m + 1)]
for ni in range(n):
	(s, e) = [int(x) for x in input().strip().split()]
	graph[s].append(e)
grapht = [[] for x in range(m + 1)]
for mi in range(1, m + 1):
	for mij in graph[mi]:
		grapht[mij].append(mi)
k = int(input())
kl = [int(x) for x in input().split()]
(v, d, mina, maxa) = ([0] * (m + 1), [m + 10] * (m + 1), 0, 0)
(start, end) = (kl[0], kl[-1])
(d[end], dq, v[end]) = (0, deque([end]), 1)
while dq:
	node = dq.popleft()
	for nn in grapht[node]:
		if not v[nn]:
			(d[nn], v[nn]) = (1 + d[node], 1)
			dq.append(nn)
for kj in range(k - 1):
	ki = kl[kj]
	(mki, mcnt) = (float('inf'), 1)
	for nn in graph[ki]:
		if d[nn] < mki:
			mki = d[nn]
			mcnt = 1
		elif d[nn] == mki:
			mcnt += 1
	if mki == d[kl[kj + 1]]:
		if mcnt > 1:
			maxa += 1
	else:
		mina += 1
		maxa += 1
print(mina, maxa)


import sys
(n, m) = list(map(int, sys.stdin.readline().strip().split()))
N = [[] for i in range(0, n + 1)]
N2 = [[] for i in range(0, n + 1)]
for i in range(0, m):
	(u, v) = list(map(int, sys.stdin.readline().strip().split()))
	N[u].append(v)
	N2[v].append(u)
D = [n + 10] * (n + 1)
k = int(sys.stdin.readline().strip())
p = list(map(int, sys.stdin.readline().strip().split()))
D[p[k - 1]] = 0
L = [p[k - 1]]
i = 0
while i < len(L):
	u = L[i]
	for v in N2[u]:
		if D[v] > D[u] + 1:
			D[v] = D[u] + 1
			L.append(v)
	i = i + 1
m = 0
M = 0
for i in range(0, k - 1):
	q = p[i]
	r = p[i + 1]
	if D[q] != 1 + D[r]:
		m = m + 1
		M = M + 1
	c = 0
	for v in N[q]:
		if D[v] + 1 == D[q]:
			c = c + 1
	if c != 1 and D[q] == 1 + D[r]:
		M = M + 1
print(m, M)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, M, edges, K, path):
	(s, t) = (path[0], path[-1])
	after = [[] for _ in range(N + 1)]
	dist = [N + 1 for _ in range(N + 1)]
	dist[t] = 0
	d = 0
	q = [t]
	while q:
		d += 1
		nq = []
		for u in q:
			for v in edges[u]:
				if dist[v] > d:
					dist[v] = d
					after[v] = [u]
					nq.append(v)
				elif dist[v] == d:
					after[v].append(u)
		q = nq
	(minRebuild, maxRebuild) = (0, 0)
	for i in range(len(path) - 1):
		if path[i + 1] in after[path[i]]:
			if len(after[path[i]]) > 1:
				maxRebuild += 1
		else:
			minRebuild += 1
			maxRebuild += 1
	return [minRebuild, maxRebuild]
(N, M) = map(int, input().split())
edges = collections.defaultdict(list)
for i in range(M):
	(u, v) = map(int, input().split())
	edges[v].append(u)
K = int(input())
path = [int(x) for x in input().split()]
print(' '.join(map(str, solve(N, M, edges, K, path))))


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
(n, m) = R()
a = [[] for i in range(n + 1)]
b = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = R()
	a[y] += (x,)
	b[x] += (y,)
k = I()
v = L()
stk = deque([v[-1]])
vst = [False] * (n + 1)
val = [1] * (n + 1)
val[stk[-1]] = 0
vst[stk[-1]] = True
while stk:
	p = stk.pop()
	for el in a[p]:
		if not vst[el]:
			val[el] += val[p]
			stk.appendleft(el)
			vst[el] = True
mn = 0
mx = 0
for j in range(k - 1):
	i = v[j]
	cnt = 0
	p = inf
	for el in b[i]:
		if val[el] < p:
			p = val[el]
			cnt = 1
		elif val[el] == p:
			cnt += 1
	if p < val[v[j + 1]]:
		mx += 1
		mn += 1
	elif cnt > 1:
		mx += 1
print(mn, mx)


class LinkedListNodeBase:
	__slots__ = ['prev', 'next']

	def __init__(self):
		self.prev = None
		self.next = None

	def connect(self, node):
		self.next = node
		node.prev = self
		return node

	def splice(self, fragment):
		if fragment.prev:
			fragment.prev.next = None
		u = self
		v = fragment
		w = self.next
		u.connect(v)
		while v.next:
			v = v.next
		v.connect(w)
		return v

	def splice1(self, node):
		node.connect(self.next)
		self.connect(node)

	def eject(self):
		self.prev.connect(self.next)

	def iterate(self):
		u = self
		while True:
			yield u
			u = u.next
			if not u or u == self:
				return
import abc
import math as m

class AbstractHeap(abc.ABC):

	@abc.abstractmethod
	def __init__(self, iterable=..., **kwarg):
		super().__init__(**kwarg)

	@abc.abstractmethod
	def __bool__(self):
		...

	@abc.abstractmethod
	def __len__(self):
		...

	@abc.abstractmethod
	def __contains__(self, value):
		...

	@abc.abstractmethod
	def __getitem__(self, value):
		...

	@abc.abstractmethod
	def push(self, key, value):
		...

	@abc.abstractmethod
	def pop(self):
		...

	@abc.abstractmethod
	def decrease_key(self, value, key):
		...

	@abc.abstractmethod
	def merge(self, other):
		...

class _FibHeapNode(LinkedListNodeBase):
	__slots__ = ['key', 'value', 'parent', 'child', 'degree', 'mark']

	def __init__(self, key, value):
		super().__init__()
		self.key = key
		self.value = value
		self.parent = None
		self.child = None
		self.degree = 0
		self.mark = False

class FibonacciHeap(AbstractHeap):

	def __init__(self, iterable=(), **kwarg):
		super().__init__(**kwarg)
		self._n = 0
		self._root = None
		self._index = {}
		for (k, v) in iterable:
			self.push(k, v)

	def __bool__(self):
		return bool(self._n)

	def __len__(self):
		return self._n

	def __contains__(self, value):
		return value in self._index

	def __getitem__(self, value):
		return self._index[value].key

	def __str__(self):

		def chain_str(c):
			ls = []
			for x in c.iterate():
				s = str(x.key)
				if x.child:
					s += f' ({chain_str(x.child)})'
				ls.append(s)
			return ', '.join(ls)
		return f"[{(chain_str(self._root) if self else '')}]"

	def push(self, key, value):
		node = _FibHeapNode(key, value)
		self._index[value] = node
		if self._root is None:
			node.connect(node)
			self._root = node
			self._n = 1
		else:
			self._root.splice1(node)
			if key < self._root.key:
				self._root = node
			self._n += 1

	def pop(self):
		z = self._root
		if z.child:
			for c in z.child.iterate():
				c.parent = None
			z.splice(z.child)
		if z.next == z:
			self._root = None
		else:
			self._root = z.next
			z.eject()
			self._consolidate()
		self._n -= 1
		del self._index[z.value]
		return (z.key, z.value)

	def _consolidate(self):
		A = {}
		for x in list(self._root.iterate()):
			d = x.degree
			while d in A:
				y = A[d]
				if x.key > y.key:
					(x, y) = (y, x)
				self._link(y, x)
				del A[d]
				d += 1
			A[d] = x
		i = iter(A.values())
		self._root = next(i)
		self._root.connect(self._root)
		for x in i:
			self._root.splice1(x)
			if x.key < self._root.key:
				self._root = x

	def _link(self, y, x):
		y.eject()
		y.parent = x
		if x.child:
			x.child.splice1(y)
		else:
			x.child = y
			y.connect(y)
		x.degree += 1
		y.mark = False

	def decrease_key(self, value, key):
		x = self._index[value]
		x.key = key
		del self._index[value]
		self._index[value] = x
		y = x.parent
		if y and x.key < y.key:
			self._cut(x, y)
			self._cascading_cut(y)
		if x.key < self._root.key:
			self._root = x

	def _cut(self, x, y):
		if x.next == x:
			y.child = None
		else:
			y.child = x.next
		x.parent = None
		x.eject()
		y.degree -= 1
		self._root.splice1(x)
		x.mark = False

	def _cascading_cut(self, y):
		z = y.parent
		if z:
			if not y.mark:
				y.mark = True
			else:
				self._cut(y, z)
				self._cascading_cut(z)

	def merge(self, other):
		if not other:
			return
		if self:
			self._root.splice(other._root)
			if other._root.key < self._root.key:
				self._root = other._root
			self._index.update(other._index)
		else:
			self._root = other._root
			self._index = other._index
		self._n += other._n
		other._root = None
		other._n = 0
		other._index = {}

class _InfKey:
	__gt__ = __ge__ = lambda *_: True
	__lt__ = __le__ = lambda *_: False
_inf_key = _InfKey()

class Implicit2Heap(AbstractHeap):

	def __init__(self, iterable=(), **kwarg):
		super().__init__(**kwarg)
		self._build_heap(iterable)

	def __bool__(self):
		return bool(self._tree)

	def __len__(self):
		return len(self._tree)

	def __contains__(self, value):
		return value in self._index

	def __getitem__(self, value):
		return self._tree[self._index[value]][0]

	def __str__(self):
		ls = []
		for (i, x) in enumerate(self._tree):
			s = '[' if m.log2(i + 1) % 1 == 0 else ''
			s += str(x[0])
			s += ']' if m.log2(i + 2) % 1 == 0 else ''
			ls.append(s)
		return ', '.join(ls)

	def _build_heap(self, iterable):
		self._tree = tree = list(iterable)
		size = len(tree)
		self._index = {tree[i][1]: i for i in range(size // 2, size)}
		for i in range(size // 2 - 1, -1, -1):
			self._heapify(i)

	def _heapify(self, i):
		tree = self._tree
		size = len(tree)
		left = (i + 1) * 2 - 1
		right = (i + 1) * 2 + 1 - 1
		if left < size and tree[left] < tree[i]:
			z = left
		else:
			z = i
		if right < size and tree[right] < tree[z]:
			z = right
		if z != i:
			(tree[i], tree[z]) = (tree[z], tree[i])
			self._heapify(z)
		self._index[tree[i][1]] = i

	def decrease_key(self, value, key):
		tree = self._tree
		i = self._index[value]
		while i > 0:
			p = (i + 1) // 2 - 1
			if not key < tree[p][0]:
				break
			tree[i] = tree[p]
			self._index[tree[i][1]] = i
			i = p
		tree[i] = (key, value)
		self._index[value] = i

	def push(self, key, value):
		self._index[value] = len(self._tree)
		self._tree.append((_inf_key, value))
		self.decrease_key(value, key)

	def pop(self):
		tree = self._tree
		z = tree[0]
		tree[0] = tree[-1]
		del tree[-1]
		if tree:
			self._heapify(0)
		del self._index[z[1]]
		return z

	def merge(self, other):
		if not other:
			return
		self._build_heap(self._tree + other._tree)
		other._tree = []
		other._index = {}

class _PairingHeapNode:
	__slots__ = ['key', 'value', 'parent', 'left', 'right']

	def __init__(self, key, value):
		super().__init__()
		self.key = key
		self.value = value
		self.parent = None
		self.left = None
		self.right = None

	def link(self, other):
		if other.key < self.key:
			(self, other) = (other, self)
		if not self.left:
			self.left = other
			other.parent = self
		else:
			r = self.left
			while r.right:
				r = r.right
			r.right = other
			other.parent = r
		return self

class PairingHeap(AbstractHeap):

	def __init__(self, iterable=(), **kwarg):
		super().__init__(**kwarg)
		self._root = None
		self._index = {}
		for (k, v) in iterable:
			self.push(k, v)

	def __bool__(self):
		return self._root is not None

	def __len__(self):
		return len(self._index)

	def __contains__(self, value):
		return value in self._index

	def __getitem__(self, value):
		return self._index[value].key

	def __str__(self):

		def tree_str(t):
			i = t
			ls = []
			while i:
				ls.append(str(i.key))
				i = i.right
			s = ', '.join(ls)
			if t.left:
				s += f' ({tree_str(t.left)})'
			return s
		return f"[{(tree_str(self._root) if self else '')}]"

	def push(self, key, value):
		node = _PairingHeapNode(key, value)
		self._index[value] = node
		if self._root is None:
			self._root = node
		else:
			self._root = self._root.link(node)

	def decrease_key(self, value, key):
		x = self._index[value]
		x.key = key
		del self._index[value]
		self._index[value] = x
		if x.parent is None:
			return
		if x.parent.left == x:
			x.parent.left = x.right
		else:
			x.parent.right = x.right
		if x.right:
			x.right.parent = x.parent
		x.parent = x.right = None
		self._root = self._root.link(x)

	def pop(self):
		z = self._root
		if z.left is None:
			self._root = None
		else:
			pass0 = []
			i = z.left
			while i:
				j = i.right
				i.parent = i.right = None
				pass0.append(i)
				i = j
			pass1 = []
			for (i, j) in zip(pass0[:-1:2], pass0[1::2]):
				pass1.append(i.link(j))
			if len(pass0) % 2 == 1:
				pass1.append(pass0[-1])
			y = pass1.pop()
			while pass1:
				y = y.link(pass1.pop())
			self._root = y
		del self._index[z.value]
		return (z.key, z.value)

	def merge(self, other):
		if not other:
			return
		if self:
			self._root = self._root.link(other._root)
			self._index.update(other._index)
		else:
			self._root = other._root
			self._index = other._index
		other._root = None
		other._index = {}
import math as m
import collections
import copy

class Graph:

	def __init__(self, maxV, isflow=False, sparse=False, **kwarg):
		super().__init__(**kwarg)
		self.maxV = maxV
		self.isflow = isflow
		self.sparse = sparse
		self._V = []
		self._V_index = {}
		non_edge = 0 if isflow else m.inf
		if sparse:
			df = lambda : non_edge
			self._E = [collections.defaultdict(df) for _ in range(maxV)]
		else:
			self._E = [[non_edge] * maxV for _ in range(maxV)]
		self._adj = [set() for _ in range(maxV)]
		self._levels = {}

	def __contains__(self, label):
		return label in self._V_index

	def __iter__(self):
		return iter(self._V)

	@property
	def nV(self):
		return len(self._V)

	@property
	def nE(self):
		n = sum((len(a) for a in self._adj))
		if self.isflow:
			n //= 2
		return n

	def add_vertex(self, label):
		self._V_index[label] = self.nV
		self._V.append(label)

	def add_vertexes(self, labels):
		for u_label in labels:
			self.add_vertex(u_label)

	def _add_edge(self, u, v, w):
		if self.isflow:
			self._E[u][v] += w
			self._adj[u].add(v)
			self._adj[v].add(u)
		else:
			self._E[u][v] = w
			self._adj[u].add(v)

	def add_edge(self, u_label, v_label, w=1):
		self._add_edge(self._V_index[u_label], self._V_index[v_label], w)

	def _isadj(self, u, v):
		return v in self._adj[u]

	def isadj(self, u_label, v_label):
		return self._isadj(self._V_index[u_label], self._V_index[v_label])

	def trim(self, u_label):
		u = self._V_index[u_label]
		self._adj[u] = set()
		if self.sparse:
			self._E[u].clear()
		else:
			self._E[u] = [m.inf] * self.maxV

	def _bfs_levels(self, s, t):
		self._levels[s] = [m.inf] * self.maxV
		self._levels[s][s] = 0
		queue = collections.deque([s])
		while queue:
			u = queue.popleft()
			for v in self._adj[u]:
				if self._E[u][v] > 0 and self._levels[s][v] == m.inf:
					self._levels[s][v] = self._levels[s][u] + 1
					queue.append(v)
		return self._levels[s][t]

	def _push_blocking_flow(self, s, t):
		pointers = [self._adj[i].copy() for i in range(self.nV)]

		def dfs_push(u, t, inflow):
			if u == t:
				return inflow
			u_outflow = 0
			while pointers[u]:
				v = pointers[u].pop()
				if self._levels[s][v] == self._levels[s][u] + 1 and self._E[u][v] > 0:
					v_flow = dfs_push(v, t, min(inflow, self._E[u][v]))
					self._E[u][v] -= v_flow
					self._E[v][u] += v_flow
					inflow -= v_flow
					u_outflow += v_flow
					if inflow == 0:
						pointers[u].add(v)
						break
			return u_outflow
		blocking_flow = dfs_push(s, t, m.inf)
		self._levels = {}
		return blocking_flow

	def max_flow(self, s_label, t_label):
		E_saved = copy.deepcopy(self._E)
		s = self._V_index[s_label]
		t = self._V_index[t_label]
		mf = 0
		while self._bfs_levels(s, t) != m.inf:
			mf += self._push_blocking_flow(s, t)
		self._E = E_saved
		return mf

	def all_pairs_spaths(self):
		fw = self._E
		for k in range(self.nV):
			next_fw = []
			for i in range(self.nV):
				next_fw.append([])
				for j in range(self.nV):
					next_fw[i].append(min(fw[i][j], fw[i][k] + fw[k][j]))
			fw = next_fw
		fw_labeled = {self._V[u]: {self._V[v]: fw[u][v] for v in range(self.nV)} for u in range(self.nV)}
		return fw_labeled

	def single_source_spaths(self, s_label, t_labels=None, d_limit=m.inf, Heap=Implicit2Heap):

		class SPathsObject(dict):
			pass
		ret = SPathsObject()
		s = self._V_index[s_label]
		if t_labels is None:
			t_set = set(range(self.nV))
		else:
			t_set = set((self._V_index[t_label] for t_label in t_labels))
		queue = Heap([(0, s)])
		spaths = {}
		parents = {}
		t_found = []
		while queue:
			(su, u) = queue.pop()
			if su >= d_limit:
				ret.stop = d_limit
				break
			spaths[u] = su
			if u in t_set:
				t_set.remove(u)
				t_found.append(u)
				if not t_set:
					ret.stop = su
					break
			for v in self._adj[u]:
				sv = su + self._E[u][v]
				if v in queue:
					if sv < queue[v]:
						parents[v] = u
						queue.decrease_key(v, sv)
				elif v not in spaths:
					parents[v] = u
					queue.push(sv, v)
		else:
			ret.stop = m.inf
		ret.update(((self._V[v], d) for (v, d) in spaths.items()))
		ret.parents = {self._V[v]: self._V[p] for (v, p) in parents.items()}
		ret.parents[s_label] = None
		ret.found = [self._V[t] for t in t_found]
		return ret

	def shortest_path(self, s_label, t_label, **kwarg):
		spaths = self.single_source_spaths(s_label, [t_label], **kwarg)
		return spaths.get(t_label, m.inf)

	def is_bipartite(self):
		if self.isflow:
			adj = self._adj
		else:
			adj = [set() for _ in range(self.nV)]
			for u in range(self.nV):
				for v in self._adj[u]:
					adj[u].add(v)
					adj[v].add(u)
		colors = {}

		def bfs_bicolor(s):
			if s in colors:
				return True
			colors[s] = True
			queue = collections.deque([s])
			while queue:
				u = queue.popleft()
				for v in adj[u]:
					if v not in colors:
						colors[v] = not colors[u]
						queue.append(v)
					elif colors[v] == colors[u]:
						return False
			return True
		return all(map(bfs_bicolor, range(self.nV)))
import collections
import sys
input = iter(sys.stdin.readlines()).__next__

def main():
	(n, m) = map(int, input().split())
	roads = [tuple(map(int, input().split())) for _ in range(m)]
	k = int(input())
	p = [int(x) for x in input().split()]
	G = Graph(n, sparse=True)
	adj = collections.defaultdict(set)
	G.add_vertexes(range(1, n + 1))
	for (u, v) in roads:
		G.add_edge(v, u)
		adj[u].add(v)
	spaths = G.single_source_spaths(p[-1], Heap=FibonacciHeap)
	min_rebuild = 0
	max_rebuild = 0
	for (i, u) in enumerate(p[:-1]):
		u_d = spaths[u]
		v = p[i + 1]
		v_d = spaths[v]
		if v_d != u_d - 1:
			min_rebuild += 1
			max_rebuild += 1
			continue
		for w in adj[u]:
			if w != v and spaths[w] == v_d:
				max_rebuild += 1
				break
	print(min_rebuild, max_rebuild)
main()


from collections import deque

def check(h):
	ans = 0
	for i in range(len(zapadlo[h])):
		if colors[zapadlo[h][i]] == colors[h] - 1:
			ans += 1
	return ans
(n, m) = map(int, input().split())
mas = [0] * n
zapadlo = [0] * n
for i in range(n):
	mas[i] = []
	zapadlo[i] = []
for i in range(m):
	(a, b) = map(int, input().split())
	mas[b - 1] += [a - 1]
	zapadlo[a - 1] += [b - 1]
k = int(input())
path = list(map(int, input().split()))
q = deque()
v = path[-1] - 1
q.append(v)
colors = [-1] * n
pred = [-1] * n
colors[v] = 0
while q:
	f = q.popleft()
	for j in range(len(mas[f])):
		i = mas[f][j]
		if colors[i] == -1:
			colors[i] = colors[f] + 1
			pred[i] = f
			q.append(i)
a = 0
b = 0
for i in range(1, k):
	g = path[i] - 1
	z = path[i - 1] - 1
	e = colors[g]
	f = colors[z]
	if e + 1 != f:
		a += 1
		b += 1
	elif check(z) > 1:
		b += 1
print(a, b)


from heapq import *
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

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

def MI1():
	return map(int1, sys.stdin.readline().split())

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

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	(n, m) = MI()
	to = [[] for _ in range(n)]
	ot = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = MI1()
		to[u].append(v)
		ot[v].append(u)
	k = II()
	pp = LI1()
	hp = []
	heappush(hp, (0, pp[-1]))
	dist = [-1] * n
	while hp:
		(d, u) = heappop(hp)
		if dist[u] != -1:
			continue
		dist[u] = d
		for v in ot[u]:
			if dist[v] != -1:
				continue
			heappush(hp, (d + 1, v))
	mn = mx = 0
	for (p0, p1) in zip(pp, pp[1:]):
		if dist[p0] - 1 != dist[p1]:
			mn += 1
		for v in to[p0]:
			if v == p1:
				continue
			if dist[p0] - 1 == dist[v]:
				mx += 1
				break
	print(mn, mx)
main()


from collections import defaultdict, deque
(n, m) = map(int, input().split())
e = defaultdict(list)
for _ in range(m):
	(a, b) = map(int, input().split())
	e[b].append(a)
(plen, path) = (int(input()), list(map(int, input().split())))
tg = path[-1]
pathfrom = defaultdict(list)
pathsz = defaultdict(int)
q = deque([(tg, tg, 1)])
while q:
	(frm, to, sz) = q.popleft()
	if pathsz[to] == 0:
		pathsz[to] = sz
		pathfrom[to].append(frm)
		for u in e[to]:
			q.append((to, u, sz + 1))
	elif pathsz[to] == sz:
		pathfrom[to].append(frm)
(mn, mx) = (0, 0)
for i in range(plen - 1):
	(u, v) = (path[i], path[i + 1])
	if v in pathfrom[u]:
		if len(pathfrom[u]) > 1:
			mx += 1
	else:
		mn += 1
		mx += 1
print(mn, mx)


from sys import stdin, stdout
import math
(n, m) = map(int, stdin.readline().rstrip().split(' '))
roads = [[] for _ in range(n)]
roadsTo = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, stdin.readline().rstrip().split(' '))
	u -= 1
	v -= 1
	roads[v].append(u)
	roadsTo[u].append(v)
k = int(stdin.readline().rstrip())
p = list(map(int, stdin.readline().rstrip().split(' ')))
p = [i - 1 for i in p]
visited = set([p[k - 1]])
lastBatch = set([p[k - 1]])
minLen = [0] * n
while len(visited) < n:
	batch = set()
	for i in lastBatch:
		for j in roads[i]:
			if j not in visited:
				visited.add(j)
				minLen[j] = minLen[i] + 1
				batch.add(j)
	lastBatch = batch
minChg = 0
maxChg = 0
for i in range(len(p) - 1):
	nextUp = minLen[p[i + 1]]
	otherQuickest = min([minLen[j] for j in roadsTo[p[i]] if j != p[i + 1]] + [999999])
	if otherQuickest < nextUp:
		minChg += 1
		maxChg += 1
	elif otherQuickest == nextUp:
		maxChg += 1
print(str(minChg) + ' ' + str(maxChg))


from collections import defaultdict, deque
(n, m) = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	graph[v].append(u)
k = int(input())
path = list(map(int, input().split()))
dq = deque()
dist = [float('inf')] * (n + 1)
dist[path[-1]] = 0
dq.append(path[-1])
From = [set() for i in range(n + 1)]
while dq:
	p = dq.popleft()
	w = dist[p] + 1
	for parent in graph[p]:
		if dist[parent] < w:
			continue
		elif dist[parent] > w:
			dist[parent] = w
			dq.append(parent)
		From[parent].add(p)
mn = 0
mx = 0
for i in range(1, k):
	f = path[i - 1]
	t = path[i]
	if t in From[f]:
		if len(From[f]) > 1:
			mx += 1
	else:
		mx += 1
		mn += 1
print(mn, mx)


import math
(n, m) = map(int, input().strip().split())
outadj = [set() for _ in range(n + 1)]
inadj = [set() for _ in range(n + 1)]
cost = [math.inf] * (n + 1)
discovered = [False] * (n + 1)
for _ in range(m):
	(u, v) = map(int, input().strip().split())
	outadj[u].add(v)
	inadj[v].add(u)
k = int(input())
path = list(map(int, input().strip().split()))
src = path[0]
dest = path[-1]
q = [dest]
cost[dest] = 0
discovered[dest] = True
while len(q) != 0:
	u = q.pop(0)
	for v in inadj[u]:
		if discovered[v]:
			continue
		discovered[v] = True
		cost[v] = cost[u] + 1
		q.append(v)
minim = 0
maxim = 0
for i in range(k - 1):
	if cost[path[i]] - 1 != cost[path[i + 1]]:
		minim += 1
		maxim += 1
	else:
		for v in outadj[path[i]]:
			if cost[path[i]] - 1 == cost[v] and v != path[i + 1]:
				maxim += 1
				break
print(minim, maxim)


import bisect
import collections
import copy
import enum
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
sys.setrecursionlimit(3001)
input = sys.stdin.readline
ng = collections.defaultdict(list)
sp = collections.defaultdict(list)
(n, m) = map(int, input().split())
for _ in range(m):
	(u, v) = map(int, input().split())
	ng[v].append(u)
k = int(input())
ks = list(map(int, input().split()))
q = []
vis = [0] * (n + 1)
q.append(ks[-1])
vis[ks[-1]] = 1
while q:
	nxt = set()
	for cq in q:
		for nq in ng[cq]:
			if vis[nq] == 0:
				sp[nq].append(cq)
				nxt.add(nq)
	q = list(nxt)
	for cq in q:
		vis[cq] = 1
mn = 0
mx = 0
for i in range(1, k):
	if ks[i] not in sp[ks[i - 1]]:
		mn += 1
		mx += 1
	elif len(sp[ks[i - 1]]) > 1:
		mx += 1
print(mn, mx)


import sys
from collections import deque

def bfs(g, src, d, found):
	q = deque()
	q.append(src)
	d[src] = 0
	while q:
		rmv = q.popleft()
		for child in g[rmv]:
			if d[child] == -1:
				d[child] = d[rmv] + 1
				q.append(child)
				found[child] = 1
			elif d[child] == d[rmv] + 1:
				found[child] += 1
(n, m) = map(int, sys.stdin.readline().split())
g = []
gt = []
for i in range(n):
	g.append(list())
	gt.append(list())
for _ in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	u -= 1
	v -= 1
	g[u].append(v)
	gt[v].append(u)
k = int(sys.stdin.readline())
p = list(map(int, sys.stdin.readline().split()))
for i in range(len(p)):
	p[i] -= 1
d = [-1] * n
found = {}
bfs(gt, p[-1], d, found)
mn = 0
mx = 0
for i in range(1, k):
	if d[p[i - 1]] - 1 != d[p[i]]:
		mn += 1
		mx += 1
	elif found.get(p[i - 1]) != None and found[p[i - 1]] > 1:
		mx += 1
print(mn, mx)


inf = int(10000000000.0)
(n, m) = map(int, input().split())
trans = [[] for i in range(n)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	trans[b - 1].append(a - 1)
	graph[a - 1].append(b - 1)
k = int(input())
lis = [x - 1 for x in map(int, input().split())]
(s, d) = (lis[0], lis[-1])
v = [0] * n
dis = [inf] * n
v[d] = 1
dis[d] = 0
q = [d]
while q:
	node = q.pop(0)
	for i in trans[node]:
		if not v[i] and dis[i] > dis[node] + 1:
			dis[i] = dis[node] + 1
			q.append(i)
(reb, ad) = (0, 0)
prev = s
for i in range(1, k - 1):
	if dis[lis[i]] + 1 > dis[prev]:
		reb += 1
	for j in graph[prev]:
		if j != lis[i] and dis[j] + 1 == dis[prev]:
			ad += 1
			break
	prev = lis[i]
print(reb, ad)


import sys, os, io
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = [int(i) for i in input().split()]
graph = [[] for i in range(n)]
graph1 = [[] for i in range(n)]
for i in range(m):
	(ui, vi) = [int(i) - 1 for i in input().split()]
	graph[vi].append(ui)
	graph1[ui].append(vi)
k = int(input())
p = [int(i) - 1 for i in input().split()]
q = deque()
q.append(p[-1])
dis = [10 ** 9] * n
dis[p[-1]] = 0
cnt = [0] * n
while len(q):
	curr = q.popleft()
	for i in graph[curr]:
		if dis[i] > dis[curr] + 1:
			dis[i] = dis[curr] + 1
			cnt[i] = 1
			q.append(i)
		elif dis[i] == dis[curr] + 1:
			cnt[i] += 1
x = 0
y = 0
arr = [[] for i in range(n)]
for i in range(n):
	arr[dis[i]].append(i)
for i in range(1, k):
	if dis[p[i]] > dis[p[i - 1]] - 1:
		y += 1
	else:
		for j in graph1[p[i - 1]]:
			if j != p[i] and dis[j] == dis[p[i]]:
				x += 1
				break
print(y, x + y)


from collections import deque
(n, m) = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	g[v].append(u)
k = int(input())
path = list(map(int, input().split()))
for i in range(k):
	path[i] -= 1
q = deque([])
q.append(path[-1])
dist = [-1] * n
isv = [-1] * n
dist[q[0]] = 0
while q:
	top = q.popleft()
	for i in g[top]:
		if dist[i] == -1:
			q.append(i)
			dist[i] = dist[top] + 1
			isv[i] = 1
		elif dist[i] == dist[top] + 1:
			isv[i] += 1
(mn, mx) = (0, 0)
for i in range(1, k):
	if dist[path[i - 1]] - 1 != dist[path[i]]:
		mn += 1
		mx += 1
	elif isv[path[i - 1]] != -1 and isv[path[i - 1]] > 1:
		mx += 1
print(mn, mx)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
E = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	E[y].append(x)
k = int(input())
A = list(map(int, input().split()))
from collections import deque
LAST = A[-1]
Q = deque()
Q.append(LAST)
USE = [1 << 31] * (n + 1)
USE[LAST] = 1
FROM = [set() for i in range(n + 1)]
while Q:
	x = Q.popleft()
	walk = USE[x] + 1
	for to in E[x]:
		if USE[to] < walk:
			continue
		elif USE[to] > walk:
			USE[to] = walk
			Q.append(to)
		FROM[to].add(x)
MIN = 0
MAX = 0
for i in range(1, k):
	now = A[i - 1]
	to = A[i]
	if to in FROM[now]:
		if len(FROM[now]) == 1:
			True
		else:
			MAX += 1
	else:
		MIN += 1
		MAX += 1
print(MIN, MAX)


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')

def main():
	from collections import deque, defaultdict
	(n, m) = map(int, input().split())
	rev = [[] for s in range(n)]
	for s in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		rev[v].append(u)
	k = int(input())
	vals = [int(i) - 1 for i in input().split()]
	queue = deque([vals[-1]])
	pos = defaultdict(list)
	pos[vals[-1]] = [0, set([])]
	while len(queue) > 0:
		v0 = queue.popleft()
		for s in range(len(rev[v0])):
			node = rev[v0][s]
			if len(pos[node]) == 0:
				pos[node] = [pos[v0][0] + 1, set([v0])]
				queue.append(node)
			elif pos[v0][0] + 1 < pos[node][0]:
				pos[node] = [pos[v0][0] + 1, set([v0])]
			elif pos[v0][0] + 1 == pos[node][0]:
				pos[node][1].add(v0)
	maxy = 0
	minny = 0
	for s in range(k - 1):
		if not vals[s + 1] in pos[vals[s]][1]:
			maxy += 1
			minny += 1
		elif vals[s + 1] in pos[vals[s]][1] and len(pos[vals[s]][1]) >= 2:
			maxy += 1
	print(minny, maxy)
main()


from sys import stdin, stdout
import math, sys
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

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')
adj = defaultdict(list)
rev = defaultdict(list)
dist = []
visited = []

def bfs(node):
	global adj, rev, dist, visited
	visited[node] = 1
	qu = deque()
	qu.append(node)
	while qu:
		el = qu.popleft()
		for child in rev[el]:
			if not visited[child]:
				dist[child] = dist[el] + 1
				qu.append(child)
				visited[child] = 1

def main():
	global adj, rev, dist, visited
	(n, m) = map(int, input().split())
	adj.clear()
	rev.clear()
	visited = [0] * (n + 1)
	dist = [0] * (n + 1)
	mn = 0
	mx = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		rev[v].append(u)
	k = int(input())
	arr = [int(k) for k in input().split()]
	no = arr[-1]
	bfs(no)
	for i in range(1, k):
		if dist[arr[i]] > dist[arr[i - 1]] - 1:
			mn += 1
			mx += 1
		else:
			for child in adj[arr[i - 1]]:
				if child != arr[i]:
					if dist[child] == dist[arr[i]]:
						mx += 1
						break
	stdout.write(str(mn) + ' ' + str(mx) + '\n')
main()


(n, m) = map(int, input().split())
import collections
re = collections.defaultdict(list)
ad = collections.defaultdict(list)
for _ in range(m):
	(a, b) = map(int, input().split())
	ad[a].append(b)
	re[b].append(a)
k = int(input())
p = map(int, input().split())
p = list(p)
short = {}
short[p[-1]] = 0
s = collections.deque([p[-1]])
while len(s) != 0:
	top = s.popleft()
	for x in re[top]:
		if x not in short:
			short[x] = short[top] + 1
			s.append(x)
MIN = MAX = 0
for (i, x) in enumerate(p[:-1]):
	y = p[i + 1]
	if short[x] != short[y] + 1:
		MIN += 1
		MAX += 1
	else:
		SUM = 0
		for z in ad[x]:
			if short[x] == short[z] + 1:
				SUM += 1
		if SUM >= 2:
			MAX += 1
print(MIN, MAX)


import os, sys
from io import BytesIO, IOBase
from collections import deque

def main():
	(n, m) = map(int, input().split())
	path = [[] for _ in range(n)]
	path1 = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(lambda xx: int(xx) - 1, input().split())
		path[b].append(a)
		path1[a].append(b)
	k = int(input())
	p = list(map(lambda xx: int(xx) - 1, input().split()))
	curr = deque([p[k - 1]])
	dis = [-1] * n
	dis[p[k - 1]] = 0
	while len(curr):
		x = curr.popleft()
		for i in path[x]:
			if dis[i] == -1:
				dis[i] = dis[x] + 1
				curr.append(i)
	(maxi, mini) = (0, 0)
	for i in range(k - 1):
		(di, cou) = (10 ** 10, 0)
		for x in path1[p[i]]:
			if dis[x] < di:
				di = dis[x]
				cou = 1
			elif dis[x] == di:
				cou += 1
		if dis[p[i + 1]] == di:
			maxi += cou > 1
		else:
			mini += 1
			maxi += 1
	print(mini, maxi)
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()


import sys
from collections import deque
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
gT = [[] for _ in range(n)]
for _ in range(m):
	(v, to) = map(int, input().split())
	v -= 1
	to -= 1
	g[v].append(to)
	gT[to].append(v)
k = int(input())
route = [int(x) - 1 for x in input().split()]
s = route[0]
e = route[-1]
dist = [None] * n
queue = deque([(e, 0)])
while queue:
	(v, d) = queue.popleft()
	if dist[v] is None:
		dist[v] = d
		for to in gT[v]:
			queue.append((to, d + 1))
minVal = 0
maxVal = 0
prev = s
for i in range(1, k):
	curr = route[i]
	if dist[prev] - 1 < dist[curr]:
		minVal += 1
		maxVal += 1
	else:
		hasOptions = False
		for to in g[prev]:
			if to == curr:
				continue
			if dist[prev] - 1 == dist[to]:
				hasOptions = True
				break
		if hasOptions:
			maxVal += 1
	prev = curr
print(minVal, maxVal)


from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush
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')

def RL():
	return 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 = 1000000007
INF = float('inf')
import bisect

def main():
	(n, m) = RL()
	graph = defaultdict(list)
	graph2 = defaultdict(list)
	path = [0] * (n + 1)
	visit = [0] * (n + 1)

	def bfs(start):
		visit[start] = 1
		q = deque()
		q.append((start, 0))
		while q:
			(node, dis) = q.popleft()
			path[node] = dis
			for nex in graph[node]:
				if visit[nex] == 0:
					q.append((nex, dis + 1))
					visit[nex] = 1
	for _ in range(m):
		(a, b) = RL()
		graph[b].append(a)
		graph2[a].append(b)
	k = N()
	karr = list(RL())
	bfs(karr[-1])
	r1 = r2 = 0
	for i in range(k - 1):
		(a, b) = (karr[i], karr[i + 1])
		if path[a] - 1 != path[b]:
			r1 += 1
			r2 += 1
		else:
			for at in graph2[a]:
				if at != b and path[at] == path[b]:
					r2 += 1
					break
	print(r1, r2)
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque

def main():

	def bfs(s):
		d = [-1] * n
		q = deque()
		q.append(s)
		d[s] = 0
		while q:
			cur = q.popleft()
			for v in G1[cur]:
				if d[v] == -1:
					d[v] = d[cur] + G1[cur][v]
					q.append(v)
		return d
	(n, m) = map(int, input().split())
	G = [{} for i in range(n)]
	G1 = [{} for i in range(n)]
	for i in range(m):
		(x, y) = map(int, input().split())
		G[x - 1][y - 1] = 1
		G1[y - 1][x - 1] = 1
	k = int(input())
	p = list(map(int, input().split()))
	dis = bfs(p[-1] - 1)
	min_ans = 0
	max_ans = 0
	for i in range(1, k - 1):
		m = dis[p[i] - 1]
		k1 = 0
		k2 = 0
		for j in G[p[i - 1] - 1]:
			if dis[j] <= m and j != p[i] - 1 and (k1 == 0):
				max_ans += 1
				k1 = 1
			if dis[j] < m:
				min_ans += 1
				k2 = 1
			if k1 == 1 and k2 == 1:
				break
	print(min_ans, max_ans)
main()


from sys import stdin, stdout
g = []
gg = []
dj = []

def main():
	global g
	global gg
	global dj
	(n, m) = list(map(int, stdin.readline().split()))
	g = [[] for _ in range(n + 1)]
	gg = [[] for _ in range(n + 1)]
	dj = [-1 for _ in range(n + 1)]
	al = [-1 for _ in range(n + 1)]
	for _ in range(m):
		(a, b) = list(map(int, stdin.readline().split()))
		g[b].append(a)
		gg[a].append(b)
	t = int(stdin.readline())
	route = list(map(int, stdin.readline().split()))
	dest = route[-1]
	stack = []
	stack.append(dest)
	dist = 0
	while stack:
		temp = []
		for x in stack:
			if dj[x] == -1:
				dj[x] = dist
				for y in g[x]:
					if al[y] == -1:
						temp.append(y)
						al[y] = 0
		dist += 1
		stack = temp
	cnt = 0
	opt = 0
	for (i, x) in enumerate(route):
		if i == len(route) - 1:
			continue
		nxt = route[i + 1]
		if dj[x] != dj[nxt] + 1:
			cnt += 1
		else:
			for y in gg[x]:
				if dj[y] == dj[nxt] and nxt != y:
					opt += 1
					break
	print(str(cnt) + ' ' + str(cnt + opt))
main()


from collections import deque
from collections import defaultdict
(no_nodes, e) = list(map(int, input().strip().split()))
edges = []
for _ in range(e):
	(u, v) = list(map(int, input().strip().split()))
	edges.append((u, v))
k = int(input().strip())
given_path = list(map(int, input().strip().split()))
dest = given_path[-1]

class BFS_Graph:

	def __init__(self, no_nodes):
		self.graph = defaultdict(list)
		self.no_nodes = no_nodes + 1

	def add_edge(self, u, v):
		self.graph[u].append(v)

	def add_edges_from_list(self, edges):
		for edge in edges:
			self.add_edge(edge[1], edge[0])

	def BFS(self, source, destination=-1):
		visited = [False] * self.no_nodes
		pred = [-1] * self.no_nodes
		dist = [float('inf')] * self.no_nodes
		visited[source] = True
		dist[source] = 0
		queue = deque()
		queue.append(source)
		while queue:
			u = queue.popleft()
			if u == destination:
				break
			for i in self.graph[u]:
				if visited[i] == False:
					visited[i] = True
					dist[i] = dist[u] + 1
					pred[i] = [u]
					queue.append(i)
				elif dist[i] == dist[u] + 1:
					pred[i].append(u)
		return (pred, dist)
g = BFS_Graph(no_nodes)
g.add_edges_from_list(edges)
(pred, dist) = g.BFS(dest)
definite = []
possible = []
for i in range(1, k - 1):
	pre_node = given_path[i - 1]
	current_node = given_path[i]
	if dist[current_node] >= dist[pre_node]:
		definite.append(current_node)
	elif len(pred[pre_node]) > 1:
		possible.append(current_node)
max_val = len(definite) + len(possible)
min_val = len(definite)
print(min_val, max_val)


import sys
input = sys.stdin.readline
import heapq
import copy
import math
import decimal

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def insr2():
	s = input()
	return s[:len(s) - 1]

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

def pr_list(a):
	print(*a, sep=' ')

def main():
	tests = 1
	mod = 1000000007
	limit = 10 ** 18
	ans = 0
	stack = []
	hashm = {}
	arr = []
	heapq.heapify(arr)
	for test in range(tests):
		[n, m] = inlt()
		grid = [{} for i in range(n + 1)]
		grid_r = [{} for i in range(n + 1)]
		for _ in range(m):
			[i, j] = inlt()
			grid[i][j] = 1
			grid_r[j][i] = 1
		mini = [sys.maxsize for i in range(n + 1)]
		k = inp()
		p = inlt()
		mini[p[-1]] = 0
		stack = [p[-1]]
		while stack != []:
			nexts = []
			for i in stack:
				for j in grid_r[i]:
					if mini[j] == sys.maxsize:
						nexts.append(j)
						mini[j] = mini[i] + 1
			stack = nexts
		minimum = 0
		maximum = 0
		for i in range(0, k - 1):
			dist = mini[p[i]]
			dist = dist - 1
			valid = []
			minimum = minimum + 1
			for j in grid[p[i]]:
				if mini[j] == dist:
					valid.append(j)
					if j == p[i + 1]:
						minimum = minimum - 1
			if len(valid) > 1:
				maximum = maximum + 1
			elif len(valid) == 1 and valid[0] != p[i + 1]:
				maximum = maximum + 1
		pr_list([minimum, maximum])
main()


import sys
from collections import defaultdict, deque

def bfs(g, source):
	q = deque()
	dist = {}
	q.append(source)
	dist[source] = 0
	while q:
		node = q.popleft()
		assert node in dist
		d = dist[node]
		for nbr in g[node]:
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
	return dist

def solve(N, M, roads, K, intersections):
	graph = defaultdict(set)
	graphT = defaultdict(set)
	for (u, v) in roads:
		graph[u].add(v)
		graphT[v].add(u)
	dist = bfs(graphT, intersections[-1])
	lo = 0
	hi = 0
	for i in range(K - 1):
		u = intersections[i]
		d1 = dist[u]
		short = set()
		for v in graph[u]:
			d2 = dist[v]
			if d1 - d2 == 1:
				short.add(v)
		if intersections[i + 1] in short:
			if len(short) > 1:
				hi += 1
		else:
			lo += 1
			hi += 1
	return str(lo) + ' ' + str(hi)
input = sys.stdin.readline
(N, M) = map(int, input().split())
roads = []
for i in range(M):
	roads.append(list(map(int, input().split())))
K = int(input())
intersections = list(map(int, input().split()))
ans = solve(N, M, roads, K, intersections)
print(ans)


from sys import stdin
from bisect import bisect_left as bl
from bisect import bisect_right as br

def input():
	return stdin.readline()[:-1]

def intput():
	return int(input())

def sinput():
	return input().split()

def intsput():
	return map(int, sinput())

class RangedList:

	def __init__(self, start, stop, val=0):
		self.shift = 0 - start
		self.start = start
		self.stop = stop
		self.list = [val] * (stop - start)

	def __setitem__(self, key, value):
		self.list[key + self.shift] = value

	def __getitem__(self, key):
		return self.list[key + self.shift]

	def __repr__(self):
		return str(self.list)

	def __iter__(self):
		return iter(self.list)

def dprint(*args, **kwargs):
	if debugging:
		print(*args, **kwargs)
debugging = 1
(n, m) = intsput()
roads = {}
rev_roads = {}
headto = {}
for i in range(1, n + 1):
	roads[i] = []
	rev_roads[i] = []
	headto[i] = set()
for _ in range(m):
	(start, end) = intsput()
	roads[start].append(end)
	rev_roads[end].append(start)
k = intput()
path = list(intsput())
(start, end) = (path[0], path[-1])
visited = set([end])
queue = set([end])
nxtqueue = set()
while queue:
	for stt in queue:
		for dest in rev_roads[stt]:
			if dest not in visited:
				headto[dest].add(stt)
				nxtqueue.add(dest)
	for vstd in nxtqueue:
		visited.add(vstd)
	queue = nxtqueue
	nxtqueue = set()
small = 0
large = 0
for i in range(k - 1):
	(frm, to) = (path[i], path[i + 1])
	if to in headto[frm]:
		small += 0
	else:
		small += 1
	if to in headto[frm]:
		large += 1 if len(headto[frm]) > 1 else 0
	else:
		large += 1
print(small, large)


from collections import defaultdict
(n, m) = map(int, input().split())
adj = defaultdict(list)
rev = defaultdict(list)
dist = {}
for _ in range(m):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	rev[v].append(u)
k = int(input())
path = list(map(int, input().split()))
dt = {}

def bfs(t):
	q = [t]
	dt[t] = 0
	while q:
		c = q.pop(0)
		for y in rev[c]:
			if y not in dt:
				dt[y] = dt[c] + 1
				q.append(y)
min_rebuild = 0
max_rebuild = 0
bfs(path[k - 1])
for i in range(1, k - 1):
	v = path[i - 1]
	u = path[i]
	if dt[u] + 1 > dt[v]:
		min_rebuild += 1
		max_rebuild += 1
	elif dt[u] + 1 == dt[v]:
		for w in adj[v]:
			if u != w and dt[u] == dt[w]:
				max_rebuild += 1
				break
print(min_rebuild, max_rebuild)


from heapq import *
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
to = [[] for i in range(n + 1)]
d = [1061109567 for i in range(n + 1)]
vis = [0 for i in range(n + 1)]

def dij(s):
	hp = []
	d[s] = 0
	heappush(hp, (0, s))
	while hp:
		(val, iid) = heappop(hp)
		if vis[iid] == 1:
			continue
		vis[iid] = 1
		for son in g[iid]:
			if d[son] > d[iid] + 1:
				d[son] = d[iid] + 1
				heappush(hp, (d[son], son))
for i in range(m):
	(u, v) = map(int, input().split())
	g[v].append(u)
	to[u].append(v)
k = int(input())
p = list(map(int, input().split()))
dij(p[-1])
mn = 0
mx = 0
for i in range(len(p) - 1):
	u = p[i]
	v = p[i + 1]
	if d[u] != d[v] + 1:
		mn += 1
	for iid in to[u]:
		if iid == v:
			continue
		if d[u] == d[iid] + 1:
			mx += 1
			break
print(mn, mx)


from sys import stdin
from collections import defaultdict, deque
input = stdin.readline
(n, m) = map(int, input().split())
edges = defaultdict(list)
forward = defaultdict(list)
for _ in range(m):
	(end, start) = map(int, input().split())
	edges[start].append(end)
	forward[end].append(start)
k = int(input())
path = list(map(int, input().split()))
(start, end) = (path[0], path[-1])
dist = {end: 0}
q = deque()
q.append(end)
while q:
	node = q.popleft()
	for nb in edges[node]:
		if nb in dist:
			continue
		dist[nb] = dist[node] + 1
		q.append(nb)
(MIN, MAX) = (0, 0)
for idx in range(k):
	if idx == k - 1:
		break
	now = path[idx]
	next_node = path[idx + 1]
	if dist[next_node] + 1 != dist[now]:
		MIN += 1
		MAX += 1
	elif any((dist[child] + 1 == dist[now] for child in forward[now] if child != next_node)):
		MAX += 1
print(MIN, MAX)


import queue
from sys import stdin, stdout
from queue import PriorityQueue
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, m) = mp()
roads = []
cons = dd(list)
fwd = dd(list)
for i in range(m):
	(x, y) = mp()
	cons[y - 1].append(x - 1)
	fwd[x - 1].append(y - 1)
k = iinp()
route = lmp()
end = route[-1] - 1
dist = l1d(n, inf)
vis = l1d(n, False)

def bfs(ind, d):
	st = deque()
	st.appendleft((ind, d))
	vis[ind] = True
	d += 1
	while len(st):
		(x, d) = st.pop()
		dist[x] = min(dist[x], d)
		for i in cons[x]:
			if not vis[i]:
				vis[i] = True
				st.appendleft((i, d + 1))
bfs(end, 0)
prev = route[0] - 1
mn = 0
mx = 0
md = dd(int)
for i in dist:
	md[i] += 1
for i in range(1, k):
	cur = route[i] - 1
	if dist[cur] >= dist[prev]:
		mn += 1
		mx += 1
	else:
		flg = False
		for f in fwd[prev]:
			if f != cur and dist[f] == dist[prev] - 1:
				flg = True
				break
		if flg:
			mx += 1
	prev = cur
print(mn, mx)


from collections import deque

class Graph:

	def __init__(self):
		self.edges = {}
		self.distances = {}
		self.shortest_paths = {}

	def join_nodes(self, a, b):
		if a not in self.edges:
			self.edges[a] = set()
		self.edges[a].add(b)

	def bfs_mark_distances(self, source):
		queue = deque([source])
		visited = set([source])
		self.distances[source] = 0
		while queue:
			parent = queue.popleft()
			for n in self.edges[parent]:
				if n in visited:
					continue
				self.distances[n] = self.distances[parent] + 1
				queue.append(n)
				visited.add(n)

	def count_shortest_paths(self):
		for (e, children) in self.edges.items():
			for c in children:
				if self.distances[e] == self.distances[c] - 1:
					if c not in self.shortest_paths:
						self.shortest_paths[c] = 0
					self.shortest_paths[c] += 1
graph = Graph()
(n, m) = map(int, input().split(' '))
for _ in range(m):
	(a, b) = map(int, input().split(' '))
	graph.join_nodes(b, a)
input()
path = list(map(int, input().split(' ')))
destination = path[-1]
graph.bfs_mark_distances(destination)
graph.count_shortest_paths()
min_rebuild = 0
max_rebuild = 0
for i in range(len(path) - 1):
	if graph.distances[path[i + 1]] != graph.distances[path[i]] - 1:
		min_rebuild += 1
	if graph.distances[path[i + 1]] != graph.distances[path[i]] - 1 or graph.shortest_paths[path[i]] > 1:
		max_rebuild += 1
print(min_rebuild, max_rebuild)


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

def bfs(root):
	vis = [0] * n
	queue = [root, -1]
	queue = deque(queue)
	vis[root] = 1
	d = 0
	while len(queue) != 1:
		element = queue.popleft()
		if element == -1:
			queue.append(-1)
			d += 1
			continue
		vis[element] = 1
		dist[element] = d
		for i in graph[element]:
			if not vis[i]:
				queue.append(i)
				vis[i] = 1
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
t = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	graph[v - 1].append(u - 1)
	t[u - 1].append(v - 1)
k = int(input())
p = list(map(int, input().split()))
dist = [0 for i in range(n)]
bfs(p[-1] - 1)
maxx = 0
minn = 0
for i in range(k - 1):
	if dist[p[i + 1] - 1] > dist[p[i] - 1] - 1:
		maxx += 1
		minn += 1
	else:
		count = 0
		for j in t[p[i] - 1]:
			if dist[j] == dist[p[i] - 1] - 1:
				count += 1
		if count >= 2:
			maxx += 1
print(minn, maxx)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
g_inv = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	g[u].append(v)
	g_inv[v].append(u)
k = int(input())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
from collections import deque
q = deque()
visit = [-1] * n
q.append(P[-1])
visit[P[-1]] = 0
while q:
	v = q.popleft()
	for u in g_inv[v]:
		if visit[u] == -1:
			visit[u] = visit[v] + 1
			q.append(u)
min_ = 0
max_ = 0
for i in range(k - 1):
	v = P[i]
	flag1 = False
	flag2 = False
	for u in g[v]:
		if u == P[i + 1] and visit[u] != visit[v] - 1:
			flag1 = True
		elif u != P[i + 1] and visit[u] == visit[v] - 1:
			flag2 = True
		else:
			pass
	if flag1:
		min_ += 1
	if flag2:
		max_ += 1
print(min_, max_)


from types import GeneratorType
INF = 10000000000.0

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def addEdge(self, v, w):
		self.adj[v].append(w)
import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
G = Graph(n)
G_transpose = Graph(n)
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	G.addEdge(u - 1, v - 1)
	G_transpose.addEdge(v - 1, u - 1)
minimums = [0 for _ in range(n)]
mini = [0 for _ in range(n)]
from collections import deque

def BFS_SP(graph, start):
	explored = set()
	queue = deque([start])
	dz = set()
	while queue:
		node = queue.popleft()
		if node not in explored:
			neighbours = graph.adj[node]
			for neighbour in neighbours:
				if neighbour not in dz:
					sd[neighbour] = sd[node] + 1
					minimums[neighbour] = sd[node] + 1
					mini[neighbour] = 1
					dz.add(neighbour)
					queue.append(neighbour)
				elif sd[node] + 1 == minimums[neighbour]:
					mini[neighbour] += 1
			explored.add(node)
k = int(input())
path = list(map(int, input().split()))
sd = [INF for _ in range(n)]
sd[path[-1] - 1] = 0
BFS_SP(G_transpose, path[-1] - 1)
ans_min = 0
ans_max = 0
for i in range(0, len(path) - 1):
	next_dist = sd[path[i + 1] - 1]
	if sd[path[i] - 1] == sd[path[i + 1] - 1] + 1:
		if mini[path[i] - 1] > 1:
			ans_max += 1
	else:
		ans_min += 1
		ans_max += 1
print(ans_min - 1, ans_max - 1)


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

def bfs(root):
	visit = [0] * (n + 1)
	queue = [root, -1]
	queue = deque(queue)
	visit[root] = 1
	d = 0
	while len(queue) != 1:
		element = queue.popleft()
		if element == -1:
			queue.append(-1)
			d += 1
			continue
		visit[element] = 1
		store[element] = d
		for i in r_graph[element]:
			if not visit[i]:
				queue.append(i)
				visit[i] = 1
(n, m) = map(int, input().split())
r_graph = [[] for i in range(n + 1)]
graph = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	r_graph[b].append(a)
k = int(input())
c = list(map(int, input().split()))
store = [0] * (n + 1)
bfs(c[-1])
(maxi, mini, count) = (0, 0, 0)
for i in range(k - 1):
	if store[c[i]] < store[c[i + 1]] + 1:
		maxi += 1
		mini += 1
	else:
		count = 0
		for j in graph[c[i]]:
			if store[c[i]] == store[j] + 1:
				count += 1
		if count >= 2:
			maxi += 1
print(mini, maxi)


(n, m) = map(int, input().split())
crossroads_in = [None] * n
for i in range(m):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	if not crossroads_in[b]:
		crossroads_in[b] = [a]
	else:
		crossroads_in[b].append(a)
k = int(input())
route = list(map(lambda x: int(x) - 1, input().split()))
distance = [0] * n
ways = [0] * n
t = route[-1]
visited = [0] * n
queue = [t]
p = 0
while p < len(queue):
	t = queue[p]
	p += 1
	if not crossroads_in[t]:
		continue
	for a in crossroads_in[t]:
		if distance[a] == 0:
			distance[a] = distance[t] + 1
			ways[a] = 1
		elif distance[a] == distance[t] + 1:
			ways[a] += 1
		if not visited[a]:
			queue.append(a)
			visited[a] = 1
d = 1
max_rebuild = 0
min_rebuild = 0
for t in reversed(route[:-1]):
	if distance[t] != d or ways[t] > 1:
		max_rebuild += 1
	if distance[t] != d:
		min_rebuild += 1
		d = distance[t]
	d += 1
print(min_rebuild, max_rebuild)


from sys import stdin
inf = stdin
(n, m) = map(int, inf.readline().split(' '))
graph = [[] for i in range(n + 1)]
for i in range(m):
	(p, q) = map(int, inf.readline().split(' '))
	graph[q].append(p)
path_len = int(inf.readline())
path = list(map(int, inf.readline().split(' ')))
queue = []
min_dist = [10000000] * (n + 1)
no_min_dist = [0] * (n + 1)
shortest_nodes = [[] for i in range(n + 1)]
queue.append(path[path_len - 1])
min_dist[path[path_len - 1]] = 0
while queue:
	node = queue.pop(0)
	for i in graph[node]:
		if min_dist[node] + 1 == min_dist[i]:
			no_min_dist[i] += 1
			shortest_nodes[i].append(node)
		elif min_dist[i] == 10000000:
			no_min_dist[i] = 1
			min_dist[i] = min_dist[node] + 1
			queue.append(i)
			shortest_nodes[i].append(node)
min_ans = 0
max_ans = 0
for i in range(path_len - 1):
	curr = path[i]
	if path[i + 1] in shortest_nodes[curr]:
		if no_min_dist[curr] != 1:
			max_ans += 1
	else:
		min_ans += 1
		max_ans += 1
print(min_ans, max_ans)


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

class Graph:

	def __init__(self, v):
		self.graph = defaultdict(list)
		self.reverse = defaultdict(list)
		self.distance = [0] * (v + 1)
		self.V = v

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.reverse[v].append(u)

	def bfs(self, v):
		queue = [v]
		visited = [False] * (self.V + 1)
		distance = self.distance
		visited[v] = True
		while queue:
			s = queue.pop(0)
			for i in self.reverse[s]:
				if visited[i] == False:
					visited[i] = True
					distance[i] = distance[s] + 1
					queue.append(i)

	def bfscalc(self, arr):
		(ansMin, ansMax, distance) = (0, 0, self.distance)
		for i in range(len(arr) - 1):
			k = arr[i]
			p = arr[i + 1]
			(minNode, minDistance, cnt) = (0, 10 ** 9, 0)
			for j in self.graph[k]:
				if minDistance > distance[j]:
					minDistance = distance[j]
					minNode = j
					cnt = 0
				if distance[j] == distance[p]:
					cnt += 1
			if distance[p] > minDistance:
				ansMin += 1
				ansMax += 1
			elif distance[p] == minDistance and cnt > 1:
				ansMax += 1
		print(ansMin, ansMax)
(n, m) = map(int, input().split())
g = Graph(n)
for _ in range(m):
	(a, b) = map(int, input().split())
	g.addEdge(a, b)
k = int(input())
arr = list(map(int, input().split()))
g.bfs(arr[k - 1])
g.bfscalc(arr)


(n, m) = list(map(int, input().split()))
roads = [[] for _ in range(n)]
in_roads = [[] for _ in range(n)]

def change(x):
	return int(x) - 1
for _ in range(m):
	(a, b) = list(map(change, input().split()))
	roads[a].append(b)
	in_roads[b].append(a)
total_path_dist = int(input())
path = list(map(change, input().split()))
from collections import deque
min_to_end = [0] * n
extended = [False] * n
queue = deque()
queue.append((path[-1], 0))
extended[path[-1]] = True
while queue:
	(i, leng) = queue.popleft()
	min_to_end[i] = leng
	for in_rd in in_roads[i]:
		if not extended[in_rd]:
			extended[in_rd] = True
			queue.append((in_rd, leng + 1))
min_ = 0
max_ = 0
for i in range(len(path) - 1):
	inter = path[i]
	to_int = path[i + 1]
	best_dist = min_to_end[inter]
	to_is_min = False
	other_mins = False
	for oth_int in roads[inter]:
		oth_best_dist = min_to_end[oth_int]
		if oth_int == to_int:
			if best_dist - 1 == oth_best_dist:
				to_is_min = True
			else:
				min_ += 1
				max_ += 1
				break
		elif best_dist - 1 == oth_best_dist:
			other_mins = True
	if to_is_min and other_mins:
		max_ += 1
print(min_, max_)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
from heapq import heappop, heappush

def multi_dijkstra(G, starts):
	n = len(G)
	dist = [float('inf')] * n
	visited = set()
	heap = []
	for i in starts:
		heap.append((0, i))
	while heap and len(visited) != n:
		(d, cur) = heappop(heap)
		if cur in visited:
			continue
		visited.add(cur)
		dist[cur] = d
		for to in G[cur]:
			if to not in visited:
				heappush(heap, (d + 1, to))
	return dist
(n, m) = map(int, input().split())
G = [[] for i in range(n)]
Gr = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Gr[a].append(b)
	G[b].append(a)
k = int(input())
p = list(map(int, input().split()))
p = [i - 1 for i in p]
(s, t) = (p[0], p[-1])
dist = multi_dijkstra(G, [t])
mi = ma = 0
cur = s
for i in range(1, k - 1):
	nxt = p[i]
	d = dist[cur]
	f = False
	dists = [dist[to] for to in Gr[cur]]
	d_min = min(dists)
	if dist[nxt] != d_min:
		mi += 1
		ma += 1
	elif dists.count(d_min) > 1:
		ma += 1
	cur = nxt
print(mi, ma)


from collections import deque
(n, m) = [int(x) for x in input().split()]
adj = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	adj[b].append(a)
k = int(input())
path = [int(x) - 1 for x in input().split()]
on_path = [False] * n
next_on_path = [-1] * n
for (i, v) in enumerate(path):
	on_path[v] = True
	if i + 1 < len(path):
		next_on_path[v] = path[i + 1]
(s, t) = (path[0], path[-1])
queue = deque([t])
seen = [False] * n
seen[t] = True
dist = [-1] * n
dist[t] = 0
fast_on_path = [False] * n
fast_off_path = [False] * n
while len(queue) > 0:
	cur = queue.popleft()
	for nb in adj[cur]:
		if not seen[nb]:
			seen[nb] = True
			queue.append(nb)
			dist[nb] = dist[cur] + 1
			if on_path[nb]:
				if next_on_path[nb] == cur:
					fast_on_path[nb] = True
				else:
					fast_off_path[nb] = True
		elif on_path[nb] and dist[nb] == dist[cur] + 1:
			if next_on_path[nb] == cur:
				fast_on_path[nb] = True
			else:
				fast_off_path[nb] = True
print(len(path) - sum(fast_on_path) - 1, sum(fast_off_path))


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def bfs(tree, s):
	n = len(tree)
	h = [0] * (n + 1)
	v = [0] * (n + 1)
	q = deque()
	q.append((s, 0))
	v[s] = 1
	while q:
		(c, p) = q.popleft()
		h[c] = h[p] + 1
		for i in tree[c]:
			if not v[i]:
				q.append((i, c))
				v[i] = 1
	return h

def main():
	(n, m) = map(int, input().split())
	tree = [[] for _ in range(n + 1)]
	tree1 = [[] for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = map(int, input().split())
		tree[x].append(y)
		tree1[y].append(x)
	k = int(input())
	a = list(map(int, input().split()))
	(h, mi, ma) = (bfs(tree1, a[-1]), 0, 0)
	for i in range(k - 1):
		if h[a[i + 1]] > h[a[i]] - 1:
			(mi, ma) = (mi + 1, ma + 1)
		else:
			f = 0
			for j in tree[a[i]]:
				if h[j] == h[a[i]] - 1 and j != a[i + 1]:
					f = 1
					break
			ma += f
	print(mi, ma)
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()


(n, m) = map(int, input().split())
u = []
r = []
for i in range(n):
	u.append([])
	r.append([])
for _ in range(m):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	u[b].append(a)
	r[a].append(b)
k = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
q = [p[-1]]
d = [100000000000] * n
d[p[-1]] = 0
q0 = 0
while len(q) > q0:
	v = q[q0]
	q0 += 1
	for i in u[v]:
		if d[i] > d[v] + 1:
			d[i] = d[v] + 1
			q.append(i)
mn = 0
mx = 0
for i in range(k - 1):
	(v, w) = (p[i], p[i + 1])
	if d[w] > d[v] - 1:
		mn += 1
		mx += 1
		continue
	for y in r[v]:
		if d[y] == d[v] - 1 and y != w:
			mx += 1
			break
print(mn, mx)


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def main():
	(n, m) = map(int, input().split())
	graph = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[v].append(u)
	k = int(input())
	path = list(map(int, input().split()))
	start = path[0]
	end = path[-1]
	dist = [-1] * (n + 1)
	dist[end] = 0
	directCount = [0] * (n + 1)
	queue = deque([end])
	vis = [0] * (n + 1)
	vis[end] = 1
	while queue:
		z = queue.popleft()
		for item in graph[z]:
			if vis[item] == 0:
				vis[item] = 1
				dist[item] = dist[z] + 1
				queue.append(item)
				directCount[item] = 1
			elif dist[item] == dist[z] + 1:
				directCount[item] += 1
	(mm, mx) = (0, 0)
	prev = dist[start]
	for i in range(1, k - 1):
		z = path[i]
		if dist[z] == prev - 1:
			if directCount[path[i - 1]] > 1:
				mx += 1
		else:
			mm += 1
		prev = dist[z]
	print(mm, mx + mm)
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 stdin, gettrace
from _collections import deque
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():
	(n, m) = map(int, input().split())
	adj = [set() for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj[v - 1].add(u - 1)
	k = int(input())
	pp = [int(a) - 1 for a in input().split()]
	spl = [n + 1] * n
	nxn = [set() for _ in range(n)]
	q = deque()
	q.append(pp[-1])
	spl[pp[-1]] = 0
	pushed = [False] * n
	while q:
		i = q.popleft()
		for a in adj[i]:
			if spl[a] >= spl[i] + 1:
				spl[a] = spl[i] + 1
				nxn[a].add(i)
				if not pushed[a]:
					q.append(a)
					pushed[a] = True
	mn = 0
	mx = 0
	prev = pp[0]
	for p in pp[1:]:
		if p not in nxn[prev]:
			mn += 1
			mx += 1
		elif len(nxn[prev]) > 1:
			mx += 1
		prev = p
	print(mn, mx)
main()


import sys
from collections import Counter, deque
readline = sys.stdin.readline

def bfs(s):
	Q = deque([s])
	dist = [N + 5] * N
	dist[s] = 0
	while Q:
		vn = Q.pop()
		for vf in Edgeinv[vn]:
			if dist[vf] > 1 + dist[vn]:
				dist[vf] = 1 + dist[vn]
				Q.appendleft(vf)
	return dist
(N, M) = map(int, readline().split())
Edge = [[] for _ in range(N)]
Edgeinv = [[] for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	Edgeinv[v].append(u)
	Edge[u].append(v)
K = int(readline())
path = list(map(lambda x: int(x) - 1, readline().split()))
T = path[-1]
dist = bfs(T)
mn = 0
mx = 0
for (vn, vf) in zip(path, path[1:]):
	dn = dist[vn]
	df = dist[vf]
	if dn != 1 + df:
		mn += 1
		mx += 1
	else:
		for vf2 in Edge[vn]:
			if vf == vf2:
				continue
			if dn == 1 + dist[vf2]:
				mx += 1
				break
print(mn, mx)


from collections import *
import math
INF = 1 << 60

def main():
	(N, M) = map(int, input().split(' '))
	adjl = [list() for _ in range(N)]
	adjltrans = [list() for _ in range(N)]
	for _ in range(M):
		(u, v) = map(int, input().split(' '))
		adjl[u - 1].append(v - 1)
		adjltrans[v - 1].append(u - 1)
	K = int(input())
	path = list(map(lambda x: int(x) - 1, input().split(' ')))
	dist = bfs(N, M, adjltrans, path[-1])
	max_reb = 0
	min_reb = 0
	for pidx in range(1, K):
		prev = path[pidx - 1]
		p = path[pidx]
		if dist[p] >= dist[prev]:
			min_reb += 1
			max_reb += 1
		else:
			opp = False
			for adj in adjl[prev]:
				if adj != p and dist[adj] == dist[p]:
					opp = True
			if opp:
				max_reb += 1
	print(min_reb, max_reb)

def bfs(N, M, adjl, src):
	q = deque()
	dist = [-1 for _ in range(N)]
	vis = [False for _ in range(N)]
	q.append((src, 0))
	dist[src] = 0
	vis[src] = True
	while len(q) > 0:
		(cur, dst) = q.popleft()
		for adj in adjl[cur]:
			if not vis[adj]:
				dist[adj] = dst + 1
				q.append((adj, dst + 1))
				vis[adj] = True
	return dist
main()