#P6903. 枸杞
枸杞
题目描述
给定 张无向图。每次询问选取编号在 内的图,一个位置由在所选的每张图中各取一个顶点组成。
一步游走时,每个坐标可以留在原顶点,或沿所在图的一条边移动。至少一个坐标必须移动。求游走步数为 到 、最后回到起点的方案总数,对 取模。选择不同起点得到的方案分别计数。
输入格式
第一行一个正整数 ,表示无向图数量。
接下来依次输入 张图。第 张图先输入一行 ,分别表示点数和边数。随后 行每行两个点编号,表示一条无向边。点从 到 编号。
接下来一行一个正整数 ,表示询问数。
接下来 行,每行三个正整数 ,表示对应询问。
输出格式
输出 行,每行一个整数,表示该询问的答案。
样例
2
3 3
1 2
2 3
1 3
3 2
1 2
2 3
3
1 1 4
2 2 4
1 2 2
30
12
54
第一问中,三角形的每个顶点作为起点时,长度 、、 的闭合游走分别有 、、 种,合计 。
数据范围
,,,。
| 测试点 | 上限 | 上限 | 是否保证 |
|---|---|---|---|
| 1–2 | 30 | 是 | |
| 3–7 | 否 | ||
| 8–12 | 15 | ||
| 13–20 | 30 |
本站原评测配置为 4 秒、256 MB。
By Anoxx