题目描述
题目译自 POI XXVII - I etap 「Przedszkole」
有一个 n 个点 m 条边的无向图,每个点从 1 到 n 编号。你有 k 种颜色,要给每个点染色,使得有边相连的两个点颜色不一样。求出染色方案数,对 109+7 取模。
输入格式
第一行包含 3 个整数 n,m 和 z,表示图中点个数,边条数和询问个数。
接下来 m 行,每行包含两个整数 ai 和 bi,表示点 ai 和 bi 之间有一条边相连。保证不会有重边和自环。
接下来 z 行,每行包含一个整数 ki,表示你有 ki 种颜色。
输出格式
对于每组数据,输出你有 ki 种颜色时的染色方案数,对 109+7 取模。
样例
4 4 1
1 2
2 3
1 3
3 4
3
12
附加样例
附加样例参见 prz/prz*.in
和 prz/prz*.out
:
-
附加样例 1:n=5,m=10,两个询问 k∈{5,6};
-
附加样例 2:n=11,m=40,一个询问 k=15;
-
附加样例 3:n=100,m=15,5 个询问,k 从 [10,100] 里面随机;
-
附加样例 4:n=100,m=100,所有点构成了一个环;三个询问 k∈{5,10,15}。
数据范围与提示
对于 100% 的数据,1≤n≤105,0≤m≤min(105,n(n−1)/2),1≤z≤1000,1≤ai,bi≤n,1≤ki≤109。
Subtask # |
额外限制 |
分值 |
1 |
n ≤8,k≤8,z≤50 |
8 |
2 |
n ≤15 |
26 |
3 |
m≤24 |
33 |
4 |
每个点恰好有两条边和它相连 |
33 |