#P1439. YY的问题

    ID: 450 传统题 2000ms 256MiB 尝试: 28 已通过: 1 难度: 6 上传者: 标签>CF2100提高容斥原理回溯搜索可行性剪枝高精度加法高精度减法高精度乘法高精度除法难度分类

YY的问题

YY 的问题

题目描述

有一张完全二分图,左部和右部各有 nn 个顶点,每一侧的顶点分别编号为 1,2,…,n1,2,\ldots,n。起初,每一个左部顶点都与所有右部顶点连有一条边。

现在删除其中的 mm 条边。删除第 ii 条边由两个整数 ui,viu_i,v_i 指定,表示删除左部顶点 uiu_i 与右部顶点 viv_i 之间的边。

匹配是一个边的集合,其中任意两条边都不共用端点。匹配的大小等于集合中边的数量。

请你分别计算,在删边后的二分图中,大小恰好为 0,1,2,…,n0,1,2,\ldots,n 的匹配各有多少种。

两个匹配不同,当且仅当它们选取的边集合不同。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 ui,viu_i,v_i,表示删除左部顶点 uiu_i 与右部顶点 viv_i 之间的边。

输出格式

输出 n+1n+1 行。

第 k+1k+1 行(0≤k≤n0\le k\le n)输出一个整数,表示恰好包含 kk 条边的匹配数量。

答案不取模,必须输出完整的十进制整数。

样例输入

3 5
1 2
1 3
2 1
2 3
3 1

样例输出

1
4
4
1

样例解释

删除指定的五条边后,剩余四条边为 (1,1)(1,1)、(2,2)(2,2)、(3,2)(3,2)、(3,3)(3,3),其中二元组的第一个元素是左部编号,第二个元素是右部编号。

  • 大小为 00:空匹配,共 11 种;
  • 大小为 11:选择任意一条剩余边,共 44 种;
  • 大小为 22:共 44 种;
  • 大小为 33:只有 {(1,1),(2,2),(3,3)}\{(1,1),(2,2),(3,3)\},共 11 种。

数据范围与约定

对于所有测试数据:

$$1\le n\le 500,\qquad 0\le m\le 20,\qquad 1\le u_i,v_i\le n.$$

输入描述的是待删除的边;同一条边即使重复指定,删除效果也不变。本套测试数据中的删除边互不重复。

提示:答案可能远大于 6464 位整数范围。