20008 - Clues

当福尔摩斯在调查另一起犯罪时，他发现了若干线索。同时，他已经找到了其中一些线索之间的直接联系。线索之间的直接联系是互相的。也就是说，线索 A 和 B 之间的直接联系与 B 和 A 之间的直接联系是同一条联系。两个线索之间至多只会有一条直接联系。

当然，福尔摩斯能够找到所有线索之间的直接联系。但这会花费太多时间，罪犯可能会利用这段额外的时间藏匿起来。为了破案，福尔摩斯需要让每一个线索都能够与所有其他线索相关联（可能不是直接联系，也可能通过其他线索间接联系）。如果存在线索 C，使得 A 与 C 有直接联系，且 C 能够与 B 相关联，那么 A 与 B 也被认为是相关联的。

福尔摩斯计算了他最少还需要去寻找的直接联系的数量，用 T 表示。

请计算有多少种不同的方法恰好寻找 T 条直接联系，使最终所有线索都能关联起来。若存在两种方案，使得某一对线索在一种方案中有直接联系，在另一种方案中没有直接联系，则认为这两种方案是不同的。

由于答案可能很大，请输出其对 k 取模的结果。

第一行包含三个用空格分隔的整数 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 之间有直接联系。保证任意两条线索之间至多只有一条直接联系。注意，线索之间直接联系是互相的。

输出一个整数，表示答案对 k 取模后的结果。

第一个样例只有两个线索，福尔摩斯还没有发现它们之间的任何直接联系。唯一的办法是去寻找一条联系。

第二个样例有三个线索，福尔摩斯还没有发现它们之间的任何直接联系。他需要在人为三条可能的直接联系中找到两条，才可以破案——有 3 种方式。

第三个样例有四个线索，侦探已经找到了第一个和第四个线索之间的一条直接联系。还有 8 种方式可以找到剩下两条联系，从而使所有线索关联起来。