#P1439. YY的问题
YY的问题
YY 的问题
题目描述
有一张完全二分图,左部和右部各有 个顶点,每一侧的顶点分别编号为 。起初,每一个左部顶点都与所有右部顶点连有一条边。
现在删除其中的 条边。删除第 条边由两个整数 指定,表示删除左部顶点 与右部顶点 之间的边。
匹配是一个边的集合,其中任意两条边都不共用端点。匹配的大小等于集合中边的数量。
请你分别计算,在删边后的二分图中,大小恰好为 的匹配各有多少种。
两个匹配不同,当且仅当它们选取的边集合不同。
输入格式
第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示删除左部顶点 与右部顶点 之间的边。
输出格式
输出 行。
第 行()输出一个整数,表示恰好包含 条边的匹配数量。
答案不取模,必须输出完整的十进制整数。
样例输入
3 5
1 2
1 3
2 1
2 3
3 1
样例输出
1
4
4
1
样例解释
删除指定的五条边后,剩余四条边为 、、、,其中二元组的第一个元素是左部编号,第二个元素是右部编号。
- 大小为 :空匹配,共 种;
- 大小为 :选择任意一条剩余边,共 种;
- 大小为 :共 种;
- 大小为 :只有 ,共 种。
数据范围与约定
对于所有测试数据:
$$1\le n\le 500,\qquad 0\le m\le 20,\qquad 1\le u_i,v_i\le n.$$输入描述的是待删除的边;同一条边即使重复指定,删除效果也不变。本套测试数据中的删除边互不重复。
提示:答案可能远大于 位整数范围。