紧急学习矩阵树定理。
矩阵树定理
矩阵树定理讲的是以下内容：
对于图 定义度数矩阵为 邻接矩阵为 定义拉普拉斯矩阵 。
求出将拉普拉斯矩阵去掉一行一列的矩阵 的行列式就是原图的生成树个数。
酷炫算术魔法！
但是为什么？
实际上就是一个容斥原理。
不妨考虑行列式的展开式：
来看看这个式子到底有什么组合意义。
拉普拉斯矩阵的样子就是，对角线上是点的度数，剩下的点中两点之间有边时为 ，否则为 。
不妨先考虑后面那个乘积是什么意思。
- 如果 ，那么对乘积的贡献就是 。
- 否则，如果 和 有连边，贡献就是 ，否则就是 。
因此，要满足后面的乘积非零，当且仅当每个 的点满足 在原图中有连边。
对于 的点，相当于在 的所有出边中任意选择一条，将其端点作为父亲。
考虑这样构造出来了一个什么样的图：
- 对于 的点，我们对置换进行轮换分解。这会形成若干个环。
- 对于 的点，我们从出边中任选一条。
容易发现，这构成了若干颗基环树和一颗以 为根的树，并且这张图仍然是原图的子图。乘积的绝对值就是这样构造出来的图的个数。
考虑一张图 什么时候会被构造出来。我们只保留 的点和 的连边，这张图称作 ，需要注意 唯一对应了一个置换，被删除的点在置换中连自环即可还原回去。
容易发现，只有当这张图是 的子图时， 才会做出贡献，否则无论如何都生成不了 。
考虑你保留下来这张图实际上是什么。就是若干不相交的环，并且是 中的环的一个子集。
不难发现 中每个环的子集都会被遍历到，构造这样的置换并不难，只要让子集中的环上的每个点指向下一个点，其他点连自环就行了。
因此一个有 个环的图一共会产生 次贡献。我们可以仿照子集反演的想法，让这 中一半系数为 ，一半为 ，这样 非零时这张图的贡献就会相互抵消，而 的时候系数为 （注意，无环说明这是原图的一颗生成树），正是我们要算的生成树个数。
仿照子集反演（是不是就是子集反演来着）构造容斥系数为 。这样有 个环的图的总贡献就等于
取到 当且仅当 。
因此，一个有 个环的图 ，其系数就是 。
也就是说，每有一个环，系数就会乘上 。
考虑一个长度为 的环，其对奇偶性的贡献是 ，由于每个点在拉普拉斯矩阵的位置的乘积还有一次 的贡献，因此总共的贡献就是 。所以一个环就恰好对系数造成 的影响。
因此，这个式子恰好凑出了这个容斥系数，最后得到的结果就是生成树个数。
对于这道题目，我们先构造出这张图的拉普拉斯矩阵，求行列式即可。
计算行列式
我们现在已经构造出了这张图的拉普拉斯矩阵，现在要计算其行列式。对于一般的图，可以使用高斯消元在 的复杂度内求出其行列式，然而这个复杂度对于本题来说是不可接受的。
我们不妨从最后加入的节点 入手。最后加入的节点只和 个点有连边，因而其拉普拉斯矩阵对应行上只有 个非零值（抛开对角线上的元素）。考虑利用这一行消掉其他行上这一列的值。
这一列有值当且仅当这个点和最后的节点有连边，因此这样的行也只有 个。我们枚举这 行，暴力在对应的 列上减去这些值。需要注意的是，由于题目保证了加入最后一个点前这 个点就已经两两连边了，因此这些位置上的值也非 。换句话说，这个操作并不会增加对应行上非零值的数量。不仅如此，假设当前在处理第 行，这样还会将 置为 ，反而使得非零值减少了 。对于任意一个点 ，假设编号比它大的点和这个点的连边用 条，那么在后面这些点消元完毕后，第 行的非零值至少会减少 。而最开始的非零值恰好等于点 的度数，也就是 ，分别是加入时连的 条边和与编号比它大的点的连边。因此后面点消元完毕之后 行的有效值最多为 ，此时消元复杂度不会超过 。
用哈希表记录每行的状态，从后向前进行消元即可。复杂度 。
代码在这里。