CF156D.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 B are 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.

夏洛克·福尔摩斯在调查另一起案件时，发现了若干条线索。此外，他已发现其中某些线索之间存在直接关联。线索之间的直接关联是相互的：即线索 A 与线索 B 之间的直接关联，和线索 B 与线索 A 之间的直接关联是同一回事。任意两条线索之间至多只存在一条直接关联。

当然，夏洛克有能力为所有线索两两之间都建立起直接关联。但这将耗费过多时间，而罪犯则可能利用这段额外时间隐匿行踪。为侦破此案，夏洛克需要确保每条线索均能与其他所有线索关联（未必是直接关联，可通过其他线索间接关联）。若线索 A 与线索 B 之间存在直接关联，或存在某条线索 C，使得 A 与 C 有直接关联且 C 与 B 关联（递归定义），则称线索 A 与 B 是关联的。

夏洛克·福尔摩斯计算出，为侦破此案所需新增的最少直接关联数恰好为 T。

请计算：有多少种不同的方式，恰好新增 T 条直接关联，使得最终所有线索均彼此关联？若两种新增直接关联的方式中，存在某对线索，在一种方式中有直接关联而在另一种方式中没有，则认为这两种方式不同。

由于不同方式的总数可能非常大，请输出结果对 k 取模后的值。

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.

第一行包含三个以空格分隔的整数 $n$、$m$、$k$（$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq k \leq 10^9$）——分别表示线索的数量、福尔摩斯已发现的直接线索连接数，以及模运算所用的除数。

接下来的 $m$ 行中，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$，$a \neq b$），表示线索 $a$ 与线索 $b$ 之间存在一条直接连接。保证任意两条线索之间至多只有一条直接连接。注意，线索之间的直接连接是双向的。

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

输出单个数字——该问题答案对 $k$ 取模的结果。

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.

第一个样例仅有两条线索，而夏洛克尚未在它们之间发现任何直接联系。破案的唯一方法是找到这种联系。

第二个样例包含三条线索，而夏洛克尚未在它们之间发现任何直接联系。他必须在三条线索之间找出三条可能的直接联系中的两条，才能破案——共有 3 种方式。

第三个样例包含四条线索，侦探已发现第一条线索与第四条线索之间存在一条直接联系。此时，还有 8 种方式可找出剩余两条线索以破案。