시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB2820960.000%

문제

Consider $n$ points placed around a circumference so that they form a regular polygon. Points are enumerated in clockwise order by sequential integers between $1$ and $n$. The number of points is even.

Each point is connected with exactly one other point, so $n / 2$ chords are formed. You may replace $k$ of those chords with arbitrary chords (even if they don't end in any of the given points), and then select set of chords such that each pair of chords in the set is intersecting. Your goal is to replace the chords and and select the set in such a way that the size of the set is maximum possible.

입력

The first line of input contains two integers $n$ and $k$ ($2 \le n \le 8000$, $n$ is even, $0 \le k \le \min (n / 2, 20)$).

The second line contains a permutation $P$ of the first $n$ integers denoting the connection. If $P_i = j$, it means that points $i$ and $j$ are connected by a chord. It is guaranteed that if $P_i = j$ then $P_j = i$, and that $P_i \ne i$.

출력

Print one integer: the maximal size of a set of intersecting chords which may be selected after changing $k$ of the given chords.

예제 입력 1

8 0
6 8 5 7 3 1 4 2

예제 출력 1

2

예제 입력 2

8 1
7 4 6 2 8 3 1 5

예제 출력 2

3

힌트

In the second example, you may replace the chord $(1, 7)$ to obtain a set of three intersecting chords: for example, all chords except $(2, 4)$ form a pairwise intersecting set.