#1439. YY的问题

题目描述

做了AHOI2006的Board一题，YY觉得天昏地暗，回肠荡气，余音绕梁…… YY也就想出了一个问题：对于一个完全二分图，有多少种不同的完备匹配？ 结果YY发现这个问题太简单了，根本难不倒大家。 YY就改进了一下，对于一个有2N个节点的完全二分图，包含边数为0，为1，为2……为N的匹配分别有多少？ YY经过研究，发现此题存在N种解法，甚至可以交表！ 绝望的YY心想，这下子伤自尊了，题目没法出了。好在他这时突然又想起了Board那题。“对啊！”YY说，“我在图中删去M条边，再问你们包含边数为0，为1，为2……为N的匹配分别有多少，这样就没办法交表了。” 于是，问题就出来了。可惜的是，这下子YY真的不会做了……大家会做的话帮一下YY吧。

输入格式

第一行两个整数N和M，定义见上文。1<=N<=500，0<=M<=20。 后面M行，每行有两个数A和B，表示YY删去的一条边——二分图左边部分编号为A的节点与二分图右边部分编号为B的节点。二分图的两个部分的节点都分别编号为1..N。

输出格式

N+1行，分别表示包含边数为0，为1，为2……为N的匹配分别有多少。

样例

样例输入

3 5  

1 2  

1 3  

2 1  

2 3  

3 1  

样例输出

1  

4  

4  

1  

数据范围与提示