最大半连通子图

题目描述:

输入格式:

第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。

输出格式:

包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

样例输入:

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

样例输出:

3
3

提示:

对于20%的数据，   N ≤18；

对于60%的数据，   N ≤10000；

对于100%的数据， N ≤100000, M ≤1000000；

对于100%的数据， X ≤10⁸。

时间限制: 3000ms
空间限制: 256MB

---

来源: 浙江省选2007day2t1