Description

Problem summary:

There are $n$ types of pathogens, and there are $m$ kinds of undirected influences among them. The $i$-th influence occurs between pathogens $u_i$ and $v_i$, specifically between two pathogens.

We arrange all the influences in order by their indices to form a sequence. If an interval contains a cycle, then that interval is called a reinforcement interval.

For each influence, count in how many reinforcement intervals it appears.

So, how can we compute the result efficiently?

(For the subsequent story, see the editorial of this problem. Please proceed to T2.)

Input Format

The first line contains a number $m$.

Then $m$ lines follow; each line contains two numbers $u_i$, $v_i$, separated by a space.

Output Format

Output one line with $m$ numbers. The $i$-th number denotes how many reinforcement intervals contain the $i$-th influence. Numbers are separated by spaces.

5
1 2
2 3
3 4
1 4
4 2

2 3 3 3 2

Hint

Sample explanation:

The first influence appears in two reinforcement intervals: [1,4] and [1,5].

The second influence appears in three reinforcement intervals: [1,4], [1,5], and [2,5].

The third influence appears in three reinforcement intervals: [1,5], [1,4], and [2,5].

The fourth influence appears in three reinforcement intervals: [1,4], [2,5], and [1,5].

The fifth influence appears in two reinforcement intervals: [2,5] and [1,5].

Note: reinforcement intervals are formed by “influences” (edges), not by “pathogens” (vertices).

Constraints

$n\leqslant2m\leqslant400000$

Test points 1–2, total 10 points, $m\leqslant5$.

Test points 3–6, total 20 points, $m\leqslant200$.

Test points 7–12, total 30 points, $m\leqslant5000$.

Test points 13–15, total 15 points, $m\leqslant50000$.

Test points 16–18, total 15 points, $m\leqslant50000$, bundled test.

Test points 19–22, total 10 points, $m\leqslant200000$, bundled test.

by oscar

Translated by ChatGPT 5