#P15638. [Bulgarian2025冬季赛]Squirrel松鼠

[Bulgarian2025冬季赛]Squirrel松鼠

题目描述

一只松鼠站在一棵长满橡子的树根处,准备收集橡子。

这棵树有 NN 个分叉点和 N−1N-1 条树枝,每个分叉点编号为 11 到 NN,其中 11 号点是树根。每个分叉点都有一个橡子。

松鼠一开始在根节点,并且已经拿走了根节点的橡子。接下来,它需要选择一串树枝进行移动,使得每个分叉点被访问的次数恰好等于与它相连的树枝数量。每当松鼠第一次访问某个分叉点时,就会拿走这个分叉点上的橡子。

松鼠有 MM 个要求。第 ii 个要求为 (ai,bi)(a_i,b_i),表示 aia_i 号分叉点的橡子必须在 bib_i 号分叉点的橡子之前被拿走。

请计算满足所有要求的不同移动方式数量,答案对 109+710^9+7 取模。

输入格式

第一行输入两个整数 N,MN,M。

接下来 N−1N-1 行,每行输入两个不同整数 ui,viu_i,v_i,表示一条树枝。

接下来 MM 行,每行输入两个不同整数 ai,bia_i,b_i,表示一个先后顺序要求。

输出格式

输出一个整数,表示满足全部要求的移动方式数量对 109+710^9+7 取模的结果。

数据范围

  • 2≤N≤1000002\le N\le 100000
  • 1≤M≤3000001\le M\le 300000
  • 1≤ai,bi,ui,vi≤N1\le a_i,b_i,u_i,v_i\le N
  • D≤12D\le 12,其中 DD 为一个分叉点连接的树枝最大数量。

子任务

子任务 分值 依赖 NN MM DD
1 26 无 ≤10\le 10 ≤50\le 50 ≤12\le 12
2 11 ≤20\le 20 ≤100\le 100 ≤3\le 3
3 9 2 ≤1000\le 1000
4 2-3 ≤7\le 7
5 1-4 ≤12\le 12
6 12 2-3 ≤100000\le 100000 ≤300000\le 300000 ≤3\le 3
7 2-4,6 ≤7\le 7
8 1-7 ≤12\le 12

样例 1

输入

3 2
1 2
1 3
1 2
3 1

输出

0

样例 2

输入

6 2
1 2
1 3
1 4
3 5
3 6
5 6
5 4

输出

3