Connecting Warehouses

You are given a directed graph \(G=(V,E)\) representing a network of warehouses and routes. Each warehouse is represented by a node and each existing route by a directed edge. There are \(n\) warehouses and \(m\) existing routes. A designated start warehouse \(s\) is provided. Your task is to determine the minimum number of additional routes (directed edges) that must be added so that every warehouse in \(V\) becomes reachable from \(s\).

Input Format: The first line of input contains three integers \(n\), \(m\), and \(s\). This is followed by \(m\) lines, each containing two integers \(u\) and \(v\) indicating a directed edge from warehouse \(u\) to warehouse \(v\).

Output Format: Print a single integer, the minimal number of additional routes necessary.

Note: The solution involves performing a breadth-first search (BFS) from the start node and then using a reverse graph to assess which nodes are not connected. Formally, the answer is the size of the set:

[ { x \in V \mid x \text{ is reachable from some unreachable node via the reverse graph} } \setminus { x \in V \mid x \text{ is reachable from } s } ]

inputFormat

The input is given from stdin and has the following format:

n m s
u1 v1
u2 v2
... 
um vm

Where:

• \(n\) is the number of warehouses (nodes).
• \(m\) is the number of existing routes (directed edges).
• \(s\) is the designated starting warehouse.
• Each of the next \(m\) lines contains two integers \(u\) and \(v\) which denote a directed edge from warehouse \(u\) to warehouse \(v\).

outputFormat

Output a single integer to stdout — the minimal number of additional routes required so that every warehouse is reachable from \(s\).

## sample

5 4 1
1 2
2 3
4 5
5 1

2