#P13797. wangyurzee的树

    ID: 12998 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 6 上传者: 标签>难度分类提高组合数学Prüfer 序列容斥原理枚举与搜索全子集枚举阶乘逆元预处理数论快速幂CF2100

wangyurzee的树

题目描述

有 nn 个两两不同的节点,编号为 1,2,…,n1,2,\dots,n。你需要在它们之间连接恰好 n−1n-1 条无向边,使得整张图成为一棵树。

但是给出了 mm 个限制条件。第 ii 个限制给出一对 (ui,di)(u_i,d_i),表示 节点 uiu_i 的度数不能等于 did_i。

节点的度数指与该节点相连的边的条数。

请问满足所有限制条件的生成树方案数有多少?答案对 10000000071000000007 取模。


输入格式

第一行两个整数 n,mn,m,表示节点个数与限制个数。

接下来 mm 行,每行两个整数 ui,diu_i,d_i,表示限制:节点 uiu_i 的度数不能为 did_i。


输出格式

输出一行一个整数,表示满足条件的方案数(对 10000000071000000007 取模)。


数据范围与保证

  • 1≤n≤1061 \le n \le 10^6
  • 0≤m≤170 \le m \le 17
  • 1≤di≤n−11 \le d_i \le n-1
  • 保证不会有两条完全相同的限制(即不存在相同的 (ui,di)(u_i,d_i))
  • 为了方便起见,保证 1≤ui≤m1 \le u_i \le m(因此被限制的点都在前 mm 个点里),并且显然也有 ui≤nu_i \le n

样例 1

3 1
1 2
2

解释:n=3n=3 时一共有 33 棵不同的树(边集分别为 (1,2),(1,3){(1,2),(1,3)}、(1,2),(2,3){(1,2),(2,3)}、(1,3),(2,3){(1,3),(2,3)})。其中第一棵里节点 11 的度数是 22,违反“节点 11 的度数不能为 22”,所以合法的只有 22 种。