Minimum Broadcast Cities for Complete Message Spread

Given \(n\) cities connected by directed roads, a message spreads along these roads. Determine the minimum number of cities in which the message must be initially released so that every city eventually receives the message.

Formally, you are given a directed graph \(G=(V,E)\) where \(V\) represents the cities and \(E\) represents the one-way roads. You need to choose a set of starting cities such that for every city \(v \in V\), there is a path from at least one starting city to \(v\). The answer is equal to the number of strongly connected components with no incoming edge from any other component in the condensation graph of \(G\).

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of cities and roads respectively. The next \(m\) lines each contain two integers \(u\) and \(v\), indicating a directed road from city \(u\) to city \(v\). Cities are numbered from 1 to \(n\).

outputFormat

Output a single integer: the minimum number of cities where the message must be initially released to ensure that every city receives the message.

sample

5 4
1 2
2 3
3 4
4 5

1