Given a directed acyclic graph(DAG) with n nodes labeled from 0 to n-1. Given edges, s and d ,count the number of ways to reach from s to d.There is a directed Edge from vertex edges[i][0] to the vertex edges[i][1].
 
Example:
Input: edges = {{0,1},{0,3},{1,2},{3,2}}, 
n = 4, s = 0, d = 2
Output: 2
Explanation: There are two ways to reach at 
2 from 0. These are-
1. 0->1->2
2. 0->3->2
 
Your Task:
You don't need to read or print anything. Your task is to complete the function possible_paths() which takes edges, n, s and d as input parameter and returns the number of ways to reach from s to d.
 
Expected Time Compelxity: O(2^{n})
Expected Space Complexity: O(n+e) 
where e is the number of edges in the graph.
 
Constraints:
1 <= n <= 15
0 <= s, d <= n-1

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def possible_paths(self, edges, n, s, d):

        #Code here

Solutions:
class Solution:

	def possible_paths(self, edges, n, s, d):
		g = [[] for _ in range(n)]
		for (a, b) in edges:
			g[a].append(b)
		path = set()

		def helper(node, prev, p):
			if node == d:
				path.add(tuple(p + [node]))
				return p
			if node in p:
				return False
			for neig in g[node]:
				if neig != prev:
					helper(neig, node, p + [node])
			return p
		helper(s, -1, [])
		return len(path)


class Solution:

	def solve(self, adj, n, s, d, dp):
		if dp[s] != 0:
			return dp[s]
		for child in adj[s]:
			dp[s] += self.solve(adj, n, child, d, dp)
		return dp[s]

	def possible_paths(self, edges, n, s, d):
		adj = dict()
		for i in range(n):
			adj[i] = []
		dp = [0] * n
		dp[d] = 1
		for edge in edges:
			(u, v) = (edge[0], edge[1])
			adj[u].append(v)
		return self.solve(adj, n, s, d, dp)


class Solution:

	def solve(self, adj, way, s, d):
		if s == d:
			way[0] += 1
			return
		for i in adj[s]:
			self.solve(adj, way, i, d)

	def possible_paths(self, edges, n, s, d):
		adj = [[] for i in range(n)]
		for (i, j) in edges:
			adj[i].append(j)
		way = [0]
		self.solve(adj, way, s, d)
		return way[0]


class Solution:

	def possible_paths(self, edges, n, s, d):

		def _dfs(vertex, target):
			visited.add(vertex)
			path.append(vertex)
			if vertex == target:
				output.append(list(path))
				path.pop()
				visited.remove(vertex)
				return
			for neighbor in graph[vertex]:
				if neighbor not in visited:
					_dfs(neighbor, target)
			path.pop()
			visited.remove(vertex)
		graph = [[] for i in range(n)]
		for edge in edges:
			graph[edge[0]].append(edge[1])
		visited = set()
		vertices = range(n)
		start = s
		target = d
		output = []
		path = []
		_dfs(start, target)
		return len(output)


from collections import defaultdict

class Solution:

	def dfs(self, node, d, graph):
		if node == d:
			self.ans += 1
			return
		for i in graph[node]:
			self.dfs(i, d, graph)

	def possible_paths(self, edges, n, s, d):
		graph = defaultdict(list)
		self.ans = 0
		for (a, b) in edges:
			graph[a].append(b)
		self.dfs(s, d, graph)
		return self.ans


from collections import defaultdict

class Solution:

	def ToGraph(self, edges):
		graph = defaultdict(list)
		for edge in edges:
			(u, v) = edge
			graph[u].append(v)
		return graph

	def possible_paths(self, edges, n, s, d):
		graph = self.ToGraph(edges)
		stack = [s]
		count = 0
		while stack:
			current = stack.pop()
			if current == d:
				count += 1
			for neighbour in graph[current]:
				stack.append(neighbour)
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):

		def vamsi(u, d, adj, visited, ans):
			if u == d:
				ans[0] += 1
				return
			visited[u] = 1
			for i in adj[u]:
				if i not in visited:
					vamsi(i, d, adj, visited, ans)
			del visited[u]
			return
		adj = {}
		for i in range(0, n):
			adj[i] = []
		for (i, j) in edges:
			adj[i].append(j)
		visited = {}
		ans = [0]
		vamsi(s, d, adj, visited, ans)
		return ans[0]


from collections import defaultdict, deque

class Solution:

	def possible_paths(self, edges, n, s, d):
		g = defaultdict(list)
		for (i, j) in edges:
			g[i].append(j)
		q = deque([s])
		res = 0
		while q:
			cur = q.popleft()
			if cur == d:
				res += 1
			for nei in g[cur]:
				q.append(nei)
		return res


class Solution:

	def possible_paths(self, edges, n, s, d):
		queue = []
		queue.append(s)
		count = 0
		while queue:
			ele = queue.pop(0)
			if ele == d:
				count += 1
			for i in edges:
				if i[0] == ele:
					queue.append(i[1])
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		visit = []
		visit.append(s)
		count = 0
		while visit:
			a = visit.pop()
			if a == d:
				count += 1
			for i in edges:
				if i[0] == a:
					visit.append(i[1])
		return count


class Solution:

	def possible_paths(self, edges, n, src, dest):
		x = [[] for i in range(n)]
		for (a, b) in edges:
			x[a].append(b)

		def f(i):
			if i == dest:
				return 1
			if dp[i] != None:
				return dp[i]
			ans = 0
			for j in x[i]:
				ans += f(j)
			dp[i] = ans
			return ans
		dp = [None for i in range(n)]
		return f(src)


class Solution:

	def dfs(self, s, adj, d, count):
		if s == d:
			count[0] += 1
		for i in adj[s]:
			self.dfs(i, adj, d, count)

	def possible_paths(self, edges, n, s, d):
		adj = [[] for i in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
		count = [0]
		self.dfs(s, adj, d, count)
		return count[0]


class Solution:

	def possible_paths(self, edges, n, s, d):
		visited = [False] * n
		count = [0]

		def checkPaths(start, dest):
			visited[start] = True
			if start == dest:
				count[0] += 1
			else:
				for edge in edges:
					if edge[0] == start and (not visited[edge[1]]):
						checkPaths(edge[1], dest)
			visited[start] = False
		checkPaths(s, d)
		return count[0]


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		graph = defaultdict(lambda : [])
		for (first, second) in edges:
			graph[first].append(second)
		stack = [s]
		count = 0
		while stack:
			item = stack.pop()
			if item == d:
				count += 1
			else:
				stack += graph[item]
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		x = {c: [] for c in range(n)}
		for (a, b) in edges:
			x[a].append(b)

		def dfs(node):
			if node == d:
				return 1
			ans = 0
			for j in x[node]:
				ans += dfs(j)
			return ans
		return dfs(s)


class Solution:

	def possible_paths(self, edges, n, s, d):
		x = [[] for i in range(n)]
		for (a, b) in edges:
			x[a].append(b)

		def check(i):
			if i == d:
				return 1
			ans = 0
			for j in x[i]:
				ans += check(j)
			return ans
		return check(s)


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = [[] for i in range(n)]
		for (i, j) in edges:
			adj[i].append(j)
		return self.dfs(s, adj, d)

	def dfs(self, node, adj, target):
		if node == target:
			return 1
		output = 0
		for i in adj[node]:
			output += self.dfs(i, adj, target)
		return output


class Solution:

	def possible_paths(self, edges, n, s, dest):
		if n == 1 or s == dest:
			return 1
		d = dict()
		for i in range(len(edges)):
			if edges[i][0] in d:
				d[edges[i][0]].append(edges[i][1])
			else:
				d[edges[i][0]] = [edges[i][1]]
		res = [0]

		def dfs(i, dest):
			if i in d:
				for j in d[i]:
					if j == dest:
						res[0] += 1
					else:
						dfs(j, dest)
		dfs(s, dest)
		return res[0]


class Solution:

	def possible_paths(self, edges, n, s, d):
		nodes = [s]
		cnt = 0
		while nodes:
			cur = nodes.pop(0)
			if cur == d:
				cnt += 1
			for i in edges:
				if i[0] == cur:
					nodes.append(i[1])
		return cnt


class Solution:

	def possible_paths(self, edges, n, s, d):
		count = [0]
		D = [[] for i in range(n)]
		for a in edges:
			D[a[0]].append(a[1])
		visited = [-1] * n
		self.x(D, s, d, count, visited)
		return count[0]

	def x(self, D, s, d, count, visited):
		visited[s] = 1
		if s == d:
			count[0] += 1
		for i in D[s]:
			if visited[i] == -1:
				self.x(D, i, d, count, visited)
		visited[s] = -1


class Solution:

	def possible_paths(self, edges, n, s, des):
		from collections import defaultdict
		d = defaultdict(list)
		for (i, j) in edges:
			d[i].append(j)
		visited = [False] * n
		res = set()

		def dfs(d, curr, des, path):
			nonlocal res, visited
			if curr == des:
				news = ''
				for i in path:
					news += str(i)
				res.add(news)
				return
			visited[curr] = True
			path.append(curr)
			for j in d[curr]:
				if visited[j] == False:
					dfs(d, j, des, path)
			visited[curr] = False
			path.pop()
		dfs(d, s, des, [])
		return len(res)


from collections import deque

class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = [[0] * n for _ in range(n)]
		for edge in edges:
			adj[edge[0]][edge[1]] = 1
		count = 0
		source = deque([s])
		while len(source):
			if source[0] == d:
				count += 1
			else:
				for i in range(n):
					if adj[source[0]][i]:
						source.append(i)
			source.popleft()
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = {}
		for edge in edges:
			(start, end) = (edge[0], edge[1])
			if start not in adj.keys():
				adj[start] = [end]
				adj[end] = []
			else:
				adj[start].append(end)
		ans = []

		def dfs(start, end, adj, ans, path=[]):
			path = path + [start]
			if start == end:
				ans.append(path.copy())
				path.pop()
				return
			if start not in adj.keys():
				return
			for neighbour in adj[start]:
				if neighbour not in path:
					dfs(neighbour, end, adj, ans, path)
			path.pop()
		dfs(s, d, adj, ans)
		return len(ans)


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		graph = defaultdict(list)
		for (parent, child) in edges:
			graph[parent].append(child)

		def dfs(curr, d):
			if curr == d:
				return 1
			res = 0
			for child in graph[curr]:
				res += dfs(child, d)
			return res
		return dfs(s, d)


class Solution:

	def getPossiblePath(self, hash, index, d, dp):
		if index == d:
			return 1
		if dp[index] != -1:
			return dp[index]
		if index in hash:
			list = hash[index]
			result = 0
			for i in list:
				result += self.getPossiblePath(hash, i, d, dp)
			dp[index] = result
			return dp[index]
		else:
			return 0

	def possible_paths(self, edges, n, s, d):
		hash = dict()
		dp = [-1 for i in range(n)]
		for i in edges:
			if i[0] not in hash:
				hash[i[0]] = [i[1]]
			else:
				hash[i[0]].append(i[1])
		return self.getPossiblePath(hash, s, d, dp)


from collections import defaultdict

class Solution:

	def DFS(self, s, d, graph, visited, ans):
		visited[s] = True
		if s == d:
			ans[0] += 1
		for neighbour in graph[s]:
			self.DFS(neighbour, d, graph, visited, ans)
		visited[s] = False
		return

	def possible_paths(self, edges, n, s, d):
		graph = defaultdict(list)
		for edge in edges:
			graph[edge[0]].append(edge[1])
		visited = [False for i in range(n)]
		ans = [0]
		self.DFS(s, d, graph, visited, ans)
		return ans[0]


class Solution:

	def possible_paths(self, edges, n, s, d):

		def dfs(s, d, edges, vis, ANS, ans):
			vis[s] = True
			ans.append(s)
			if s == d:
				ANS.append(ans)
				vis[ans.pop()] = False
				return
			for i in range(len(edges)):
				if edges[i][0] == s:
					if vis[edges[i][1]] == False:
						dfs(edges[i][1], d, edges, vis, ANS, ans)
			vis[ans.pop()] = False
			return
		vis = [False for i in range(n)]
		ANS = []
		ans = []
		dfs(s, d, edges, vis, ANS, ans)
		return len(ANS)


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		count = 0

		def dfs(v, visited):
			nonlocal count
			visited.add(v)
			for i in range(n):
				if i in graph[v] and i not in visited:
					dfs(i, visited)
			if v == d:
				count += 1
			visited.remove(v)
		graph = defaultdict(list)
		for i in range(len(edges)):
			graph[edges[i][0]].append(edges[i][1])
		dfs(s, set())
		return count


class Solution:

	def count_dfs(self, graph, u, d, visited):
		if u == d:
			return 1
		visited[u] = True
		ans = 0
		for v in graph[u]:
			if visited[v] == False:
				ans += self.count_dfs(graph, v, d, visited)
		visited[u] = False
		return ans

	def possible_paths(self, edges, n, s, d):
		graph = [[] for i in range(n)]
		for edge in edges:
			graph[edge[0]].append(edge[1])
		visited = [False for i in range(n)]
		return self.count_dfs(graph, s, d, visited)


class Solution:

	def possible_paths(self, edges, n, s, d):

		def dfs(adj, i, d):
			cnt = 0
			if i == d:
				cnt += 1
			for j in adj[i]:
				cnt += dfs(adj, j, d)
			return cnt
		adj = [[] for i in range(n)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
		total_cnt = dfs(adj, s, d)
		return total_cnt


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		if n == 0:
			return 1
		adj = defaultdict(list)
		for (u, v) in edges:
			adj[u].append(v)
		visited = [0] * n
		q = []
		q.append(s)
		count = 0
		if s == d:
			count += 1
		while q:
			node = q.pop(0)
			for i in adj[node]:
				if i == d:
					count += 1
				if visited[i] == 0:
					q.append(i)
					visited[i] == 1
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		if s == d:
			return 1
		count = 0
		l = [s]
		for j in l:
			for i in range(0, len(edges)):
				if edges[i][0] == j:
					if edges[i][1] == d:
						count += 1
						l.append(edges[i][1])
					else:
						l.append(edges[i][1])
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		q = []
		q.append(s)
		count = 0
		while q:
			curr = q.pop(0)
			if curr == d:
				count += 1
			for i in edges:
				if i[0] == curr:
					q.append(i[1])
		return count


class Solution:

	def possible_paths(self, edges, n, st, dest):
		if st == dest:
			return 1
		if len(edges) == 0:
			return -1
		adj = []
		for i in range(n):
			adj.append([])
		for pair in edges:
			(s, e) = pair
			adj[s].append(e)
		ans = [0]
		self.dfs(adj, ans, st, dest)
		return ans[0]

	def dfsUtil(self, st, dest, adj, ans):
		if st == dest:
			ans[0] += 1
			return
		for itm in adj[st]:
			self.dfsUtil(itm, dest, adj, ans)

	def dfs(self, adj, ans, st, dest):
		for itm in adj[st]:
			self.dfsUtil(itm, dest, adj, ans)


class Solution:

	def possible_paths(self, edges, n, s, d):
		ans = []

		def dfs(s, di, vis, d):
			if s == d:
				ans.append(1)
				return
			for k in range(len(di[s])):
				dfs(di[s][k], di, vis, d)
		di = {}
		vis = set()
		for i in range(n):
			di[i] = []
		for i in range(len(edges)):
			di[edges[i][0]].append(edges[i][1])
		dfs(s, di, vis, d)
		return len(ans)


def soln(g, s, d, l):
	if s == d:
		l[0] += 1
		return
	for i in g[s]:
		soln(g, i, d, l)
	return

class Solution:

	def possible_paths(self, edges, n, s, d):
		g = {}
		for i in range(n):
			g[i] = []
		l = [0]
		for i in edges:
			g[i[0]].append(i[1])
		soln(g, s, d, l)
		return l[0]


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = [[] for i in range(n)]
		result = 0
		for edge in edges:
			u = edge[0]
			v = edge[1]
			adj[u].append(v)
		queue = [s]
		while queue:
			node = queue.pop(0)
			if node == d:
				result += 1
				continue
			for it in adj[node]:
				queue.append(it)
		return result


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		dic = defaultdict(list)
		for i in edges:
			dic[i[0]].append(i[1])
		count = 0

		def checkcount(dic, s, d, visted, path):
			nonlocal count
			visited[s] = True
			if s == d:
				count += 1
			for i in dic[s]:
				if visted[i] == None:
					checkcount(dic, i, d, visted, path)
			visted[s] = None
		visited = [None] * n
		path = []
		checkcount(dic, s, d, visited, path)
		return count


class Solution:

	def __init__(self):
		self.res = 0

	def possible_paths(self, edges, n, s, d):
		adj = [[] for _ in range(n)]
		for edge in edges:
			adj[edge[0]].append(edge[1])
		self.dfs(adj, s, d)
		return self.res

	def dfs(self, adj, s, d):
		if s == d:
			self.res += 1
			return
		for i in adj[s]:
			self.dfs(adj, i, d)


class Solution:

	def possible_paths(self, edges, n, s, d):
		di = dict()
		for i in range(len(edges)):
			if edges[i][0] not in di:
				di[edges[i][0]] = []
			di[edges[i][0]].append(edges[i][1])

		def get_paths(start, end, path=[]):
			path = path + [start]
			if start == end:
				return [path]
			if start not in di:
				return []
			paths = []
			for node in di[start]:
				if node not in path:
					new_paths = get_paths(node, end, path)
					for p in new_paths:
						paths.append(p)
			return paths
		return len(get_paths(s, d))


class Solution:
	num = 0

	def possible_paths(self, edges, n, s, d):
		if edges == [] or s == d:
			return 1
		for edge in edges:
			if edge[0] == s:
				self.recurs(s, edges, edge)
		return self.num

	def recurs(self, choosing, edges, edge):
		if edge[1] == d:
			self.num += 1
		else:
			for e in edges:
				if edge[1] == e[0]:
					self.recurs(edge[1], edges, e)


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = [[] for i in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])

		def rec(adj, c):
			if c == d:
				return 1
			e = 0
			for i in adj[c]:
				e += rec(adj, i)
			return e
		return rec(adj, s)


class Solution:

	def possible_paths(self, edges, n, s, d):
		if s == d:
			return 1
		stack = [s]
		counter = 0
		neighbors = {}
		for edge in edges:
			(a, b) = (edge[0], edge[1])
			if a not in neighbors:
				neighbors[a] = [b]
			else:
				neighbors[a].append(b)
		path = str(s)
		vis = {i: False for i in range(n)}
		passed = set()
		while stack:
			top = stack[-1]
			state = False
			if top in neighbors:
				for neigh in neighbors[top]:
					temp = path + '_' + str(neigh)
					if temp not in passed:
						stack.append(neigh)
						path = temp
						if neigh == d:
							counter += 1
						passed.add(path)
						state = True
						vis[neigh] = True
						break
			if not state:
				pp = stack.pop()
				path = path[:-(1 + len(str(pp)))]
		return counter


class Solution:

	def possible_paths(self, edges, n, s, d):
		graph = {}
		for i in edges:
			if i[0] in graph.keys():
				graph[i[0]].append(i[1])
			else:
				graph[i[0]] = [i[1]]
		q = []
		q.append(s)
		totalPath = 0
		while len(q) > 0:
			if q[0] == d:
				totalPath += 1
			elif q[0] in graph.keys():
				for i in graph[q[0]]:
					q.append(i)
			q.pop(0)
		return totalPath


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = []
		for i in range(n):
			adj.append([])
		for edge in edges:
			adj[edge[0]].append(edge[1])
		queue = [s]
		ways = 0
		while queue:
			elem = queue.pop()
			if elem == d:
				ways += 1
				continue
			for itm in adj[elem]:
				queue.insert(0, itm)
		return ways


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = defaultdict(list)
		for (i, j) in edges:
			adj[i].append(j)
		ans = []
		stack = [(s, [0])]
		while stack:
			(node, path) = stack.pop()
			if node == d:
				ans.append(path)
			else:
				for adjnode in adj[node]:
					stack.append((adjnode, path + [adjnode]))
		return len(ans)


from collections import defaultdict

class Solution:

	def buildGraph(self, edges):
		graph = defaultdict(list)
		for (i, j) in edges:
			graph[i].append(j)
		return graph

	def possible_paths(self, edges, n, s, d):
		ways = 0
		graph = self.buildGraph(edges)
		visited = set()

		def dfs(curr):
			nonlocal ways
			if curr == d:
				ways += 1
				return
			if curr in visited:
				return
			visited.add(curr)
			for i in graph[curr]:
				dfs(i)
			visited.remove(curr)
		dfs(s)
		return ways


class Solution:

	def possible_paths(self, edges, n, s, d):
		if s == d:
			return 1
		count = 0
		for i in edges:
			if i[0] == s:
				count += self.possible_paths(edges, n, i[1], d)
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		q = []
		q.append(s)
		c = 0
		while q:
			a = q.pop(0)
			if a == d:
				c += 1
			for i in edges:
				if i[0] == a:
					q.append(i[1])
		return c


class Solution:

	def possible_paths(self, edges, n, s, d):

		def buildAdj(edges):
			adj = {}
			for edge in edges:
				(s, d) = (edge[0], edge[1])
				if s not in adj:
					adj[s] = []
				adj[s].append(d)
			return adj

		def dfs(s):
			if s == d:
				return 1
			count = 0
			if s in adj:
				neighbors = adj[s]
				for neighbor in neighbors:
					count += dfs(neighbor)
			return count
		adj = buildAdj(edges)
		return dfs(s)


class Solution:

	def possible_paths(self, edges, n, s, d):

		def dfs(u, count):
			if u == d:
				count[0] += 1
			for v in m[u]:
				dfs(v, count)
		import collections
		m = collections.defaultdict(list)
		for i in edges:
			m[i[0]].append(i[1])
		count = [0]
		dfs(s, count)
		return count[0]


class Solution:

	def possible_paths(self, edges, n, s, d):
		q = [s]
		c = 0
		adj = [[] for _ in range(n)]
		for i in edges:
			adj[i[0]].append(i[1])
		while q:
			x = q.pop(0)
			for i in adj[x]:
				q.append(i)
			if x == d:
				c = c + 1
		return c


class Solution:

	def possible_paths(self, edges, n, s1, d1):
		adj = {}
		for i in range(n):
			adj[i] = []
		for i in edges:
			(s, d) = (i[0], i[1])
			adj[s].append(d)
		visited = [False for i in range(n)]
		output = [0]

		def dfs(s, d):
			visited[s] = True
			if s == d:
				output[0] += 1
				visited[d] = False
				return
			for i in adj[s]:
				if visited[i] == False:
					dfs(i, d)
			visited[s] = False
		dfs(s1, d1)
		return output[0]


from collections import defaultdict

class Solution:

	def __init__(self):
		self.count = 0
		self.adj = defaultdict(list)

	def possible_paths(self, edges, n, s, d):
		for (i, j) in edges:
			self.adj[i].append(j)
		self.getpaths(s, d)
		return self.count

	def getpaths(self, s, d):
		if s == d:
			self.count += 1
			return
		for i in self.adj[s]:
			self.getpaths(i, d)
		return


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		queue = []
		queue.append(s)
		count = 0
		while queue:
			node = queue.pop(0)
			if node == d:
				count += 1
			for i in edges:
				if i[0] == node:
					queue.append(i[1])
		return count


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj = [[] for _ in range(n)]
		for (u, v) in edges:
			adj[u].append(v)
		visited = [False] * n
		paths = [0]
		self.dfs(s, d, adj, visited, paths)
		return paths[0]

	def dfs(self, s, d, adj, visited, paths):
		visited[s] = True
		if s == d:
			paths[0] += 1
		for ngbr in adj[s]:
			if not visited[ngbr]:
				self.dfs(ngbr, d, adj, visited, paths)
		visited[s] = False


class Solution:

	def possible_paths(self, edges, n, s, d):
		vis = [0] * n
		adj = [[] for i in range(n)]
		for (i, j) in edges:
			adj[i].append(j)

		def count_dfs(node):
			if node == d:
				return 1
			vis[node] = 1
			res = 0
			for i in adj[node]:
				if not vis[i]:
					res += count_dfs(i)
			vis[node] = 0
			return res
		return count_dfs(s)


class Solution:

	def possible_paths(self, edges, n, s, d):
		graph = {}
		for vertex in range(n):
			graph[vertex] = []
		for (u, v) in edges:
			graph[u].append(v)
		self.count = 0
		visit = set()

		def dfs(s):
			if s == d:
				self.count += 1
				return
			visit.add(s)
			for nei in graph[s]:
				if nei not in visit:
					dfs(nei)
			visit.remove(s)
		dfs(s)
		return self.count


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		res = 0

		def dfs(node):
			nonlocal res
			if node == d:
				res += 1
				return
			for nei in adj[node]:
				dfs(nei)
		adj = defaultdict(list)
		for (src, dist) in edges:
			adj[src].append(dist)
		dfs(s)
		return res


class Solution:

	def __init__(self):
		self.count = 0

	def dfs(self, s, d, adj):
		if s == d:
			self.count += 1
			return
		for id in adj[s]:
			self.dfs(id, d, adj)

	def possible_paths(self, edges, n, s, d):
		adj = [[] for _ in range(n)]
		for elem in edges:
			adj[elem[0]].append(elem[1])
		self.dfs(s, d, adj)
		return self.count


class Solution:

	def possible_paths(self, edges, n, s, d):
		adj_list = {}
		visited = [0] * n
		ans = []
		for k in range(0, len(edges)):
			first = edges[k][0]
			second = edges[k][1]
			if first not in adj_list:
				adj_list[first] = [second]
			else:
				adj_list[first].append(second)
		self.dfs(s, d, adj_list, visited, ans)
		return len(ans)

	def dfs(self, s, d, adj_list, visited, ans):
		if s == d:
			ans.append(1)
			return
		visited[s] = 1
		if s in adj_list:
			for j in adj_list[s]:
				if visited[j] == 0:
					self.dfs(j, d, adj_list, visited, ans)
					visited[j] = 0
		return


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):
		graph = defaultdict(list)
		for (src, dst) in edges:
			graph[src].append(dst)
		visited = set()
		visited.add(s)
		paths = []

		def dfs_traverse(cur_node, path):
			if cur_node == d:
				paths.append(path[:])
				return
			for neighbor in graph[cur_node]:
				if neighbor in visited:
					continue
				visited.add(neighbor)
				dfs_traverse(neighbor, path + [neighbor])
				visited.remove(neighbor)
		dfs_traverse(s, [s])
		return len(paths)


from collections import defaultdict

class Solution:

	def dfs(self, v, visited, d, arr, res, graph):
		visited[v] = True
		arr.append(v)
		if v == d:
			res.append(arr.copy())
		else:
			for i in graph[v]:
				if visited[i] == False:
					self.dfs(i, visited, d, arr, res, graph)
		arr.pop()
		visited[v] = False

	def possible_paths(self, edges, n, s, d):
		dct = defaultdict(list)
		for edge in edges:
			dct[edge[0]].append(edge[1])
		res = []
		visited = [False] * n
		self.dfs(s, visited, d, [], res, dct)
		return len(res)


class Solution:

	def possible_paths(self, edges, n, s, d):
		global count
		count = 0

		def dfs(root):
			global count
			if root == d:
				count += 1
				return
			for child in [edge[1] for edge in edges if edge[0] == root]:
				dfs(child)
		dfs(s)
		return count


from collections import defaultdict

class Solution:

	def possible_paths(self, edges, n, s, d):

		def dfs(vis, s, d):
			vis[s] = True
			if s == d:
				count[0] += 1
			for u in adj[s]:
				if vis[u] == False:
					dfs(vis, u, d)
			vis[s] = False
		adj = [[] for i in range(n)]
		for (i, j) in edges:
			adj[i].append(j)
		count = [0]
		vis = [False for _ in range(n)]
		dfs(vis, s, d)
		return count[0]


class Solution:

	def possible_paths(self, edges, n, s, d):
		g = [[] for _ in range(n)]
		for i in edges:
			u = i[0]
			v = i[1]
			g[u].append(v)
		dp = [-1 for _ in range(n)]

		def paths(node):
			if node == d:
				return 1
			if dp[node] != -1:
				return dp[node]
			c = 0
			for i in g[node]:
				c += paths(i)
			return c
		return paths(s)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m, s, d) = input().split()
		n = int(n)
		m = int(m)
		s = int(s)
		d = int(d)
		edges = []
		for _ in range(m):
			(x, y) = input().split()
			x = int(x)
			y = int(y)
			edges.append([x, y])
		obj = Solution()
		ans = obj.possible_paths(edges, n, s, d)
		print(ans)