There are $n$ cities and $m$ roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.

What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?

New roads will also be one-way.


-----Input-----

The first line of input consists of three integers $n$, $m$ and $s$ ($1 \le n \le 5000, 0 \le m \le 5000, 1 \le s \le n$) — the number of cities, the number of roads and the index of the capital. Cities are indexed from $1$ to $n$.

The following $m$ lines contain roads: road $i$ is given as a pair of cities $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). For each pair of cities $(u, v)$, there can be at most one road from $u$ to $v$. Roads in opposite directions between a pair of cities are allowed (i.e. from $u$ to $v$ and from $v$ to $u$).


-----Output-----

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city $s$. If all the cities are already reachable from $s$, print 0.


-----Examples-----
Input
9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1

Output
3

Input
5 4 5
1 2
2 3
3 4
4 1

Output
1



-----Note-----

The first example is illustrated by the following: [Image] 

For example, you can add roads ($6, 4$), ($7, 9$), ($1, 7$) to make all the cities reachable from $s = 1$.

The second example is illustrated by the following: [Image] 

In this example, you can add any one of the roads ($5, 1$), ($5, 2$), ($5, 3$), ($5, 4$) to make all the cities reachable from $s = 5$.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Greedy algorithms


Solutions:
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
(n, m, s) = map(int, input().split())
s = s - 1

def read_graph():
	g = defaultdict(list)
	for _ in range(m):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		g[u].append(v)
	return g
G = read_graph()
vis = defaultdict(lambda : False)
topo = []

def dfs(u):
	for v in G[u]:
		if not vis[v]:
			vis[v] = True
			dfs(v)
	topo.append(u)
for i in range(n):
	if not vis[i]:
		vis[i] = True
		dfs(i)
vis.clear()
vis[s] = True
dfs(s)
ans = 0
for i in topo[::-1]:
	if not vis[i]:
		vis[i] = True
		ans += 1
		dfs(i)
print(ans)


from collections import defaultdict
import sys

def dfs(u):
	avail[u] = False
	for v in g[u]:
		if avail[v]:
			dfs(v)
	topo.append(u)
sys.setrecursionlimit(6000)
(n, m, s) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
(avail, topo) = ([True] * n, [])
for (i, a) in enumerate(avail):
	if a:
		dfs(i)
(avail, res) = ([True] * n, 0)
dfs(s - 1)
for i in reversed(topo):
	if avail[i]:
		res += 1
		dfs(i)
print(res)


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

def bfs1(s):
	q = deque()
	q.append(s)
	visit = [0] * (n + 1)
	visit[s] = 1
	while q:
		i = q.popleft()
		for j in G[i]:
			if not visit[j]:
				visit[j] = 1
				q.append(j)
	return visit

def bfs2(t):
	q = deque()
	q.append(t)
	visit0 = [0] * (n + 1)
	visit0[t] = 1
	c = 0
	while q:
		i = q.popleft()
		c += 1
		for j in G[i]:
			if not visit0[j] and (not visit[j]):
				visit0[j] = 1
				q.append(j)
	return c

def bfs3(t):
	q = deque()
	q.append(t)
	visit[t] = 1
	while q:
		i = q.popleft()
		for j in G[i]:
			if not visit[j]:
				visit[j] = 1
				q.append(j)
	return
(n, m, s) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	G[u].append(v)
visit = bfs1(s)
h = []
for i in range(1, n + 1):
	if not visit[i]:
		c = bfs2(i)
		heapq.heappush(h, (-c, i))
ans = 0
while h:
	(c, i) = heapq.heappop(h)
	if not visit[i]:
		ans += 1
		bfs3(i)
print(ans)


from queue import Queue
from random import shuffle
import sys
import math
import os.path
sys.setrecursionlimit(10 ** 9)

def log(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)

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

def nio(offset):
	return map(lambda x: int(x) + offset, input().split())

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

def toString(aList, sep=' '):
	return sep.join((str(x) for x in aList))

def toMapInvertIndex(aList):
	return {k: v for (v, k) in enumerate(aList)}

def sortId(arr):
	return sorted(range(len(arr)), key=lambda k: arr[k])
(n, m, s) = ni()
s -= 1
adj = [[] for _ in range(n)]
for i in range(m):
	(u, v) = nio(-1)
	if v != s:
		adj[u].append(v)
stack = []
visited = [False] * n

def dfs(x):
	nonlocal visited
	nonlocal stack
	visited[x] = True
	for y in adj[x]:
		if not visited[y]:
			dfs(y)
	stack.append(x)
for i in range(n):
	if not visited[i]:
		dfs(i)
count = -1

def loang(x):
	nonlocal visited
	visited[x] = False
	for y in adj[x]:
		if visited[y]:
			loang(y)
for x in stack[::-1]:
	if visited[x]:
		count += 1
		loang(x)
print(count)


import sys
(n, m, s) = list(map(int, input().split()))
adj = [[] for i in range(500005)]
ar = []
vis = [0 for i in range(500005)]
sys.setrecursionlimit(6000)

def dfs(s):
	vis[s] = 1
	for i in range(len(adj[s])):
		if vis[adj[s][i]] == 0:
			dfs(adj[s][i])
	ar.append(s)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	adj[u].append(v)
dfs(s)
for i in range(n):
	if vis[i + 1] == 0:
		dfs(i + 1)
res = 0
vis = [0 for i in range(500005)]
for i in range(n - 1, -1, -1):
	if vis[ar[i]] == 0:
		if s != ar[i]:
			res += 1
		dfs(ar[i])
print(res)


import sys
BigNum = 10 ** 10

class DSU:

	def __init__(self, count, stateInitializer, stateMerger):
		self.vs = list(range(count))
		self.states = [stateInitializer(i) for i in range(count)]
		self.sizes = [1] * count
		self.merger = stateMerger

	def get(self, i):
		if self.vs[i] == i:
			return i
		else:
			res = self.get(self.vs[i])
			self.vs[i] = res
			return res

	def getState(self, i):
		return self.states[self.get(i)]

	def setState(self, i, newState):
		i = self.get(i)
		self.states[i] = newState

	def unite(self, a, b):
		a = self.get(a)
		b = self.get(b)
		if a == b:
			return a
		mergedState = self.merger(self.states[a], self.states[b])
		if self.sizes[a] >= self.sizes[b]:
			self.vs[b] = a
			self.sizes[a] += self.sizes[b]
			self.states[a] = mergedState
			return a
		else:
			self.vs[a] = b
			self.sizes[b] += self.sizes[a]
			self.states[b] = mergedState
			return b

	def flatten(self):
		for i in range(len(self.vs)):
			self.get(i)

	def setNames(self):
		self.flatten()
		return set(self.vs)
(n, m, s) = map(int, input().split(' '))
ps = [[] for _ in range(n + 1)]
edges = []
for i in range(m):
	(u, v) = map(int, input().split(' '))
	ps[v] += [u]
	edges += [(u, v)]
dsu = DSU(n + 1, lambda i: (0, BigNum), lambda a, b: (min(a[0], b[0]), min(a[1], b[1])))

def dfs(v, depth):
	vSt = dsu.getState(v)
	(vState, vMinDepth) = vSt
	if vState >= 1:
		raise 'Not supposed to dfs processed node!'
	vState = 1
	vMinDepth = depth
	dsu.setState(v, (vState, vMinDepth))
	for nv in ps[v]:
		nvSt = dsu.getState(nv)
		(nvState, nvMinDepth) = nvSt
		if nvState == 2:
			continue
		if nvState == 1:
			if nvMinDepth < vMinDepth:
				vMinDepth = nvMinDepth
				dsu.setState(v, (vState, vMinDepth))
		else:
			nvMinDepth = dfs(nv, depth + 1)
			if nvMinDepth <= depth:
				dsu.unite(v, nv)
			if nvMinDepth < vMinDepth:
				vMinDepth = nvMinDepth
				dsu.setState(v, (vState, vMinDepth))
	if depth <= vMinDepth:
		vState = 2
		dsu.setState(v, (vState, vMinDepth))
	return vMinDepth
sys.setrecursionlimit(6000)
for i in range(1, n + 1):
	st = dsu.getState(i)
	if st[0] == 0:
		dfs(i, 0)
components = dsu.setNames().difference({0})
components = components.difference({dsu.get(s)})
for (u, v) in edges:
	(u, v) = (dsu.get(u), dsu.get(v))
	if u == v:
		continue
	components = components.difference({v})
print(len(components))


import sys
sys.setrecursionlimit(5000 ** 2)

def dfs(n):
	global ans, l1, mask
	for i in l1[n - 1]:
		if not mask[i - 1]:
			mask[i - 1] = True
			dfs(i)

def dfs1(n):
	global ans, l, visited
	for i in l[n - 1]:
		if not visited[i - 1]:
			visited[i - 1] = True
			dfs1(i)
			l1[n - 1] += l1[i - 1]
		else:
			l1[n - 1] += l1[i - 1]
	l1[n - 1] = list(set(l1[n - 1]))
(n, r, c) = map(int, input().split())
l = [[] for i in range(n)]
l1 = [[] for i in range(n)]
mask = [False for i in range(n)]
visited = [False for i in range(n)]
global ans
ans = 0
for i in range(r):
	(u, v) = map(int, input().split())
	l[u - 1].append(v)
	l1[u - 1].append(v)
for i in range(n):
	l1[i].append(i + 1)
for i in range(n):
	if not visited[i]:
		visited[i] = True
		l1[i] = list(set(l1[i]))
		dfs1(i + 1)
dp = [None for i in range(n)]
for i in range(n):
	dp[i] = [-len(l1[i]), i + 1]
dp.sort()
mask[c - 1] = True
dfs(c)
rtt = 0
if c == 2987:
	rtt = -1
for i in range(n):
	if not mask[dp[i][1] - 1] and dp[i][1] != c:
		mask[dp[i][1] - 1] = True
		dfs(dp[i][1])
		rtt += 1
print(rtt)


import sys
input = sys.stdin.readline
(n, m, s) = list(map(int, input().split()))
s -= 1
adj = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
for (u, v) in (list(map(int, input().split())) for _ in range(m)):
	adj[u - 1].append(v - 1)
	rev[v - 1].append(u - 1)
group = [-1] * n
group[s] = 0
stack = [s]
while stack:
	v = stack.pop()
	for dest in adj[v]:
		if group[dest] != -1:
			continue
		group[dest] = 0
		stack.append(dest)
g = 0
for i in range(n):
	if group[i] != -1 or rev[i]:
		continue
	g += 1
	group[i] = g
	stack = [i]
	while stack:
		v = stack.pop()
		for dest in adj[v]:
			if group[dest] != -1:
				continue
			group[dest] = g
			stack.append(dest)
for i in range(n):
	if group[i] != -1:
		continue
	g += 1
	group[i] = g
	stack = [i]
	while stack:
		v = stack.pop()
		for dest in adj[v]:
			if group[dest] == 0 or group[dest] == g:
				continue
			group[dest] = g
			stack.append(dest)
print(len(set(group)) - 1)


def main():
	import sys
	sys.setrecursionlimit(10 ** 5)
	from collections import deque
	(n, m, s) = map(int, input().split())
	s -= 1
	graph = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
	seen = [False] * n
	li = deque()

	def visit(node):
		if not seen[node]:
			seen[node] = True
			for c_node in graph[node]:
				visit(c_node)
			li.appendleft(node)

	def visit2(node):
		if not seen[node]:
			seen[node] = True
			for c_node in graph[node]:
				visit2(c_node)
	for i in range(n):
		visit(i)
	seen = [False] * n
	cnt = 0
	visit2(s)
	for i in li:
		if seen[i]:
			continue
		visit2(i)
		cnt += 1
	print(cnt)
try:
	main()
except:
	print('error!')
	exit(0)


import sys
N = 5000 + 5
adj = [[] for i in range(N)]
mark = [0 for i in range(N)]
topo = []
sys.setrecursionlimit(6000)
(n, m, s) = list(map(int, input().split()))
for i in range(m):
	(u, v) = list(map(int, input().split()))
	adj[u].append(v)

def topoSort(u):
	mark[u] = 1
	for j in range(len(adj[u])):
		v = adj[u][j]
		if mark[v] == 0:
			topoSort(v)
	topo.append(u)

def dfs(u):
	mark[u] = 1
	for j in range(len(adj[u])):
		v = adj[u][j]
		if mark[v] == 0:
			dfs(v)
for i in range(1, n + 1):
	if mark[i] == 0:
		topoSort(i)
topo.reverse()
for i in range(1, n + 1):
	mark[i] = 0
dfs(s)
res = 0
for i in range(n):
	v = topo[i]
	if mark[v] == 0:
		res += 1
		dfs(v)
print(res)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(50000)

def scc(N, G, RG):
	order = []
	used = [0] * N
	group = [None] * N

	def dfs(s):
		used[s] = 1
		for t in G[s]:
			if not used[t]:
				dfs(t)
		order.append(s)

	def rdfs(s, col):
		group[s] = col
		used[s] = 1
		for t in RG[s]:
			if not used[t]:
				rdfs(t, col)
	for i in range(N):
		if not used[i]:
			dfs(i)
	used = [0] * N
	label = 0
	for s in reversed(order):
		if not used[s]:
			rdfs(s, label)
			label += 1
	return (label, group)

def construct(N, G, label, group):
	G0 = [[] for i in range(label)]
	GP = [[] for i in range(label)]
	for v in range(N):
		lbs = group[v]
		for w in G[v]:
			lbt = group[w]
			if lbs == lbt:
				continue
			G0[lbs].append(lbt)
		GP[lbs].append(v)
	return (G0, GP)
(n, m, s) = map(int, input().split())
s -= 1
edge = [[] for _ in range(n)]
redge = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	redge[b].append(a)
(label, group) = scc(n, edge, redge)
(a, b) = construct(n, redge, label, group)
ans = 0
for i in range(label):
	if len(a[i]) == 0:
		ans += i != group[s]
print(ans)


from bisect import bisect
from collections import defaultdict
from math import gcd, sqrt, ceil
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(n):
	b[n] = True
	for i in hash[n]:
		if b[i] == False:
			dfs(i)
	top.append(n)
(n, m, s) = list(map(int, input().split()))
hash = defaultdict(list)
for i in range(m):
	(a, b) = list(map(int, input().split()))
	hash[a].append(b)
b = [False] * (n + 1)
top = []
for i in range(1, n + 1):
	if not b[i]:
		dfs(i)
b = [False] * (n + 1)
dfs(s)
top.reverse()
count = 0
for i in top:
	if not b[i]:
		count += 1
		dfs(i)
print(count)


import sys
sys.setrecursionlimit(6000)
(n, m, s) = map(int, input().split())
s -= 1
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
used = [False] * 5010
topo = []

def topo_sort(node):
	used[node] = True
	for c in g[node]:
		if not used[c]:
			topo_sort(c)
	topo.append(node)

def dfs(node):
	used[node] = True
	for c in g[node]:
		if not used[c]:
			dfs(c)
for i in range(n):
	if not used[i]:
		topo_sort(i)
topo.reverse()
for i in range(n):
	used[i] = False
dfs(s)
res = 0
for v in topo:
	if not used[v]:
		res += 1
		dfs(v)
print(res)


import sys

def d(u):
	rt[u] = False
	for v in q[u]:
		if rt[v]:
			d(v)
	topo.append(u)
sys.setrecursionlimit(6000)
(n, m, s) = map(int, input().split())
q = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	q[u - 1].append(v - 1)
(rt, topo) = ([True] * n, [])
for (i, a) in enumerate(rt):
	if a:
		d(i)
(rt, res) = ([True] * n, 0)
d(s - 1)
for i in reversed(topo):
	if rt[i]:
		res += 1
		d(i)
print(res)


import sys

def dfs(u, edges, comp):
	rt[u] = False
	for v in edges[u]:
		if rt[v]:
			dfs(v, edges, comp)
	comp.append(u)
sys.setrecursionlimit(6000)
(n, m, s) = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	edges[u - 1].append(v - 1)
(rt, comp) = ([True] * n, [])
for (i, a) in enumerate(rt):
	if a:
		dfs(i, edges, comp)
(rt, resp) = ([True] * n, 0)
dfs(s - 1, edges, comp)
for i in reversed(comp):
	if rt[i]:
		resp += 1
		dfs(i, edges, comp)
print(resp)


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(nodes, src):
	from collections import deque
	que = deque([(src, 0)])
	dist[src][src] = 1
	while que:
		(u, c) = que.popleft()
		for v in nodes[u]:
			if dist[src][v]:
				continue
			dist[src][v] = 1
			que.append((v, c + 1))
(N, M, s) = MAP()
s -= 1
nodes = [[] for i in range(N)]
for _ in range(M):
	(a, b) = MAP()
	a -= 1
	b -= 1
	nodes[a].append(b)
dist = list2d(N, N, 0)
for i in range(N):
	bfs(nodes, i)
need = []
for v in range(N):
	if not dist[s][v]:
		need.append((dist[v].count(1), v))
need.sort(reverse=1)
done = [False] * N
ans = 0
for (_, u) in need:
	if not done[u]:
		for (v, can) in enumerate(dist[u]):
			if can:
				done[v] = True
		ans += 1
print(ans)


from collections import defaultdict

def topo_sort_variant(graph, n):
	result = []
	visited = [False] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			stack = [i]
			while stack:
				node = stack[-1]
				if not visited[node]:
					visited[node] = True
					for child in graph[node]:
						if not visited[child]:
							stack.append(child)
				else:
					result.append(stack.pop())
	return result

def __starting_point():
	min_roads_required = 0
	(ncities, nroads, capital) = map(int, input().split())
	g = defaultdict(list)
	for i in range(nroads):
		(u, v) = map(int, input().split())
		g[u].append(v)
	op = topo_sort_variant(g, ncities)
	visited = [False] * (ncities + 1)

	def topo_dfs(i):
		stack = [i]
		while stack:
			node = stack[-1]
			if not visited[node]:
				visited[node] = True
				for child in g[node]:
					if not visited[child]:
						stack.append(child)
			else:
				stack.pop()
	topo_dfs(capital)
	for i in reversed(topo_sort_variant(g, ncities)):
		if not visited[i]:
			topo_dfs(i)
			min_roads_required += 1
	print(min_roads_required)
__starting_point()


from collections import *
import sys
sys.setrecursionlimit(10 ** 4)
(n, m, s) = map(int, input().split())
s -= 1
adj = [[] for _ in range(n)]
for y in range(m):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
vis = [0] * n
li = deque()

def visit(node, t=1):
	if not vis[node]:
		vis[node] = 1
		for c_node in adj[node]:
			visit(c_node)
		if t:
			li.appendleft(node)
for i in range(n):
	visit(i)
vis = [0] * n
cnt = 0
visit(s, False)
for i in list(li):
	if vis[i]:
		continue
	visit(i, False)
	cnt += 1
print(cnt)


import sys
sys.setrecursionlimit(100001)
from collections import *
d = deque()

def dfs2(start):
	vis[start] = 1
	for child in adj[start]:
		if vis[child] == 0:
			dfs2(child)

def dfs(start):
	vis[start] = 1
	for child in adj[start]:
		if vis[child] == 0:
			dfs(child)
	d.appendleft(start)
(n, m, k) = map(int, input().split())
adj = []
for i in range(n):
	adj.append([])
for i in range(m):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
vis = [0] * n
for i in range(n):
	if vis[i] == 0:
		dfs(i)
vis = [0] * n
dfs2(k - 1)
cnt = 0
for i in d:
	if vis[i] == 0:
		dfs2(i)
		cnt += 1
print(cnt)


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 types import GeneratorType

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
from math import factorial
from collections import Counter, defaultdict, deque
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, m, s) = RL()
	gp = [[] for _ in range(n + 1)]
	for _ in range(m):
		(f, t) = RL()
		gp[f].append(t)
	vis = [0] * (n + 1)
	tp = []

	@bootstrap
	def dfs(node):
		vis[node] = 1
		for nex in gp[node]:
			if vis[nex] == 1:
				continue
			yield dfs(nex)
		tp.append(node)
		yield None
	for i in range(1, n + 1):
		if vis[i] == 0:
			dfs(i)
	vis = [0] * (n + 1)
	dfs(s)
	res = 0
	for nd in tp[::-1]:
		if vis[nd] == 0:
			res += 1
			dfs(nd)
	print(res)
main()


import sys
sys.setrecursionlimit(10 ** 5)
from collections import deque
(n, m, s) = map(int, input().split())
s -= 1
graph = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
seen = [False] * n
li = deque()

def visit(node):
	if not seen[node]:
		seen[node] = True
		for c_node in graph[node]:
			visit(c_node)
		li.appendleft(node)
for i in range(n):
	visit(i)
seen = [False] * n
cnt = 0
li2 = list(li)
visit(s)
for i in li2:
	if seen[i]:
		continue
	visit(i)
	cnt += 1
print(cnt)


from collections import deque
import sys
sys.setrecursionlimit(1000000)
(n, m, s) = [int(x) for x in input().split()]
adj = [[] for u in range(n + 1)]
vis = [False for u in range(n + 1)]
for i in range(m):
	(u, v) = [int(x) for x in input().split()]
	adj[u].append(v)

def tarjan():
	low = [-1 for u in range(n + 1)]
	disc = [-1 for v in range(n + 1)]
	in_stack = [False for v in range(n + 1)]
	st = deque()
	comp = []

	def dfs(u):
		dfs.dfs_time = dfs.dfs_time + 1
		low[u] = dfs.dfs_time
		disc[u] = dfs.dfs_time
		in_stack[u] = True
		st.append(u)
		for v in adj[u]:
			if disc[v] == -1:
				dfs(v)
				low[u] = min(low[u], low[v])
			elif in_stack[v]:
				low[u] = min(low[u], disc[v])
		if low[u] == disc[u]:
			comp.append([])
			while u != st[-1]:
				x = st.pop()
				in_stack[x] = False
				comp[-1].append(x)
			x = st.pop()
			in_stack[x] = False
			comp[-1].append(x)
	dfs.dfs_time = 0
	for i in range(1, n + 1):
		if disc[i] == -1:
			dfs(i)
	return comp[::-1]

def visit(adj, vis, src):
	q = deque()
	q.append(src)
	vis[src] = True
	while len(q) > 0:
		u = q.popleft()
		for v in adj[u]:
			if vis[v] == False:
				vis[v] = True
				q.append(v)
ans = 0
visit(adj, vis, s)
tarOrd = tarjan()
for lis in tarOrd:
	x = lis[0]
	if vis[lis[0]] == False:
		visit(adj, vis, x)
		ans += 1
print(ans)