P14116 [IAMOI R4] Sequence

Little T has two sequences, $a$ and $b$, both of length $n$. Some elements in sequence $a$ are determined, while the rest are undetermined. Little T must fill in the undetermined elements. All elements in sequence $a$ must be integers between $1$ and $n$, inclusive. After Little T determines all elements of sequence $a$, an operation is performed $m$ times. Each operation consists of two steps: 1. For all $i \in [1, n]$, set $b_i \gets a_i$. 2. For all $i \in [1, n]$, set $a_i \gets b_{b_i}$. Little T wants to know, after all $m$ operations are completed, what is the maximum possible number of distinct elements in sequence $a$?

**This problem has multiple test cases.** The first line of the input contains an integer $T$, representing the number of test cases. Then, $T$ test cases follow. For each test case: - The first line contains two positive integers $n$ and $m$, representing the length of the sequences and the number of operations. - The second line contains $n$ integers, representing the initial sequence $a$. If $a_i = 0$, the element at this position is undetermined. Otherwise, the element is determined.

For each test case, output a single line containing a positive integer, which is the answer.

**【Sample Explanation】** For the first sample case, the initial sequence $a$ is fully determined. After 2 operations, sequence $a$ becomes `1 1 1 1 1 1`. The number of distinct elements is 1. For the second sample case, Little T can set the initial sequence $a$ to `2 1 4 5 6 4`. After 2 operations, sequence $a$ becomes `1 2 4 5 6 4`. The number of distinct elements is 5. **【Constraints】** **This problem uses bundled testing.** | Subtask | $n \le$ | $m$ | Special Property | Score | |:---:|:---------------:|:---------------:|:----------------:|:---:| | 1 | $8$ | $\le 8$ | None | 10 | | 2 | $5000$ | $\le 5000$ | None | 15 | | 3 | $10^5$ | $=10^9$ | None | 10 | | 4 | $10^5$ | $\le 10^9$ | Yes | 10 | | 5 | $10^5$ | $\le 10^9$ | None | 15 | | 6 | $10^6$ | $=10^9$ | None | 10 | | 7 | $10^6$ | $\le 10^9$ | Yes | 10 | | 8 | $10^6$ | $\le 10^9$ | None | 20 | - Special Property: For all $i \in [1, n]$, $a_i \neq 0$. For all test cases, it is guaranteed that: $1 \le T \le 5$, $1 \le n \le 10^6$, $1 \le m \le 10^9$, $0 \le a_i \le n$. **【Hints】** The input size may be large. Please use fast I/O methods. Please note the specific time and memory limits for this problem.