Cycle Detection in Influence Intervals

We are given \(n\) pathogens and \(m\) undirected influences. The \(i\)th influence occurs between pathogens \(u_i\) and \(v_i\). All influences are arranged in a fixed sequence (by their indices). An interval of influences, i.e. a contiguous subsequence, is called a strengthened interval if the subgraph induced by the influences in that interval contains a cycle.

Formally, let the influences be indexed from \(1\) to \(m\). An interval \([L, R]\) is strengthened if the graph formed by the edges \(\{(u_i, v_i) : L \le i \le R\}\) contains at least one cycle. For each influence \(i\), your task is to compute the number of strengthened intervals in which it appears (i.e. intervals \([L, R]\) with \(L \le i \le R\) such that the corresponding subgraph is cyclic).

Can you design an efficient algorithm to compute the answer for each influence? (For hints, see the editorial.)

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the number of pathogens and the number of influences, respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\) indicating that there is an undirected influence between pathogens \(u\) and \(v\).

outputFormat

Output \(m\) integers separated by spaces, where the \(i\)th integer represents the number of strengthened intervals that include the \(i\)th influence.

sample

3 3
1 2
2 3
1 3

1 1 1