Description：

给出一个图，其中一些点已经有边，问把所有点联通需要加的最小边数。

$1\leqslant n\leqslant 10^5$

Solution：

设联通块个数为 $cnt$ ，第 $i$ 个联通块大小为 $siz[i]$ ，那么： $$ ans=\prod_{i=1}^{cnt}siz[i]\times n^{cnt-2} $$ 简单证一下，考虑把所有联通块拿出来做 $prufer$ 序列，总共有 $cnt$ 个位置，每个位置所有点都可以填，这部分答案为 $n^{cnt-2}$ ，但我们还不知道每个点删掉时是哪个点指了一条边到他的父亲，也不知道最后删掉的那两个点是用哪个点相连的，所以还要乘一个 $\begin{align}\prod_{i=1}^{cnt}siz[i]\end{align}$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,mod;

#define MAXN 100010

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int siz[MAXN];

bool vis[MAXN];

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % mod;

		a = 1ll * a * a % mod;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%d%d%d",&n,&m,&mod);

	for(int i = 1;i <= n;++i)f[i] = i;

	for(int i = 1;i <= n;++i)siz[i] = 1;

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		int p = find(a),q = find(b);

		if(p == q)continue;

		f[p] = q;siz[q] += siz[p];

	}

	int ans = 1;

	int cnt = 0;

	for(int i = 1;i <= n;++i)

	{

		if(!vis[find(i)])

		{

			++cnt;

			ans = 1ll * ans * siz[find(i)] % mod;

			vis[find(i)] = true;

		}

	}

	ans = 1ll * ans * power(n,cnt - 2) % mod;

	if(cnt != 1)cout << ans << endl;

	else printf("%d\n",1 % mod);

	return 0;

}