这题大家貌似都见过原题qwq，我比较菜所以没见过。我们机房一共有四个人打UNR，然后一共有三个做法，有基友问都是什么我就简单说说qwq

我的做法和题解是一样的，详情还是看乐滋滋的题解吧

我左边的同学做法是这样的

他考虑对于一个图进行二分图染色，然后考虑进行染色的第一个点其实是有 $k$ 种方案的，然后对于同在一个联通块内的一个点每个点的贡献都是 $k-1$

一个简单的证明是这样的，首先我们造一棵树出来，显然这个东西是完全合法的，然后考虑加上一些非树边，由于是二分图，所以加上非树边之后显然环是偶环，那么显然第一个点和最后一个点总是不能同色的，所以他的方案数和不连边的方案数是同样的，所以就是 $k-1$

如果是非二分图，对于一种合法染色，我们循环一下就行啦，显然必然包括 $3!$ （因为两种颜色没法给他染色辣）

我对面的同学好像更diao一些大概是导出了一个类似环的多项式然后推出了一个非常简单的式子，具体意思看看代码大概还是可以接受的 CQzhangyu's Ac solution

我们现在来看看他们为啥相等……

我们考虑欧拉定理的拓展定理

$$ a^b \equiv \begin{cases} a^{b \bmod \varphi(p) } & { \gcd(a,p) = 1} \\ a^{b \bmod \varphi(p) + \varphi(p)} & \gcd(a,p) \neq 1, b \geq \varphi(p) \\ \end{cases} \pmod p $$

$\varphi(6) = \varphi(2)\times \varphi(3) = 1 \times 2 = 2$

然后……

233333333333333333333333333333333333333333333333333