P4230 Cyclic Pathogens

### (I) Cave Walking down along a narrow, slanted karst cave, it really feels like a journey to the center of the earth. Let me tell you, there is a vast underground world called the Former Hell. It is home to youkai shunned by people on the surface. Although it sounds scary, after Hell was abandoned, everything became orderly. There is an open space ahead; it seems someone is there. "A visitor from the surface? Hello." At last, we met the residents of the underground. The two youkai before us are Kurodani Yamame and Kisume. Kisume stays in a small bucket, hanging in the air, discussing something with Yamame. "Wow, what are you discussing?" "Mm, it's about viruses. You wouldn’t understand." I forgot to mention, Yamame can manipulate diseases, so discussing such topics is only natural. But curiosity is hard to resist. Let's pretend we can help and keep asking. "Well then, if you can help, that would be great." "Mm, what I mainly want to know is how interactions among pathogens affect the disease. Look, if we treat different kinds of pathogens as points, and their interactions as lines connecting the points, then if a cycle is formed, the virus’s power is greatly enhanced. I call this a reinforcement cycle." "There are many kinds of interactions among pathogens. I want to study how important each interaction is in forming reinforcement cycles." Ah, it sounds complicated, but if we help her, the underground youkai might be friendlier to us. Also, points, edges, cycles? These terms seem familiar. Maybe I really can help? Let’s keep asking for details. Mm, the information we got has been written down on this sheet of paper.

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.)

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 one line with $m$ numbers. The $i$-th number denotes how many reinforcement intervals contain the $i$-th influence. Numbers are separated by spaces.

### 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