1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, q, fa[100005], hea[100005], cnt, uu, vv, dp[100005][13][3];
struct Edge{
int too, nxt;
}edge[200005];
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
int mf(int x){
return fa[x]==x?x:fa[x]=mf(fa[x]);
}
int g(ll x){
if(!x) return x;
x %= q;
if(!x) x = q;
return x;
}
void dfs(int x, int m, int f){
dp[x][m][0] = 1;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f){
dfs(t, m, x);
int t1=m?g((ll)dp[t][m-1][0]+dp[t][m-1][1]+dp[t][m-1][2]):0;
int t2=g((ll)dp[t][m][0]+dp[t][m][1]);
dp[x][m][2] = g((ll)dp[x][m][2]*t1+(ll)dp[x][m][1]*t2);
dp[x][m][1] = g((ll)dp[x][m][1]*t1+(ll)dp[x][m][0]*t2);
dp[x][m][0] = g((ll)dp[x][m][0]*t1);
}
}
}
int main(){
cin>>n>>m>>q;
for(int i=1; i<=n; i++) fa[i] = i;
for(int i=1; i<=m; i++){
scanf("%d %d", &uu, &vv);
add_edge(uu, vv);
add_edge(vv, uu);
uu = mf(uu); vv = mf(vv);
if(uu!=vv) fa[vv] = uu;
}
for(int i=1; i<=n; i++)
if(mf(i)!=mf(1)){
printf("-1\n-1\n");
return 0;
}
for(int i=0; ; i++){
dfs(1, i, 0);
if(dp[1][i][0] || dp[1][i][1] || dp[1][i][2]){
printf("%d\n%d\n", i, (dp[1][i][0]+dp[1][i][1]+dp[1][i][2])%q);
return 0;
}
}
return 0;
}
|