CF156D 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$ 种方式可以找到剩下两条联系，从而使所有线索关联起来。 由 ChatGPT 5 翻译