题目描述

Dream SMP 具有 $m$ 位玩家，编号为 $1$ 至 $m$。初始时，每一位玩家生命数量为 $3$。一位玩家 公认活着（canonically alive） 当且仅当生命值非零。

Dream SMP 经常发生大型战争，于是会有玩家杀（PvP）别的玩家。对于活着玩家 $u$ 与 $v$，如果 $u$ 杀 $v$，$v$ 的生命数量扣除一次。注意，如果 $u$ 或 $v$ 不为公认活着，杀没有影响。

总共按时序记录了 $n$ 次追杀 $1,2,\dots,n$，其中第 $k$ 次追杀为 $u_k$ 杀 $v_k$。

DreamXD（玩家 $0$）解锁了时空穿越超能力。他现在可以选取任何 $i,v$ 使得 $1\le i\le n+1$ 并且 $1\le v\le m$，穿越到第 $i-1$ 次追杀之后与第 $i$ 次追杀之前，并追杀玩家 $v$。$i=n+1$ 表示穿越到第 $n$ 次追杀后。

不同 $i$ 和 $v$ 可能导致最终活着玩家集合不同。对于每一个 $x$ 使得 $0\le x\le m$，DreamXD 想知道，有多少种 $i,v$ 使最后公认活着玩家集合恰好含有 $x$ 位玩家？

输入格式

第一行两个正整数 $n,m$。
接下来 $n$ 行，第 $k$ 行两个正整数 $u_k,v_k$，表示在第 $k$ 时刻，$u_k$ 追杀 $v_k$。

输出格式

输出一行 $m+1$ 个正整数，其中第 $x$ 个为最终有 $x-1$ 位玩家活（不包含 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

提示

样例 2 解释

本样例对应 Dream SMP 当前（4/26/2021) 情况，仅包含公认死亡，即对应剧本，的次数：

• 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

本题采用捆绑测试。

• Subtask 1（5 pts）：$n\le5$，$m=1$。
• Subtask 2（11 pts）：$n,m\le100$。
• Subtask 3（41 pts）：$n\le10^3$。
• Subtask 4（43 pts）：没有特殊限制。

对于 $100\%$ 的数据，$1\le n\le6\times10^4$，$1\le m\le10^3$，$1\le u_i,v_i\le m$。