Reachable Nodes in a Directed Graph

You are given a directed graph with n nodes numbered from 1 to n and m edges. Each edge is represented by two integers u and v, indicating a directed edge from node u to node v. Given a starting node s, your task is to compute the number of nodes that are reachable from s using a Breadth-First Search (BFS) traversal.

The graph can be disconnected and may contain cycles. Make sure to handle graphs with no edges and cycles properly.

In mathematical terms, if we denote by \( G = (V, E) \) the graph and \( R(s) \) the set of nodes reachable from s, you are to determine \( |R(s)| \), where \(|\cdot|\) represents the cardinality of the set.

inputFormat

The first line of input contains three integers n, m and s separated by spaces, where:

• n is the number of nodes.
• m is the number of edges.
• s is the starting node.

The next m lines each contain two integers u and v representing a directed edge from node u to node v.

outputFormat

Output a single integer representing the number of nodes reachable from the given starting node s.

6 7 1
1 2
2 3
3 4
3 5
2 6
6 5
5 4

6