Minimum Reversals for Bidirectional Connectivity

You are given a directed graph representing a series of villages connected by one-way portals. The graph consists of n villages and m directed edges. Your task is to determine the minimum number of portal reversals required to ensure that the graph becomes bidirectionally connected — meaning that any village can be reached from any other village.

In mathematical form, let \( indegree[i] \) denote the number of incoming portals to village \( i \). It turns out that under the given constraints, the answer can be computed as:

[ \text{answer} = \sum_{i=1}^{n} \mathbb{1}_{{ indegree[i] = 0 }} ]

That is, the minimum number of portal reversals required is equal to the number of villages that initially have no incoming portal.

inputFormat

The input is given via standard input (stdin) and has the following format:

• An integer n representing the number of villages.
• An integer m representing the number of directed portals (edges).
• m lines follow, each containing two space-separated integers u and v indicating a portal from village u to village v.

You can assume that the villages are numbered from 1 to n.

outputFormat

Output a single integer (printed to stdout): the minimum number of portal reversals required to make the graph bidirectional.

4
3
1 2
2 3
3 4

1