3079 「2019 集训队互测 Day 4」博弈题

“棋盘的两边，一边是棋界新星Mas，一边是纵横沙场的老牌战将Z...

风起云涌，飞沙走石...

究竟会是哪一位赢得这场决战呢？”

作为解说的你，看着面前的两人一动不动，看了很久很久，很久很久，然后睡着了...

醒来之后，发现两人已经结束了对战，连棋盘上的棋子都已经收走了。

这真是你解说生涯中不可抹去的污点：还没开始解说，比赛就已经结束了！

为了挽回自己的颜面，你决定计算出有多少种不同的最终局面。

这种棋不同于一般的棋类，它是这样的：

棋盘是一个 $n$ 个点 $m$ 条边的无重边无自环的带标号无向图。

在棋局开始之前，有一个数字 $k$，表示有多少种不同颜色的棋子。

一开始的时候，所有节点上面都没有棋子。

两者轮流操作（Mas先手），操作方取出来一颗某种颜色的新棋子，将其放到图中一个没有放置棋子的点上，要求这个点满足，对于所有与之相邻的节点 $x$，$x$ 上要么没有放置棋子，要么 $x$ 上放的棋子的颜色与操作方选择的棋子的颜色不同。

注意，棋子是不可以移动的。

无法操作者输掉游戏。

身为解说的你，深知Mas和Z的实力深不可测，所以你知道他们两者的最终棋局中，没有一个节点是没有棋子的。

猜测是谁会获胜无法彰显你的水平，所以你会计算不同的最终局面的数量。

两种局面不同，当且仅当存在一个节点，放置在这个节点上的棋子在两种局面中的颜色是不同的。

同时，由于你睡了一觉，你连数字 $k$ 都忘记了，所以你会计算出一个多项式 $F(x)$，使得对于任意的 $k$，将 $k$ 代入多项式得到的结果 $F(k)$ 就是 $k$ 种颜色的情况下不同的最终局面的数量（可以证明，这样的多项式一定存在）。

由于多项式的系数可能很大，请将多项式的系数对 $10^9+7$ 取模后输出这个多项式。

注意： 这是一道提交答案题，一共有 $10$ 个测试点，每个测试点的分值都是 $10$ 分，每个测试点包含一个输入文件，一个输入文件中包含五组测试数据，每组测试数据的分值是 $2$ 分，保证同一个测试点的五组测试数据有相关的数据特性，数据具有一定的梯度。

本题共有 $10$ 个测试点，编号为 $1\sim 10$。

每个测试点有一个输入文件，编号为 * 的测试点的输入文件为 game*.in，一个输入文件中共有五组测试数据。

对于一组测试数据：

第一行两个整数 $n$ 和 $m$，表示棋盘的点数与边数。

接下来 $m$ 行，每行两个整数 $u,v(u\neq v)$，表示棋盘中的一条无向边，保证无自环无重边。

为了方便选手们观察数据，两组相邻的测试数据之间用空行隔开。

对于编号为 * 的测试点，选手需要提交的答案文件为 game*.out。

对于一个测试点，选手需要在答案文件中输出五行。

对于一组测试数据，请输出一行 $n+1$ 个数 $f_0,f_1,\dots,f_n$，这些数字之间用空格隔开，表示你求出的多项式是 $F(x)=\sum\limits_{i=0}^n f_i\cdot x^i$。

如果对于某组测试数据，选手没有求出答案，请务必输出恰好 $n+1$ 个 $[0,10^9+7)$ 内的整数（建议输出 $0$），否则选手在这个测试点的得分会被视为 $0$ 分。

评分方式

每个测试点单独评分，采用特殊比较器评分。

对于一个测试点，按照测试数据的顺序进行评分。

有一个初始为 $0$ 的计数器 $s$。

对于第 $i$ 组测试数据，记 $n_i$ 为这组测试数据给出的棋盘的点数。选手提交的文件中应该有恰好 $5+\sum_{i=1}^5 n_i$ 个数字，如果有超过 $5+\sum_{i=1}^5 n_i$ 个数字或少于 $5+\sum_{i=1}^5 n_i$个数字，那么输出格式不合法，该测试点得分为 $0$。

按照 $i=1\cdots 5$ 的顺序进行评分，对于第 $i$ 组测试数据，比较器会从选手文件中读入 $n_i+1$ 个数字并与答案比对，如果完全一致，那么给 $s$ 加上 $2$。

如果输出格式合法，那么该测试点的得分为 $s$，否则该测试点得分为 $0$。

如果选手提交的文件中出现了除数字、空格以及换行符之外的字符，将可能出现无法估计的结果，产生的后果请选手自行承担。

提示

注意，本题的输入文件是在 Windows 10 系统下生成的，请选手注意换行符带来的问题。

保证给出的图是无重边无自环的无向图。

请选手认真阅读评分方式以及输出格式，避免造成不必要的失误。

保证同一个测试点的五组测试数据有相关的数据特性，这五组数据具有一定的梯度。

部分测试点的数据特性

• 对于测试点 $2$，给出的图是一棵树。
• 对于测试点 $3$，给出的图是一棵仙人掌。
• 对于测试点 $4$，给出的图中每个双连通分量的点数不超过 $15$（“双连通分量”被定义为图中的一个没有割点的极大子图）。
• 对于测试点 $8$，给出的图的补图是一棵树。