Cyclic Operations (Codeforces 1867D)
Tags: Greedy, dfs and similar

Egor has an array $$$a$$$ of length $$$n$$$, initially consisting of zeros. However, he wanted to turn it into another array $$$b$$$ of length $$$n$$$.Since Egor doesn't take easy paths, only the following operation can be used (possibly zero or several times):  choose an array $$$l$$$ of length $$$k$$$ ($$$1 \leq l_i \leq n$$$, all $$$l_i$$$ are distinct) and change each element $$$a_{l_i}$$$ to $$$l_{(i\%k)+1}$$$ ($$$1 \leq i \leq k$$$). He became interested in whether it is possible to get the array $$$b$$$ using only these operations. Since Egor is still a beginner programmer, he asked you to help him solve this problem.The operation $$$\%$$$ means taking the remainder, that is, $$$a\%b$$$ is equal to the remainder of dividing the number $$$a$$$ by the number $$$b$$$.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) - the number of test cases.Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$).The second line contains the array $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output "YES" (without quotes) if there is a way to get the array $$$b$$$ using only the given operation. Otherwise, output "NO" (without quotes). You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes" and "YES" will be accepted as a positive answer.

Note: Let's consider the first example:   Apply the operation with $$$l$$$ = $$$[1,2,3]$$$. Now $$$a$$$ = $$$[2,3,1,0,0]$$$.  Apply the operation with $$$l$$$ = $$$[3,5,4]$$$. Now $$$a$$$ = $$$[2,3,5,3,4]$$$ = $$$b$$$.  We see that it is possible to get the array $$$b$$$. Therefore, the answer is YES.In the second example, it can be proven that the array $$$b$$$ cannot be obtained, therefore the answer is NO.

Sample Inputs:
6
5 3
2 3 5 3 4
4 2
2 4 3 1
1 1
1
3 1
1 2 3
5 3
5 4 3 2 1
6 1
1 2 3 1 5 6

Sample Outputs:
YES
NO
YES
YES
NO
NO

Solution (Python):
from sys import stdin
input_fn = lambda : stdin.readline().rstrip('\r\n')
for _ in range(int(input_fn())):
    (n, k) = map(int, input_fn().split())
    a = [x - 1 for x in map(int, input_fn().split())]
    if k == 1:
        if a != list(range(n)):
            print('NO')
        else:
            print('YES')
        continue
    visited = [0] * n
    colors = [0] * n
    color_count = 1
    for i in range(n):
        if visited[i]:
            continue
        (j, t) = (i, 1)
        while not visited[i]:
            visited[i] = t
            colors[i] = color_count
            (i, j) = (a[i], i)
            t += 1
        color_count += 1
        if colors[i] == colors[j] and visited[j] - visited[i] + 1 != k:
            print('NO')
            break
    else:
        print('YES')

Solution (Python):
from sys import stdin
input_fn = lambda : stdin.readline().rstrip('\r\n')
for _ in range(int(input_fn())):
    (n, k) = map(int, input_fn().split())
    a = [x - 1 for x in map(int, input_fn().split())]
    if k == 1:
        if a != list(range(n)):
            print('NO')
        else:
            print('YES')
        continue
    visited = [0] * n
    color = [0] * n
    x = 1
    for i in range(n):
        if visited[i]:
            continue
        (j, t) = (i, 1)
        while not visited[i]:
            visited[i] = t
            color[i] = x
            (i, j) = (a[i], i)
            t += 1
        x += 1
        if color[i] == color[j] and visited[j] - visited[i] + 1 != k:
            print('NO')
            break
    else:
        print('YES')

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
import itertools
import math
from math import gcd, sqrt
from collections import deque
import random
from bisect import bisect_left
from bisect import bisect_right
import operator
from operator import itemgetter
import heapq
import array

def SS(number, from_base, to_base, upper=False):
    """"""
    number = int(str(number), from_base)
    digits = '0123456789abcdefghijklmnopqrstuvwxyz'
    if to_base > len(digits):
        return None
    result = ''
    while number > 0:
        result = digits[number % to_base] + result
        number //= to_base
    return result.upper() if upper else result

def Fast_power(a, n, mod):
    """"""
    ans = 1
    while n > 0:
        if n & 1:
            ans = ans * a % mod
        a = a * a % mod
        n >>= 1
    return ans

def Hesh(s, mod):
    """"""
    h = 0
    for i in range(len(s)):
        h += Fast_power(ord(s[i]), i + 1, mod) % mod
    return h

class SET:

    def el_in_ret(el, ret) -> bool:
        """"""
        return el in ret

    def ret_in_rew(ret, rew) -> bool:
        """"""
        return rew.issubset(ret)

    def obedenenie(ret, rew) -> set:
        """"""
        return ret | rew

    def peresechenie(ret, rew) -> set:
        """"""
        return ret & rew

    def dop(el, ret) -> set:
        """"""
        return ret.add(el)

    def udal(el, ret) -> set:
        """"""
        return ret.discard(el)

class DICT:

    def sum_znach(slov) -> int:
        """"""
        return sum(slov.values())

    def spisok_keys(slov) -> list:
        """"""
        return list(slov.keys())

    def spisok_znach(slov) -> list:
        """"""
        return list(slov)

    def sort_by_keys(slov) -> dict:
        """"""
        return dict(sorted(slov.items()))

    def sort_by_znach(slov) -> dict:
        """"""
        return dict(sorted(slov.items(), key=itemgetter(1)))

    def key_with_maximum_znach(slov) -> int:
        """"""
        return max(slov.items(), key=operator.itemgetter(1))

    def maximum_znach(slov) -> int:
        """"""
        return max(start_dict.values())

class LIST:

    def perestanovki(mas) -> list:
        """"""
        permutations = list(itertools.permutations(mas))
        return permutations

    def kombinations(mas1, mas2) -> list:
        """"""
        ''
        products = list(itertools.product(x, y))
        return products

    def prefsu(mas) -> list:
        """"""
        new = []
        su = 0
        for i in range(len(mas)):
            su += mas[i]
            new += [su]
        return new

    def NVP(mas, l, r) -> int:
        new = mas[l:r]
        m = r - l + 1
        mas = [10 ** 18] * m
        for e in new:
            ind = BINP.left(e, mas)
            mas[ind] = e
        return mas.index(10 ** 18) - 1

class KUCHA:

    def dop(el, kucha) -> list:
        """"""
        return heapq.heappush(el, kucha)

    def udal(kucha) -> list:
        """"""
        return heapq.heappop(kucha)

    def zam(el, kucha) -> list:
        """"""
        return heapq.heapreplace(kucha, el)

    def n_most_big(n, kucha) -> list:
        """"""
        return heapq.nlargest(n, kucha)

    def n_most_small(n, kucha) -> list:
        """"""
        return heapq.nsmallest(n, kucha)

class STR:

    def prov_on_1(s) -> bool:
        """"""
        return s.isdigit()

    def prov_on_a(s) -> bool:
        """"""
        return s.isalpha()

    def prov_on_1a(s) -> bool:
        """"""
        return s.isalnum()

    def prov_on_down(s) -> bool:
        """"""
        return s.islower()

    def prov_on_up(s) -> bool:
        """"""
        return s.isupper()

    def upper(s) -> str:
        """"""
        return s.upper()

    def lower(s) -> str:
        """"""
        return s.lower()

class RANDOM:

    def random_0_n(n) -> int:
        """"""
        x = random.randint(0, n)
        return x

    def random_A_B(a, b) -> int:
        """"""
        x = random.randint(a, b)
        return x

    def shuf(mas) -> list:
        """"""
        random.shuffle(mas)
        return mas

class MATH:

    def take_koren(n) -> float:
        """"""
        return sqrt(n)

    def take_nod(a, b) -> int:
        """"""
        return gcd(a, b)

    def take_nok(a, b) -> int:
        """"""
        return a * b // gcd(a, b)

    def rounding_up(n) -> int:
        """"""
        return math.ceil(n)

    def rounding_down(n) -> int:
        """"""
        return math.floor(n)

    def take_log2(n) -> int:
        """"""
        return MATH.rounding_up(math.log2(n))

    def power(x, y) -> int:
        """"""
        ans = 1
        while n > 0:
            if n & 1:
                ans = ans * a % mod
            a = a * a % mod
            n >>= 1
        return ans

    def take_factorial(n) -> int:
        """"""
        if n == 0 or n == 1:
            return 1
        return MATH.take_factorial(n - 1) * n

    def rasst_A_B(x1, y1, x2, y2) -> float:
        """"""
        return MATH.take_koren((x1 - y1) * (x1 - y1) + (x2 - y2) * (x2 - y2))

    def kol_del(n) -> int:
        """"""
        k = 0
        if int(n ** 0.5) ** 2 == n:
            k -= 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                k += 2
        return k

    def prost_or_not(n) -> bool:
        """"""
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    def allprimes_to_n(n) -> list:
        """"""
        primes = [i for i in range(n + 1)]
        primes[1] = 0
        i = 2
        while i <= n:
            if primes[i] != 0:
                j = i + i
                while j <= n:
                    primes[j] = 0
                    j = j + i
            i += 1
        return [i for i in primes if i != 0]

class BINP:

    def left(elem, mas):
        """"""
        return bisect_left(mas, elem)

    def right(elem, mas):
        """"""
        return bisect_right(mas, elem)

    def vst_left(elem, mas):
        """"""
        ind = BINP.left(elem, mas)
        mas = mas[:ind] + [elem] + mas[ind:]
        return mas

    def vst_right(elem, mas):
        """"""
        ind = BINP.right(elem, mas)
        mas = mas[:ind] + [elem] + mas[ind:]
        return mas

class GRAPH:

    def matsme(mas):
        """"""
        ma = -10 ** 18
        for el in mas:
            ma = max(ma, el[0], el[1])
        S = [[] for i in range(ma)]
        for el in mas:
            a = el[0] - 1
            b = el[1] - 1
            S[a] += [b]
            S[b] += [a]
        return S

    def bfs(graph, v):
        """"""
        v -= 1
        vis = [-1] * len(graph)
        vis[v] = 0
        mas1 = [v]
        mas2 = []
        while len(mas1) > 0:
            for el in mas1:
                for i in range(len(graph[el])):
                    new_v = graph[el][i]
                    if vis[new_v] == -1:
                        mas2 += [new_v]
                        vis[new_v] = 0
            mas1 = mas2
            mas2 = []

    def dfs(graph, v):
        """"""
        v -= 1
        vis = [-1] * len(graph)
        GRAPH.realdfs(graph, v, vis)

    def realdfs(graph, v, vis):
        vis[v] = 0
        for i in range(len(graph[v])):
            new_v = graph[v][i]
            if vis[new_v] == -1:
                GRAPH.realdfs(graph, new_v, vis)

    def matsmede(mas):
        """"""
        ma = -10 ** 18
        for el in mas:
            ma = max(ma, el[0], el[1])
        S = [[] for i in range(ma)]
        for el in mas:
            a = el[0] - 1
            b = el[1] - 1
            c = el[2]
            S[a] += [[b, c]]
            S[b] += [[a, c]]
        return S

    def Deikstra(graphpair, start, finish):
        """"""
        start -= 1
        finish -= 1
        n = len(graphpair)
        INF = 10 ** 18
        cur = start
        dist = [INF] * n
        dist[cur] = 0
        diiist = [INF] * n
        diiist[cur] = 0
        pred = [0] * n
        while cur != finish and dist[cur] != INF:
            mas = graphpair[cur]
            for i in range(len(mas)):
                dist[mas[i][0]] = min(dist[mas[i][0]], dist[cur] + mas[i][1])
                if min(dist[mas[i][0]], dist[cur] + mas[i][1]) == dist[cur] + mas[i][1]:
                    pred[mas[i][0]] = cur
                diiist[mas[i][0]] = min(diiist[mas[i][0]], diiist[cur] + mas[i][1])
            diiist[cur] = INF
            cur = diiist.index(min(diiist))
        i = finish
        ans = []
        while i != start:
            ans += [i + 1]
            i = pred[i]
        ans += [i + 1]
        ans.reverse()
        return (dist[finish], ans)

    def kol_komponent(graph):
        """"""
        n = len(graph)
        vis = [-1] * n
        ans = 0
        for i in range(n):
            if vis[i] == -1:
                ans += 1
                v = i
                mas1 = [v]
                mas2 = []
                while len(mas1) > 0:
                    for el in mas1:
                        for i in range(len(graph[el])):
                            new_v = graph[el][i]
                            if vis[new_v] == -1:
                                mas2 += [new_v]
                                vis[new_v] = 0
                    mas1 = mas2
                    mas2 = []
        return ans

class FEN:

    def Fenwikstart(mas):
        """"""
        n = len(mas)
        Fenwiksum = [0] * n
        for i in range(len(mas)):
            ind1 = i & i + 1
            ind2 = i
            Fenwiksum[i] = sum(mas[ind1:ind2 + 1])
        return Fenwiksum

    def Fenwiksum(Fsum, l, r):
        """"""
        su1 = 0
        while r >= 0:
            su1 += Fsum[r]
            r = (r & r + 1) - 1
        su2 = 0
        l -= 1
        while l >= 0:
            su2 += Fsum[l]
            l = (l & l + 1) - 1
        return su1 - su2

    def Fenwikizm(Fsum, mas, ind, x):
        """"""
        razn = x - mas[ind]
        n = len(Fsum)
        while ind < n:
            Fsum[ind] += razn
            ind = ind | ind + 1
        return Fsum
    ''

class DO:

    def DOstart(mas):
        """"""
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [0] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = Der[i * 2] + Der[i * 2 + 1]
        return (Der, mas)

    def DOsum(do, v, tl, tr, l, r):
        """"""
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)) + DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)

    def DOizm(do, ind, x):
        """"""
        el = do[len(do) // 2 + ind]
        razn = x - el
        ind = ind + len(do) // 2
        do[ind] += razn
        while ind > 1:
            ind = ind // 2
            do[ind] += razn
        return do
    ''

class DOMIN:

    def DOminstart(mas):
        """"""
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [10 ** 18] * (k - l)
        n = len(mas)
        Der = [10 ** 18] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = min(Der[i * 2], Der[i * 2 + 1])
        return (Der, mas)

    def DOmin(do, v, tl, tr, l, r):
        """"""
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return min(DO.DOmin(do, v * 2, tl, tm, l, min(r, tm)), DO.DOmin(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r))

    def DOminizm(do, ind, x):
        """"""
        ind = ind + len(do) // 2
        do[ind] = x
        while ind > 1:
            p = ind // 2
            do[p] = min(do[p * 2], do[p * 2 + 1])
            ind = ind // 2
        return do
    ''

class DOMAX:

    def DOmaxstart(mas):
        """"""
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [-10 ** 18] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = max(Der[i * 2], Der[i * 2 + 1])
        return (Der, mas)

    def DOmax(do, v, tl, tr, l, r):
        """"""
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return max(DO.DOmax(do, v * 2, tl, tm, l, min(r, tm)), DO.DOmax(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r))

    def DOmaxizm(do, ind, x):
        """"""
        ind = ind + len(do) // 2
        do[ind] = x
        while ind > 1:
            p = ind // 2
            do[p] = max(do[p * 2], do[p * 2 + 1])
            ind = ind // 2
        return do
    ''

class LRS:

    def vozv(T, n, e, mod):
        """"""
        ''
        if n == 0:
            return 1
        if n % 2 == 1:
            x = LRS.vozv(T, n - 1, e, mod)
            if x != 1 and x != None:
                resultant_matrix = [[0] * e for i in range(e)]
                for i in range(len(x)):
                    for j in range(len(T[0])):
                        for k in range(len(T)):
                            resultant_matrix[i][j] += x[i][k] * T[k][j] % mod
                return resultant_matrix
            return T
        else:
            x = LRS.vozv(T, n // 2, e, mod)
            if x != 1 and x != None:
                resultant_matrix = [[0] * e for i in range(e)]
                for i in range(len(x)):
                    for j in range(len(x[0])):
                        for k in range(len(x)):
                            resultant_matrix[i][j] += x[i][k] * x[k][j] % mod
                return resultant_matrix
            return x

    def F(n, A0, mas, mod):
        D = A0.copy()
        A0 = []
        for el in D:
            A0 += [[el]]
        A0.reverse()
        T = [mas, [1, 0, 0], [0, 1, 0]]
        e = len(T[0])
        T_v_stepeni_n = LRS.vozv(T, n, e, mod)
        new = [[sum((a * b for (a, b) in zip(A_row, B_col))) for B_col in zip(*A0)] for A_row in T_v_stepeni_n]
        for i in range(e):
            for j in range(1):
                new[i][j] = new[i][j] % mod
        return new[-1][0]
    ''
for test in range(int(input())):
    (n, k) = map(int, input().split())
    s = {}
    (*mas,) = map(int, input().split())
    for i in range(len(mas)):
        s[i] = mas[i] - 1
    if k == 1 and mas != [i for i in range(1, n + 1)]:
        print('NO')
    elif k == 1 and mas == [i for i in range(1, n + 1)]:
        print('YES')
    else:
        vis = [0] * n
        comp = [0] * n
        ans = 'YES'
        for v in range(n):
            if vis[v] == 0:
                t = 1
                i = v
                j = i
                while vis[i] == 0:
                    vis[i] = t
                    comp[i] = v + 1
                    i = s[i]
                    t += 1
                if comp[i] == comp[j] and t - vis[i] != k:
                    ans = 'NO'
        print(ans)