/ CWOI / 题库 /

2017.07.19 P2 线索

2017.07.19 P2 线索

题目描述

夏洛克·福尔摩斯在调查一宗犯罪事件时,发现了一定数量的线索,而且他还发现有些线索存在直接关系。线索之间的直接关系是相互的,即 A -> B,并且 B -> A。两条线索直接关系不超过一条。
当然,夏洛克·福尔摩斯能找出所有线索的直接关系,但是这将花费太多的时间,到时罪犯已经隐藏起来了。为了更快的抓住犯罪分子,夏洛克·福尔摩斯需要知道每条线索之间的关系(可以是直接关系也可以是间接关系)。
夏洛克·福尔摩斯发现自己最少需要找到额外的 T 组直接关系就可以抓住罪犯。请你帮他数一数有多少种方式可以找到正确的线索之间的直接关系。由于方法数比较多,结果模 k。

输入格式

第一行三个整数 n, m, k,表示 n 条线索,m 对直接关系,模 k。
接下来 m 行,每行两个整数 a, b,表示 a 和 b 有直接关系。
这是线索之间的直接联系。保证任何两条线索都由一个直接连接联系在一起。请注意,线索之间的直接联系是相互的。

输出格式

输出方案数。

样例1

输入

2 0 1000000000

输出

1

样例2

输入

3 0 100

输出

3

样例3

输入

4 1 10000000
1 4

输出

8

数据范围

对于 30%的数据,1 \(\leq\) n \(\leq\) 20, 0 \(\leq\) m \(\leq\) 20, 1 \(\leq\) k \(\leq\) \(10^9\), 1 \(\leq\) a, b \(\leq\) n, a ≠ b;
对于 100%的数据,1 \(\leq\) n \(\leq\) \(10^5\), 0 \(\leq\) m \(\leq\) \(10^5\), 1 \(\leq\) k \(\leq\) \(10^9\), 1 \(\leq\) a, b \(\leq\) n, a ≠ b。

限制

1s

样例解释

样例 1:只有两条线索,并且线索之间没有之间关系,所以只有一种方案。
样例 2:有三条线索,有三种方案,1 -> 2, 2 -> 3、1 -> 3, 2->3、1 -> 2, 1 -> 3。
样例 3:方案太多,自己数。

来源

Codeforces156D
CWOI新高二专题测试十六

信息

难度
5
分类
数学数据结构 | 并查集 点击显示
标签
(无)
递交数
2
已通过
2
通过率
100%
上传者