409403: GYM103500 B Timelines

$$$m$$$ characters play on the SMP, numbered from $$$1$$$ to $$$m$$$. Initially, each character has $$$3$$$ lives; a character is canonically alive if and only if they have a positive number of lives.

The SMP is not peaceful. During wars and other internal conflicts one character may kill another character (possibly themselves). When $$$u$$$ kills $$$v$$$, $$$v$$$ loses one life only when both $$$u$$$ and $$$v$$$ are canonically alive; otherwise, nothing happens.

$$$n$$$ such events have happened, given by pairs two sequences $$$u_1,u_2,\dots,u_n$$$ and $$$v_1,v_2,\dots,v_n$$$. In the $$$i$$$-th such event in chronological order, character $$$u_i$$$ kills $$$v_i$$$.

DreamXD can control lives in alternate universes. For all $$$i$$$ and $$$v$$$ where $$$0\le i\le n$$$ and $$$1\le v\le m$$$, he creates an alternate universe where events happen in the given order, except immediately after the $$$i$$$-th event, where one life is deducted from character $$$v$$$. When $$$i=0$$$, this happens before the first event.

For each integer $$$x$$$ where $$$0\le x\le m$$$, count the number of alternate universes that finish with $$$x$$$ characters canonically alive.

The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 6\times 10^4$$$, $$$1\le m\le 10^3$$$).

The $$$i$$$-th of the following $$$n$$$ lines contain two positive integers, representing $$$u_i$$$ and $$$v_i$$$.

Output one line containing $$$m+1$$$ integers: the number of alternate universes that finish with $$$x$$$ characters canonically alive for $$$x=0,1,2,\dots,m$$$.

• In the first subtask, worth $$$5$$$ points, $$$n\le 5$$$ and $$$m=1$$$.
• In the second subtask, worth $$$11$$$ points, $$$n,m\le 100$$$.
• In the third subtask, worth $$$41$$$ points, $$$n\le 10^3$$$.
• In the final subtask, worth $$$43$$$ points, no additional constraints are posed.

2 2
1 2
1 2

0 3 3