P7568 "MCOI-05" Manhunt

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?

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

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