#K83032. Highest Impact Items
Highest Impact Items
Highest Impact Items
You are given N items labeled from 1 to N and M directed preference pairs. Each preference pair is given as a tuple \((A, B)\), meaning that item \(A\) is preferred over item \(B\). The impact of an item is defined as the total number of items it is directly or indirectly preferred over. In other words, for an item \(i\), its impact is the number of items \(j\) such that there exists a path from \(i\) to \(j\) in the given directed graph.
Your task is to find all the items that have the highest impact and output them in ascending order. Note that the relationships may contain cycles or disconnected components.
Definition:
The impact of an item \(i\) is given by:
\[
impact(i) = |\{ j \mid \text{there exists a directed path from } i \text{ to } j \}|
\]
inputFormat
The input is given via standard input (stdin) and has the following format:
N M A1 B1 A2 B2 ... AM BM
where:
- N is the number of items.
- M is the number of preference pairs.
- Each of the next M lines contains two integers \(A\) and \(B\) indicating that item \(A\) is preferred over item \(B\).
outputFormat
Output the items with the highest impact, each on a new line, in ascending order.
## sample4 3
2 1
3 2
4 3
4
</p>