Codeforces 156D. Clues

As Sherlock Holmes was investigating another crime, he found a certain number of clues. Also, he has already found direct links between some of those clues. The direct links between the clues are mutual. That is, the direct link between clues A and B and the direct link between clues B and A is the same thing. No more than one direct link can exist between two clues.

Of course Sherlock is able to find direct links between all clues. But it will take too much time and the criminals can use this extra time to hide. To solve the crime, Sherlock needs each clue to be linked to all other clues (maybe not directly, via some other clues). Clues A and Bare considered linked either if there is a direct link between them or if there is a direct link between A and some other clue C which is linked to B.

Sherlock Holmes counted the minimum number of additional direct links that he needs to find to solve the crime. As it turns out, it equals T.

Please count the number of different ways to find exactly T direct links between the clues so that the crime is solved in the end. Two ways to find direct links are considered different if there exist two clues which have a direct link in one way and do not have a direct link in the other way.

As the number of different ways can turn out rather big, print it modulo k.

Input

The first line contains three space-separated integers n, m, k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 109) — the number of clues, the number of direct clue links that Holmes has already found and the divisor for the modulo operation.

Each of next m lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b), that represent a direct link between clues. It is guaranteed that any two clues are linked by no more than one direct link. Note that the direct links between the clues are mutual.

Output

Print the single number — the answer to the problem modulo k.

Examples

Note

The first sample only has two clues and Sherlock hasn’t found any direct link between them yet. The only way to solve the crime is to find the link.

The second sample has three clues and Sherlock hasn’t found any direct links between them. He has to find two of three possible direct links between clues to solve the crime — there are 3 ways to do it.

The third sample has four clues and the detective has already found one direct link between the first and the fourth clue. There are 8 ways to find two remaining clues to solve the crime.

题意简述

给出一个森林,求有多少种加边方式可以将森林变为树,答案对 $K$ 取模。

分析

如果给出的边数为 $0$,方案数就是 $n^{n-2}$,这个可以用 prufer 编码证明。

那么考虑一下 prufer 编码,可以发现这个问题同样可以用 prufer 编码解决,将每个联通块分开考虑,设总联通块数为 $t$,考虑块之间连成树的方案是 $t^{t-2}$,但是一个“叶子”块连向它“父亲”块时连向“父亲”块中不同节点的时候,是属于不同的方案,简单地说就是 prufer 的每一位需要从 $1$~$n$ 中枚举,所以方案数是 $n^{t-2}$。

然后发现连向的点不同属于不同的方案,从块内不同点连出去一样是不同的方案,所以对于每个被删除时联通块,需要乘以联通块内的点数。

最后剩下两个块时,两个块之间连边的方案为两块大小的乘积。

所以实际上最后的答案是

$$n^{t-2}\times \prod_i siz(i)$$

因为模数 $K$ 没有什么性质,所以当 $t-2=-1$ 时要特判,不能用逆元。

注意要返回 $1$ 的地方要取模,因为模数可能是 $1$。

 

1 comment

发表评论