DreamXD Time-Travel Kill

In the Dream SMP world there are m players numbered from 1 to m and each starts with 3 life points. A player is said to be canonically alive if and only if his life count is nonzero. The server records a total of n kill events. In the k-th event, player \(u_k\) kills player \(v_k\). For any kill event, if both the attacker and the victim are canonically alive at that moment then the victim loses one life point; otherwise the event has no effect.

DreamXD (player 0) has unlocked a time‐travel superpower. He can choose any pair \((i,v)\) with \(1 \le i \le n+1\) and \(1 \le v \le m\), travel in time to a moment between the \(i-1\)-th and \(i\)-th kill (with \(i=n+1\) meaning after the last kill), and perform an extra kill on player \(v\). His kill works the same way as any other kill: if at that moment the victim is canonically alive then its life drops by one; if not, nothing happens.

The original sequence of kill events is processed in order (from 1 to \(n\)), and the extra kill event is inserted at the chosen time. Note that an event (whether original or the extra kill) will only reduce the victim's life by one if both the attacker and the victim are alive (i.e. have a positive life count) at that moment. In the original simulation (with no extra kill), every player starts with 3 lives and the event decreases the victim's life by 1 if effective. Hence a player may only be attacked effectively at most 3 times. Let the number of effective attacks on player \(v\) in the original simulation be \(k_v\; (0\le k_v\le 3)\}. Consequently, player \(v\) is originally alive if and only if \(k_v<3\) (since his final life is \(3-k_v\)).

DreamXD’s extra kill event does not affect the other players. However, if he targets a player v whose original effective attack count is exactly 2 then in the original simulation \(v\) would survive (with 1 life point), but the extra kill reduces its life to 0, changing the final alive status. In summary, if DreamXD targets a player \(v\) with:

• \(k_v\;=\;0\) or \(1\): the extra kill lowers \(v\u2019s\) life by 1 but \(v\) remains alive.
• \(k_v\;=\;2\): originally \(v\) would be alive, yet the extra kill makes \(v\) die.
• \(k_v\;=\;3\): \(v\) is already dead, so nothing changes.

Let \(A_0\) be the number of players (among 1 to \(m\)) that are originally alive, i.e. those with \(k_v\;\in\;\{0,1\}\). Then, notice that when DreamXD applies his extra kill, his only possible effect is to change the status of a player with \(k_v = 2\) (turning an alive player into a dead one). For any pair \((i,v)\):

• If \(v\) is such that \(k_v \neq 2\), the final alive count remains \(A_0\).
• If \(v\) has \(k_v = 2\) then the final alive count becomes \(A_0 - 1\).

Your task is: for every \(x\) with \(0 \le x \le m\), compute the number of pairs \((i,v)\) (with \(1\le i\le n+1\) and \(1\le v\le m\)) such that after inserting DreamXD's extra kill event at that moment targeting \(v\), the final set of canonically alive players has exactly \(x\) players.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of kill events and the number of players, respectively).

Each of the following \(n\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le m\)), denoting that in that event player \(u\) kills player \(v\), subject to the rule that the event is effective only if both are alive at that time.

You may assume that all input values are valid and that \(0 \le n\) and \(1 \le m\).

outputFormat

Output \(m+1\) space‐separated integers. The \(x\)-th integer (with \(0 \le x \le m\)) should be the number of pairs \((i,v)\) (\(1 \le i \le n+1\), \(1 \le v \le m\)) such that the final number of canonically alive players is exactly \(x\).

sample

3 3
1 2
2 3
1 2

0 4 8 0