思路与算法

先把互异点权按大小归一为0..N-1，保留堆的大小比较。一个搜索状态是每个顶点的权值排列，允许边(u,v)对应交换两个位置；目标是每条父子边都满足父权大于子权。每次操作代价1，要求最短步数。

一般交换图中，采用IDA*：从可采纳估价h(初态)开始逐次提高交换数阈值，深搜时若已用g步且g+h超过阈值就剪枝。同一轮内用完整64位置换编码与开放寻址表保存某状态已到达的最小g，较差重复到达不再展开，并跳过直接撤销上一步的交换。

估价不能仅看不满足堆性质的边数。把点权分成最大的ceil(N/2)个和最小的floor(N/2)个，两组不相交（N≤13时最多7+6）。对每组单独建立模式数据库：只记录该组有标签token的位置，其他token均视作不可区分。一次允许交换若移动本组一个token，边权为1；若移动本组两个token，边权为2；没有移动本组token则状态不变。最大组在任何堆中必须占据祖先封闭位置集合，并按父大子小排列；从当前森林根逐次放最大token可枚举其全部抽象目标。最小组相应占据后代封闭集合，从当前叶子逐次放最小token枚举目标。只有同一交换连通分量内的token才能互换，枚举时先检查分量限制。

从全部抽象目标反向做权为1或2的最短路，桶队列即可得到到目标集合的最小token移动成本。两组数据库成本之和除以2并向上取整，是实际交换步数下界，因为一次交换总共移动两个token。此外取每个token到必要合法位置集合的最短距离最大值，以及权值低于子树大小减1的位置数、权值高于N-1-深度的位置数的最大值来加强估价。深搜优先尝试估价小的下一步。

N=16时原数据给M=120，即可交换任意两点，另用精确的目标堆分配搜索。依权值从大到小，把当前最大剩余token放到尚未分配森林的某个根，直接交换到位后固定该根，并把它的孩子加入森林根集合。枚举所有根选择，就枚举所有合法目标堆，但不存下全部目标堆。以必要改动位置的下界剪枝，按交换数阈值迭代，首先找到的就是最少次数。

正确性说明

归一化是严格单调映射，保持所有堆比较；允许边直接定义真实操作，所以完整状态图的单位边最短路就是所求。

模式数据库下界：任意真实交换序列投影到一组token后，恰好产生该组抽象图上的路径，路径费用是这些token被移动的总次数。真实终态为堆时，其最大组必为祖先封闭、最小组必为后代封闭，并满足组内父子顺序及分量限制，必在抽象目标集合中。抽象最短费用不大于该投影路径费用。两组不相交且覆盖全部token时，每次真实交换使两组费用之和恰加2；若另有单个token采用到合法位置的距离估价，也不超过其实际移动次数。因此费用和的一半向上取整不超过剩余交换数。

必要合法位置下界：rank=v的token放在u时，必须至少有size(u)-1个更小值放到其后代，且至少depth(u)个更大值放到祖先，所以size(u)-1≤v≤N-1-depth(u)。token每交换一次至多沿允许图走一条边，其到该位置集合的图距离也是下界。对低于各自必要下界的两个位置，若一次交换能同时纠正二者，就会出现a<L_u≤b<L_v≤a的矛盾；故一次交换至多减少一个这样的坏位置，坏位置数是交换数下界。高于上界的情况对称。最大值合并多个下界仍可采纳。

IDA*只剪去不可能在当前阈值内完成的状态。同轮某个完整排列以更小g到达后，未来可行操作与目标只由排列决定，较大g的重复状态不可能提供更短解。最短序列不含相邻的同一交换及其撤销。逐阈值完整搜索因此保持最优性。模式目标即使只检查了分量必要条件而放宽了其他组约束，只会使估价偏小，不会错误剪掉真解。

全交换分支：任意合法目标堆中，最大剩余值必位于当前森林根之一，因此枚举根不遗漏目标。固定某个目标排列时，将最大剩余token与其目标位置直接交换，若本来不在位，这两个位置在当前到目标的置换映射中属于同一个环；交换把该环分裂，所需任意交换最少次数N-环数恰减1。在位则费用0。归纳可知对每个目标，这种逐最大值固定法使用其真正的最少任意交换次数。搜索遍历全部目标，并且只用必要改动位置数的下界剪枝，故所得也是所有堆目标中的最小值。

复杂度

一般图的完整置换空间最多N!。设一组有k个token，抽象有效状态数为P(N,k)=N!/(N-k)!，每个状态至多检查M条交换边；权1/2桶最短路的构造量级为O(M·P(N,k))，再加表初始化成本。N=13的7-token组使用精确完美编码，只需P(13,7)=8648640个槽；先编码3个位置，再将其余4个位置压缩到剩余10点，通过小表合并成一一对应的下标，避免16^7的大数组。较小组使用4位位置编码。数据库在搜索前只建一次。

IDA*最坏时间仍是指数级，不能把测试通过说成多项式保证。若一次阈值搜索扩展S个状态，估价查表为常数级，生成并排序至多M步的代价O(SM log M)。阈值不会需要超过连通分量内置换的有限可达直径；分量生成树逐叶固定可给总交换数N(N-1)/2的上界。置换表容量固定且冲突时只放弃缓存，不影响正确性。存储包括模式距离、桶队列和约25MiB的精确置换表；全交换分支无需模式数据库，目标分配搜索最坏仍为指数级，工作栈与现场为O(N)。

易错点

普通堆排序一次向下调整不等于本题允许的一次交换，操作必须严格使用给出的M条边。父亲编号不一定小于儿子，根用0表示；建树后再算深度和子树大小。交换图不一定连通，只能在分量内重排，不能假设全排列可达。模式库要按移动的token数收费1或2，若直接把两组各自交换次数相加会高估并错误剪枝。转移费用小于0或遗漏某组token都不合法。完整置换键必须逐位比较，不能把哈希碰撞当相同状态。大根堆目标有很多种，不能只搜索某个按数组堆化的结果。原数据N=16恰给全部120条互异非自环边，专用全交换分支仅在确实满足M=N(N-1)/2时使用。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Pattern {
    int n, k;
    vector<unsigned short> d;
    int firstRank[4096], firstMask[4096];
    vector<array<unsigned short, 256>> maps;
    vector<unsigned short> lastRank;
    unsigned index(uint32_t s) const {
        if (k != 7)
            return s;
        unsigned p = s & 4095, z = s >> 12;
        return firstRank[p] * 5040 +
               lastRank[maps[firstMask[p]][z & 255] | (maps[firstMask[p]][z >> 8] << 8)];
    }
    Pattern(int n, int k) : n(n), k(k) {
        if (k != 7) {
            d.assign(1u << (4 * k), 65535);
            return;
        }
        assert(n == 13);
        d.assign(8648640, 65535);
        lastRank.resize(65536);
        for (int s = 0; s < 65536; s++) {
            int used = 0, r = 0;
            bool ok = true;
            for (int i = 0; i < 4; i++) {
                int v = (s >> (4 * i)) & 15;
                if (v >= 10 || (used >> v & 1)) {
                    ok = false;
                    break;
                }
                r = r * (10 - i) + v - __builtin_popcount((unsigned)(used & ((1 << v) - 1)));
                used |= 1 << v;
            }
            if (ok)
                lastRank[s] = r;
        }
        int maskIndex[8192];
        fill(maskIndex, maskIndex + 8192, -1);
        for (int s = 0; s < 4096; s++) {
            int used = 0, r = 0;
            bool ok = true;
            for (int i = 0; i < 3; i++) {
                int v = (s >> (4 * i)) & 15;
                if (v >= n || (used >> v & 1)) {
                    ok = false;
                    break;
                }
                r = r * (n - i) + v - __builtin_popcount((unsigned)(used & ((1 << v) - 1)));
                used |= 1 << v;
            }
            if (!ok)
                continue;
            firstRank[s] = r;
            if (maskIndex[used] < 0) {
                maskIndex[used] = maps.size();
                array<unsigned short, 256> mp{};
                for (int x = 0; x < 256; x++) {
                    int a = x & 15, b = x >> 4;
                    if (a < n && b < n && !(used >> a & 1) && !(used >> b & 1)) {
                        a -= __builtin_popcount((unsigned)(used & ((1 << a) - 1)));
                        b -= __builtin_popcount((unsigned)(used & ((1 << b) - 1)));
                        mp[x] = a | (b << 4);
                    }
                }
                maps.push_back(mp);
            }
            firstMask[s] = maskIndex[used];
        }
    }
    void build(const vector<uint32_t> &goals, const vector<pair<int, int>> &edges) {
        vector<vector<uint32_t>> b(2 * n * n + 2);
        for (auto s : goals)
            if (d[index(s)]) {
                d[index(s)] = 0;
                b[0].push_back(s);
            }
        int where[16];
        for (int level = 0; level < (int)b.size(); level++)
            for (size_t at = 0; at < b[level].size(); at++) {
                uint32_t s = b[level][at];
                if (d[index(s)] != level)
                    continue;
                fill(where, where + n, -1);
                for (int i = 0; i < k; i++)
                    where[(s >> (4 * i)) & 15] = i;
                for (auto e : edges) {
                    int a = where[e.first], z = where[e.second];
                    if (a < 0 && z < 0)
                        continue;
                    uint32_t t = s;
                    int w = 0;
                    if (a >= 0) {
                        t ^= (uint32_t)(e.first ^ e.second) << (4 * a);
                        ++w;
                    }
                    if (z >= 0) {
                        t ^= (uint32_t)(e.first ^ e.second) << (4 * z);
                        ++w;
                    }
                    int nd = level + w;
                    if (nd < d[index(t)]) {
                        d[index(t)] = nd;
                        assert(nd < (int)b.size());
                        b[nd].push_back(t);
                    }
                }
            }
    }
};
struct Solver {
    int n, m, root, k, kt, limit, answer;
    int p[16], a[16], pos[16], comp[16], sz[16], dep[16], child[16];
    vector<pair<int, int>> edges;
    vector<int> adj[16];
    int unary[16][16];
    unique_ptr<Pattern> top, bottom;
    static const unsigned HS = 1u << 21;
    vector<unsigned long long> keys;
    vector<unsigned short> best, epoch;
    unsigned short gen = 0;
    bool seen(unsigned long long s, int g) {
        unsigned h = (s ^ (s >> 23)) * 11995408973635179863ULL >> (64 - 21);
        for (int z = 0; z < 16; z++, h = (h + 1) & (HS - 1)) {
            if (epoch[h] != gen) {
                epoch[h] = gen;
                keys[h] = s;
                best[h] = g;
                return false;
            }
            if (keys[h] == s) {
                if (best[h] <= g)
                    return true;
                best[h] = g;
                return false;
            }
        }
        return false;
    }
    unsigned long long state() const {
        unsigned long long s = 0;
        for (int u = 0; u < n; u++)
            s |= (unsigned long long)a[u] << (4 * u);
        return s;
    }
    bool goal() const {
        for (int u = 0; u < n; u++)
            if (p[u] >= 0 && a[p[u]] < a[u])
                return false;
        return true;
    }
    void swapAt(int u, int v) {
        swap(a[u], a[v]);
        pos[a[u]] = u;
        pos[a[v]] = v;
    }
    int heuristic() const {
        uint32_t t = 0, b = 0;
        for (int i = 0; i < kt; i++)
            t |= pos[n - 1 - i] << (4 * i);
        for (int i = 0; i < k; i++)
            b |= pos[i] << (4 * i);
        int sum = top->d[top->index(t)] + bottom->d[bottom->index(b)], mx = 0;
        for (int v = 0; v < n; v++) {
            int x = unary[v][pos[v]];
            mx = max(mx, x);
            if (v >= k && v < n - kt)
                sum += x;
        }
        int badLow = 0, badHigh = 0;
        for (int u = 0; u < n; u++) {
            badLow += a[u] < sz[u] - 1;
            badHigh += a[u] > n - 1 - dep[u];
        }
        return max(max(mx, (sum + 1) / 2), max(badLow, badHigh));
    }
    bool dfs(int g, int previous, int h) {
        if (g + h > limit)
            return false;
        if (goal()) {
            answer = g;
            return true;
        }
        if (seen(state(), g))
            return false;
        struct Move {
            int h, e;
        };
        vector<Move> moves;
        for (int i = 0; i < m; i++)
            if (i != previous) {
                auto e = edges[i];
                swapAt(e.first, e.second);
                int z = heuristic();
                swapAt(e.first, e.second);
                if (g + 1 + z <= limit)
                    moves.push_back({z, i});
            }
        sort(moves.begin(), moves.end(), [](Move x, Move y) {
            return x.h < y.h;
        });
        for (auto x : moves) {
            auto e = edges[x.e];
            swapAt(e.first, e.second);
            if (dfs(g + 1, x.e, x.h))
                return true;
            swapAt(e.first, e.second);
        }
        return false;
    }
    void seeds(int step, int available, int used, uint32_t code, bool isTop,
               vector<uint32_t> &goals) {
        if (step == (isTop ? kt : k)) {
            goals.push_back(code);
            return;
        }
        int value = isTop ? n - 1 - step : step;
        for (int bits = available; bits; bits &= bits - 1) {
            int u = __builtin_ctz((unsigned)bits);
            if (comp[u] != comp[pos[value]])
                continue;
            int nxt = available ^ (1 << u), nu = used | (1 << u);
            if (isTop)
                nxt |= child[u];
            else if (p[u] >= 0 && (child[p[u]] & ~nu) == 0)
                nxt |= 1 << p[u];
            seeds(step + 1, nxt, nu, code | ((uint32_t)u << (4 * step)), isTop, goals);
        }
    }
    int completeLower(unsigned remaining) {
        int cnt = __builtin_popcount(remaining), must = 0;
        for (int u = 0; u < n; u++)
            if (remaining >> u & 1)
                if (a[u] < sz[u] - 1)
                    must |= 1 << u;
        int f0[16] = {}, f1[16] = {};
        vector<int> order;
        function<void(int)> visit = [&](int u) {
            for (int bits = child[u]; bits; bits &= bits - 1)
                visit(__builtin_ctz((unsigned)bits));
            order.push_back(u);
        };
        visit(root);
        int total = 0;
        for (int u : order)
            if (remaining >> u & 1) {
                f0[u] = (must >> u & 1) ? 1000 : 0;
                f1[u] = 1;
                for (int bits = child[u]; bits; bits &= bits - 1) {
                    int v = __builtin_ctz((unsigned)bits);
                    if (!(remaining >> v & 1))
                        continue;
                    if (a[u] < a[v])
                        f0[u] += f1[v];
                    else
                        f0[u] += min(f0[v], f1[v]);
                    f1[u] += min(f0[v], f1[v]);
                }
                if (p[u] < 0 || !(remaining >> p[u] & 1))
                    total += min(f0[u], f1[u]);
            }
        int badLow = 0, badHigh = 0;
        for (int u = 0; u < n; u++)
            if (remaining >> u & 1) {
                badLow += a[u] < sz[u] - 1;
                badHigh += a[u] > n - 1 - dep[u];
            }
        return max((total + 1) / 2, max(badLow, badHigh));
    }
    bool completeDfs(int value, int available, unsigned remaining, int g) {
        if (g > limit)
            return false;
        if (value < 0) {
            answer = g;
            return true;
        }
        if (g + completeLower(remaining) > limit)
            return false;
        vector<int> choices;
        int v = pos[value];
        if (available >> v & 1)
            choices.push_back(v);
        for (int bits = available; bits; bits &= bits - 1) {
            int u = __builtin_ctz((unsigned)bits);
            if (u != v)
                choices.push_back(u);
        }
        for (int u : choices) {
            int cost = u != v;
            swapAt(u, v);
            if (completeDfs(value - 1, (available ^ (1 << u)) | child[u], remaining ^ (1u << u),
                            g + cost))
                return true;
            swapAt(u, v);
        }
        return false;
    }
    int solve() {
        cin >> n >> m;
        memset(child, 0, sizeof child);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            --p[i];
            if (p[i] < 0)
                root = i;
            else
                child[p[i]] |= 1 << i;
        }
        vector<int> values(n);
        for (int &i : values)
            cin >> i;
        auto sorted = values;
        sort(sorted.begin(), sorted.end());
        for (int u = 0; u < n; u++) {
            a[u] = lower_bound(sorted.begin(), sorted.end(), values[u]) - sorted.begin();
            pos[a[u]] = u;
        }
        for (int i = 0, u, v; i < m; i++) {
            cin >> u >> v;
            --u;
            --v;
            edges.push_back({u, v});
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        if (goal())
            return 0;
        function<void(int)> tree = [&](int u) {
            sz[u] = 1;
            for (int bits = child[u]; bits; bits &= bits - 1) {
                int v = __builtin_ctz((unsigned)bits);
                dep[v] = dep[u] + 1;
                tree(v);
                sz[u] += sz[v];
            }
        };
        dep[root] = 0;
        tree(root);
        if (m == n * (n - 1) / 2) {
            for (limit = completeLower((1u << n) - 1);; limit++)
                if (completeDfs(n - 1, 1 << root, (1u << n) - 1, 0))
                    return answer;
        }
        int cc = 0;
        fill(comp, comp + n, -1);
        for (int u = 0; u < n; u++)
            if (comp[u] < 0) {
                queue<int> q;
                q.push(u);
                comp[u] = cc;
                while (!q.empty()) {
                    int z = q.front();
                    q.pop();
                    for (int v : adj[z])
                        if (comp[v] < 0) {
                            comp[v] = cc;
                            q.push(v);
                        }
                }
                cc++;
            }
        int distances[16][16];
        for (int u = 0; u < n; u++) {
            fill(distances[u], distances[u] + n, 1000);
            queue<int> q;
            distances[u][u] = 0;
            q.push(u);
            while (!q.empty()) {
                int z = q.front();
                q.pop();
                for (int v : adj[z])
                    if (distances[u][v] > distances[u][z] + 1) {
                        distances[u][v] = distances[u][z] + 1;
                        q.push(v);
                    }
            }
        }
        for (int value = 0; value < n; value++)
            for (int u = 0; u < n; u++) {
                unary[value][u] = 1000;
                for (int target = 0; target < n; target++)
                    if (value >= sz[target] - 1 && value <= n - 1 - dep[target])
                        unary[value][u] = min(unary[value][u], distances[u][target]);
            }
        k = min(6, n / 2);
        kt = n <= 13 ? n - k : k;
        vector<uint32_t> gs;
        seeds(0, 1 << root, 0, 0, true, gs);
        top.reset(new Pattern(n, kt));
        top->build(gs, edges);
        gs.clear();
        int leaves = 0;
        for (int u = 0; u < n; u++)
            if (!child[u])
                leaves |= 1 << u;
        seeds(0, leaves, 0, 0, false, gs);
        bottom.reset(new Pattern(n, k));
        bottom->build(gs, edges);
        keys.resize(HS);
        best.resize(HS);
        epoch.resize(HS);
        for (limit = heuristic();; limit++) {
            if (++gen == 0) {
                fill(epoch.begin(), epoch.end(), 0);
                ++gen;
            }
            if (dfs(0, -1, heuristic()))
                return answer;
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver s;
    cout << s.solve() << '\n';
}