Love Polygon

This problem is translated from BalticOI 2018 Day1 problem "Love Polygon".

You are given a directed graph with N vertices where every vertex has outdegree exactly 1. At a cost of 1 unit, you are allowed to modify the endpoint of any edge (i.e. change the vertex that an edge from a given vertex points to). Your goal is to achieve a configuration in which the graph decomposes into several disjoint 2-cycles (binary cycles) covering all vertices. In other words, you need to partition the vertices into pairs (u, v) such that after modifications, the edge from u goes to v and the edge from v goes to u. Determine the minimum total cost required to achieve this configuration.

Formally, let the original function be \( f: \{1,2,\dots,N\} \to \{1,2,\dots,N\} \) with the property that for every vertex \( u \) there is exactly one directed edge \( u \to f(u) \). You are allowed to change \( f(u) \) to any vertex (the cost for modifying one vertex’s edge is 1). Find the minimum total cost so that it is possible to partition the vertices into pairs \( (u,v) \) satisfying:

[ f(u)=v \quad \text{and} \quad f(v)=u, ]

Note that it is assumed that \(N\) is even.

inputFormat

The first line contains a single even integer \( N \) (number of vertices). The second line contains \( N \) integers \( f(1), f(2), \dots, f(N) \), where \( f(i) \) denotes the endpoint of the edge from vertex \( i \). vertices are numbered from 1 to \( N \).

outputFormat

Output a single integer: the minimum total cost required to modify the graph so that it decomposes into disjoint 2-cycles covering all vertices.

sample

4
2 3 4 1

2