Minimum Barriers Problem

You are given a village with n lakes and m one-directional rivers connecting them. Each river flows from lake u to lake v. To prevent the water from propagating uncontrollably, barriers must be placed on some of these rivers. Your task is to determine, for each lake, the minimum number of barriers required so that water from that lake does not reach further lakes. Note that the last lake in any connectivity chain (i.e. a lake with no outgoing river) requires no barrier.

The river network is guaranteed to form a Directed Acyclic Graph (DAG), meaning that there exists an ordering of the lakes such that every river flows from an earlier lake to a later lake.

Input: The first line contains two integers, \( n \) and \( m \). Each of the following \( m \) lines contains two integers \( u \) and \( v \), indicating there is a river flowing from lake \( u \) to lake \( v \).

Output: Output a single line with \( n \) space-separated integers. The \( i\)-th integer should represent the minimum number of barriers required for lake \( i \).

Note: The concept behind the solution is to use a topological sort on the DAG and, iterating in reverse order, count for each lake the number of outgoing rivers that lead to not-yet-protected lakes. Once an outgoing river of a lake is counted for protection, the downstream lake is marked as visited so that any future encounter does not count another barrier for the same lake.

inputFormat

Standard input (stdin) is used for input. The first line contains two integers \( n \) and \( m \). Then \( m \) lines follow; each line contains two integers representing a directed edge from lake \( u \) to lake \( v \).

outputFormat

Standard output (stdout) should output a single line containing \( n \) space-separated integers. The \( i \)-th integer corresponds to the minimum number of barriers required for lake \( i \).

## sample

4 4
1 2
2 3
3 4
1 3

1 1 1 0

</p>