Count Power Outage

Problem Statement

In a power network, substations supply energy to other substations. However, due to a fault at one of the substations, power loses its way from that node onward. Given the network represented as a directed graph (where an edge from node u to node v indicates that v receives power from u), your task is to determine how many substations will suffer a power outage. The faulty substation itself will lose power too.

More formally, you are given an integer n representing the number of substations, and an integer m representing the number of directed connections between substations. Then m lines follow, each containing two integers u and v which denote a directed connection from u to v. Finally, you are given a substation number f that is faulty. Consider all substations that are reachable from the faulty substation f following the direction of the edges (including f itself); these substations will lose power.

The traversal performed follows the algorithm:

• Use Breadth-First Search (BFS) starting from the faulty substation.
• Count all substations that can be reached.

Mathematically, if we denote by \(G=(V,E)\) the directed graph of the power network and \(f\) as the faulty substation, you are to find \(|\{x \in V : f \rightarrow x \text{ is reachable}\}|\).

inputFormat

Input Format

The input is given from stdin and is formatted as follows:

• The first line contains three integers: \(n\) (the number of substations), \(m\) (the number of directed edges), and \(f\) (the index of the faulty substation).
• The following \(m\) lines each contain two integers \(u\) and \(v\), representing a directed edge from substation \(u\) to substation \(v\).

outputFormat

Output Format

Output a single integer to stdout which is the number of substations that will lose power, including the faulty substation.

## sample

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

4