题目描述

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

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

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

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

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

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

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

游戏规则

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

• 棋盘是一个 $n$ 个点 $m$ 条边的无重边无自环的带标号无向图。
• 在棋局开始之前，有一个数字 $k$，表示有多少种不同颜色的棋子。
• 一开始的时候，所有节点上面都没有棋子。
• 两者轮流操作（Mas先手），操作方取出来一颗某种颜色的新棋子，将其放到图中一个没有放置棋子的点上，要求这个点满足：对于所有与之相邻的节点 $x$，$x$ 上要么没有放置棋子，要么 $x$ 上放的棋子的颜色与操作方选择的棋子的颜色不同。
• 棋子是不可以移动的。
• 无法操作者输掉游戏。

问题要求

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

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

请将多项式的系数对 $10^9+7$ 取模后输出这个多项式。

输入格式

本题共有 $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$）。

样例

输入：
1 0

2 0

3 0

3 2
1 2
1 3

3 3
1 2
1 3
2 3

输出：
0 1
0 0 1
0 0 0 1
0 1 1000000005 1
0 2 1000000004 1

数据范围与提示

评分方式

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

• 有一个初始为 $0$ 的计数器 $s$
• 对于第 $i$ 组测试数据，记 $n_i$ 为这组测试数据给出的棋盘的点数
• 选手提交的文件中应该有恰好 $5+\sum_{i=1}^5 n_i$ 个数字
• 对于第 $i$ 组测试数据，如果输出完全正确，给 $s$ 加上 $2$
• 该测试点的得分为 $s$

部分测试点的数据特性

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

注意事项

• 输入文件是在 Windows 10 系统下生成的，请选手注意换行符带来的问题
• 保证给出的图是无重边无自环的无向图
• 保证同一个测试点的五组测试数据有相关的数据特性，数据具有一定的梯度