Description

Z 国坐落于遥远而又神奇的东方半岛上, 在小 Z 的统治时代公路成为这里主要的交通手段. Z 国共有 \(n\) 座城市, 一些城市之间由双向的公路所连接. 非常神奇的是 Z 国的每个城市所处的经度都不相同, 并且最多只和一个位于它东边的城市直接通过公路相连. Z 国的首都是 Z 国政治经济文化旅游的中心, 每天都有成千上万的人从 Z 国的其他城市涌向首都.

为了使 Z 国的交通更加便利顺畅, 小 Z 决定在 Z 国的公路系统中确定若干条规划路线, 将其中的公路全部改建为铁路.

我们定义每条规划路线为一个长度大于 \(1\) 的城市序列, 每个城市在该序列中最多出现一次, 序列中相邻的城市之间由公路直接相连 (待改建为铁路). 并且, 每个城市最多只能出现在一条规划路线中, 也就是说, 任意两条规划路线不能有公共部分.

当然在一般情况下是不可能将所有的公路修建为铁路的, 因此从有些城市出发去往首都依然需要通过乘坐长途汽车, 而长途汽车只往返于公路连接的相邻的城市之间, 因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首都.

我们定义一个城市的 “不便利值” 为从它出发到首都需要乘坐的长途汽车的次数, 而 Z 国的交通系统的 “不便利值” 为所有城市的不便利值的最大值, 很明显首都的 “不便利值” 为 \(0\). 小 Z 想知道如何确定规划路线修建铁路使得 Z 国的交通系统的 “不便利值” 最小, 以及有多少种不同的规划路线的选择方案使得 “不便利值” 达到最小. 当然方案总数可能非常大, 小 Z 只关心这个天文数字 \(\bmod Q\) 后的值.

注意: 规划路线 \(1-2-3\) 和规划路线 \(3-2-1\) 是等价的, 即将一条规划路线翻转依然认为是等价的. 两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案.

Input

第一行包含三个正整数 \(n, m, Q\), 其中 \(n\) 表示城市个数,\(m\) 表示公路总数,\(n\) 个城市从 \(1-N\) 编号, 其中编号为 \(1\) 的是首都.\(Q\) 表示上文提到的设计路线的方法总数的模数.

接下来 \(m\) 行, 每行两个不同的正数 \(a_i, b_i (1 \leq a_i, b_i \leq n)\) 表示有一条公路连接城市 \(a_i\) 和城市 \(b_i\). 输入数据保证一条公路只出现一次.

Output

第一行为一个整数, 表示最小的 “不便利值”.

第二行为一个整数, 表示使 “不便利值” 达到最小时不同的设计路线的方法总数 \(\bmod Q\) 的值. 如果某个城市无法到达首都, 则输出两行 \(-1\).

Sample Input

5 4 100
1 2
4 5
1 3
4 1

Sample Output

1
10

Data Range

对于 100% 的数据, 满足 \(1 \leq n, m \leq 10^5, 1 \leq Q \leq 120000000\).

Explanation

首先这棵树需要联通......

然后膜拜神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2013/12/06/3462328.html

考虑 \(dp[i][j][k]\) 表示以 \(i\) 为根的子树, 其所有孩子到其的不便利度最大为 \(j\), 向其孩子修建 \(k\) 条铁路的方案数, 设 \(i\) 的孩子集合为 \(S\), 那么有:\[ \begin{aligned} dp[i][j][0] &= \prod_{x \in S_i} dp[x][j-1][0] + dp[x][j-1][1] + dp[x][j-1][2]\\ dp[i][j][1] &= \sum_{x \in S_i} (dp[x][j][0] + dp[x][j][1])\\ &\cdot \prod_{y \in S_i \land y \neq x} (dp[y][j-1][0] + dp[y][j-1][1] + dp[y][j-1][2])\\ dp[i][j][2] &= \sum_{x \in S_i} \sum_{y \in S_i \land y \neq x} (dp[x][j][0] + dp[x][j][1]) \cdot (dp[y][j][0] + dp[y][j][1])\\ &\cdot \prod_{z \in S_i \land z \neq x \land z \neq y} (dp[z][j-1][0] + dp[z][j-1][1] + dp[z][j-1][2]) \end{aligned} \]

然后将这个繁琐的式子化简以后得到:\[ \begin{aligned} f_1 &= dp[x][j][0] + dp[x][j][1]\\ f_2 &= dp[x][j-1][0] + dp[x][j-1][1] + dp[x][j-1][2]\\ dp[i][j][2] &= dp[i][j][2] \cdot f_2 + dp[i][j][1] \cdot f_1\\ dp[i][j][1] &= dp[i][j][1] \cdot f_2 + dp[i][j][0] \cdot f_1\\ dp[i][j][0] &= dp[i][j][0] \cdot f_2 \end{aligned} \] 然后带进去即可.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
typedef pair<lli, lli> prll;
const int maxn = 100100, maxm = 400100;
/* const */ lli modr = 1000000007;

lli pmod(lli a) { lli b = a % modr;
    if (!a) return 0;
    if (!b) return modr;
    return b;
} // A peculiar modulo operation, avoids 0 detection

class TreeDP
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int n, root, ecnt;
    edge *edges[maxn], epool[maxm];
    bool vis[maxn];
    int par[maxn];
    lli dp[maxn][20][3];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    void dfs_forest(int p)
    {
        vis[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!vis[ep->v]) {
                dfs_forest(ep->v);
                par[ep->v] = p;
            }
        return ;
    }
    void dfs(int p, int fail)
    {
        dp[p][fail][0] = 1;
        dp[p][fail][1] = 0;
        dp[p][fail][2] = 0;
        for (edge *ep = edges[p]; ep; ep = ep->next) if (par[ep->v] == p) {
            dfs(ep->v, fail);
            lli f1 = dp[ep->v][fail][0] + dp[ep->v][fail][1],
                f2 = (fail > 0) ? (dp[ep->v][fail-1][0] + dp[ep->v][fail-1][1] + dp[ep->v][fail-1][2]) : (0);
            dp[p][fail][2] = pmod(dp[p][fail][2] * f2 + dp[p][fail][1] * f1);
            dp[p][fail][1] = pmod(dp[p][fail][1] * f2 + dp[p][fail][0] * f1);
            dp[p][fail][0] = pmod(dp[p][fail][0] * f2);
        }
        return ;
    }
    prll eval(void)
    {
        // In case of error or impossibility, we raise this.
        prll fallback = make_pair(-1, -1);
        // Checking connectivity to the capital
        dfs_forest(root);
        for (int i = 1; i <= n; i++)
            if (!vis[i])
                return fallback;
        // Tree is connected, getting dp array
        for (int i = 0; i < 20; i++) {
            dfs(root, i);
            lli sm = dp[root][i][0] + dp[root][i][1] + dp[root][i][2];
            if (sm <= 0)
                continue;
            return make_pair(i, sm % modr);
        }
        // That meant a total failure.
        return fallback;
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d%lld", &n, &m, &modr);
    graph.n = n;
    graph.root = 1;
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        graph.add_edge(a, b);
    }
    // Getting result
    prll pr = graph.eval();
    printf("%lld\n%lld\n", pr.first, pr.second);
    return 0;
}