Description

Dream SMP has $m$ players, numbered from $1$ to $m$. Initially, every player has $3$ lives. A player is canonically alive if and only if their number of lives is non-zero.

Large wars often happen on Dream SMP, so players may kill (PvP) other players. For two canonically alive players $u$ and $v$, if $u$ kills $v$, then $v$ loses one life. Note that if $u$ or $v$ is not canonically alive, the kill has no effect.

In total, $n$ manhunts are recorded in chronological order, numbered $1,2,\dots,n$, where the $k$-th manhunt is $u_k$ killing $v_k$.

DreamXD (player $0$) has unlocked the superpower of time travel. He can now choose any $i,v$ such that $1 \le i \le n+1$ and $1 \le v \le m$, travel to the moment after the $(i-1)$-th manhunt and before the $i$-th manhunt, and then manhunt (kill) player $v$. The case $i = n+1$ means traveling to after the $n$-th manhunt.

Different choices of $i$ and $v$ may lead to different final sets of players who are canonically alive. For each $x$ with $0 \le x \le m$, DreamXD wants to know: how many pairs $(i,v)$ make the final set of canonically alive players contain exactly $x$ players?

Input Format

The first line contains two positive integers $n,m$.
The next $n$ lines each contain two positive integers $u_k,v_k$, meaning that at time $k$, $u_k$ manhunts $v_k$.

Output Format

Output one line with $m+1$ positive integers, where the $x$-th integer is the number of plans such that finally there are exactly $x-1$ players alive (excluding Dream).

2 2
1 2
1 2

0 3 3

23 22
2 1
14 10
4 9
12 11
2 1
4 9
12 3
5 3
5 6
4 13
5 5
15 15
7 22
7 22
7 1
6 3
1 2
1 2
2 1
18 16
19 17
20 8
21 8

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 72 456 0 0

Hint

Explanation for Sample 2

This sample corresponds to the Dream SMP situation at the time (4/26/2021), and only includes canonical deaths, i.e. those in the script:

• Aug 2, 2020: Tommy killed by Dream
• Aug 2, 2020: Fundy killed by George
• Aug 2, 2020: Wilbur killed by Punz
• Aug 2, 2020: Tubbo killed by Sapnap
• Aug 2, 2020: Tommy killed by Dream
• Sep 2, 2020: Wilbur killed by Punz
• Oct 16, 2020: Tubbo killed by Techno
• Oct 16, 2020: Schlatt killed by Techno
• Oct 17, 2020: Schlatt killed by Quackity
• Nov 16, 2020: Wilbur killed by Philza
• Nov 16, 2020: Schlatt killed by Schlatt
• Dec 6, 2020: Karl killed by Karl
• Dec 14, 2020: Mexican Dream killed by Natural Causes
• Dec 14, 2020: Mexican Dream killed by Natural Causes
• Dec 14, 2020: Mexican Dream killed by Dream
• Dec 16, 2020: Quackity killed by Techno
• Jan 20, 2021: Dream killed by Tommy
• Jan 20, 2021: Dream killed by Tommy
• Mar 1, 2021: Tommy killed by Dream
• Mar 12, 2021: Connor killed by Ranboo
• Mar 23, 2021: Ponk killed by Sam
• Apr 18, 2021: Skeppy killed by Bad
• Apr 26, 2021: Foolish killed by Bad

This problem uses bundled testdata.

• Subtask 1 (5 pts): $n \le 5$, $m = 1$.
• Subtask 2 (11 pts): $n,m \le 100$.
• Subtask 3 (41 pts): $n \le 10^3$.
• Subtask 4 (43 pts): no special constraints.

For $100\%$ of the testdata, $1 \le n \le 6 \times 10^4$, $1 \le m \le 10^3$, $1 \le u_i,v_i \le m$.

Translated by ChatGPT 5