import sys


def solve() -> None:
    """置换分解成环，答案 = n - 环数；树的边读掉即可，不参与计算"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    pos = 0
    n = int(data[pos]); pos += 1
    perm = [0] * (n + 1)
    for i in range(1, n + 1):
        perm[i] = int(data[pos]); pos += 1
    # 后面的 n-1 条边与答案无关，直接跳过（token 已经全部读进 data 里）

    visited = [False] * (n + 1)
    cycles = 0
    for i in range(1, n + 1):
        if not visited[i]:
            cycles += 1
            j = i
            while not visited[j]:               # 顺着置换走完整个环
                visited[j] = True
                j = perm[j]

    sys.stdout.write(str(n - cycles) + "\n")


if __name__ == "__main__":
    solve()

示例推演

输入 a = [2, 1, 4, 3]（1 起编号）：

起点	走出的环	长度
1	$1 \to 2 \to 1$	2
3	$3 \to 4 \to 3$	2

环数是 2，答案 $4 - 2 = 2$ 。

具体操作（与题面一致）：

交换结点 1、2 → [1,2,4,3]；
交换结点 3、4 → [1,2,3,4]。

每个二元环用 1 次交换，合计 2 次。

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力搜索交换方案	指数级	指数级	状态是 $n!$ 个排列，不可行
置换找环	$O(n)$	$O(n)$	推荐，每个结点只走一次

易错点总结

1. 被「树」误导

题面给了树，但交换不受边的限制。如果误以为只能交换树上相邻的结点，
问题会变成完全不同的「树上 token swapping」，答案也会不一样。
判断依据是这句话：「每次可以交换任意两个节点的权值」。

2. 忘记减去环数

答案是 $n - \#\text{环}$ ：不是 $n$ ，也不是环的个数本身。长度为 1 的环
贡献 0，公式会自动处理。

3. 环没走完就换起点

必须在 while not visited[j] 里顺着 $a_j$ 一路走到底，把整个环都标记完，
再去看下一个未访问的点。中途跳出会把一个环数成多个。

4. 下标从 0 开始混用

结点编号是 $1 \sim n$ ，visited 要开 $n+1$ ，循环从 1 到 $n$ 。
写成 0 起点会错位一格。

5. 认为「已经有序」还要特殊判断

当所有 $a_i = i$ 时，每个点都是长度 1 的环，环数 $= n$ ，
答案 $n - n = 0$ ，公式本身就能覆盖，不需要额外分支。

扩展思考

若只允许交换树上相邻结点的权值，问题变成「树上 token swapping」，
一般图上是 NP-hard，树上也有专门的下界与算法，和本题完全不同。
若允许一次交换三个结点的权值（轮换），一个长度 $L$ 的环只需要
$\lceil (L-1)/2 \rceil$ 次左右，答案会改变。
「 $n$ 减去环数」这个结论也适用于「把排列变成另一个排列」：
先把目标排列复合进去，再数环即可。