深搜（dfs）

题目描述

苗苗正在阅读一段图搜索程序。程序使用深度优先搜索，代码如下：

vector<vector<int>> g(n + 1);
vector<int> all_vertices;
vector<int> output;
vector<int> visited(n + 1, 0);

void dfs(int u) {
    visited[u] = 1;
    output.push_back(u);
    for (int v : g[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

void run_dfs() {
    for (int v : all_vertices) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

这段程序中有两个顺序没有被固定：每个 g[u] 中相邻点的顺序可以任意决定；all_vertices 中所有点的顺序也可以任意决定。

现在给定一张 $n$ 个点、$m$ 条边的无向图，以及一个排列 $p_1,p_2,\ldots,p_n$。苗苗可以向图中加入若干条无向边。她希望在加入这些边之后，存在一种枚举顺序，使得程序输出点的顺序恰好为

请你求出至少需要加入多少条边。

可以证明，一定存在合法方案。

输入格式

从文件 dfs.in 中读入数据。

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示图中有一条连接 $u_i$ 和 $v_i$ 的无向边。

最后一行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示希望得到的输出顺序。

输出格式

输出到文件 dfs.out 中。

输出一行一个整数，表示至少需要加入的边数。

输入输出样例 #1

输入 #1

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

输出 #1

2

说明/提示

至少需要加入 $2$ 条边。例如加入边 $(1,2)$ 和 $(4,5)$ 后，可以通过合适地选择枚举顺序，使 DFS 的输出顺序为 1 2 3 4 5 6。

对于全部数据，满足：

• $1\le n\le 3\times 10^5$；
• $0\le m\le 5\times 10^5$；
• $1\le u_i,v_i\le n$，$u_i\ne v_i$；
• 同一条无向边不会重复出现；
• $p_1,p_2,\ldots,p_n$ 是 $1$ 到 $n$ 的一个排列。

特殊性质 A：保证 $p_i=i$。

样例文件