1 sounds like the minimum value we can get. Why? Is it always true?

When n ≤ 2, we can do nothing. When n ≥ 3, since , n - 1 isn't a divisor of n, so we can choose it and get 1 as the result.

	n = int(input())
	
	If n == 2:
	   print(2)
	else:
	   print(1)

You're given a permutation p of n elements. Each person i gives their item to p[i]. The process continues daily. For each person, compute the number of days it takes to get their own item back.

This is equivalent to finding the length of the cycle each element is part of

Can u check the constraints

For each element, follow the permutation until it loops back to the original position

def check(p, n):
    res = [0] * n
    for i in range(n):
        cnt = 1
        cur = p[i] - 1
        while cur != i:
            cur = p[cur] - 1
            cnt += 1
        res[i] = cnt
    return res

q = int(input())
for _ in range(q):
    n = int(input())
    p = list(map(int, input().split()))
    print(*check(p, n))

For each element, follow the permutation until it loops back to the original position

from collections import defaultdict, deque

q = int(input())
for _ in range(q):
    n = int(input())
    p = list(map(int, input().split()))
    graph = defaultdict(list)
    for i in range(1, n + 1):
        graph[i].append(p[i - 1])

    ans = []
    for i in range(1, n + 1):
        queue = deque([i])
        visited = {i}
        days = 0
        while queue:
            node = queue.popleft()
            for neighbour in graph[node]:
                if neighbour not in visited and neighbour != node:
                    visited.add(neighbour)
                    queue.append(neighbour)
                    days += 1
        ans.append(days + 1)
    print(*ans)

Can we see that every element belonging to the same cycle actually forms a group together?

To solve the problem efficiently, we can use the Disjoint Set Union (DSU) data structure, also known as Union-Find, which is ideal for managing groups of connected elements. The core idea is to treat each cycle in the permutation as a group and then track these groups as we process the permutation.

The DSU allows us to efficiently group elements together and later find the size of each group. For this problem, we will use path compression in the find operation to speed up future queries, and union by size to ensure we merge smaller groups into larger ones, which optimizes the union operation.

We start by initializing the DSU for each test case, where each element is its own parent. Then, for each element in the permutation, we union the element with the one it points to. After processing all elements, we can use the find operation to determine the root of each element's cycle and then count the size of each cycle by checking the size of the connected group it belongs to.

This approach ensures that we can efficiently handle the problem even with large inputs, as the time complexity for both union and find operations is nearly constant, due to the inverse Ackermann function, which grows extremely slowly. Thus, the solution is both time-efficient and space-efficient for large values of n.

Time Complexity: O(n * α(n)) per test case, where n is the number of elements and α(n) is the inverse Ackermann function. For practical input sizes, α(n) is very small, often treated as a constant.

Space Complexity: O(n) for storing the parent, rank (or size), and other DSU-related arrays.

import sys

input = sys.stdin.readline

# Input helpers
I = lambda: int(input())
ILT = lambda: list(map(int, input().split()))

class DSU:
    def __init__(self, n):
        self.rank = [0] * (n + 1)
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, node):
        if node == self.parent[node]:
            return node
        stack = []
        while node != self.parent[node]:
            stack.append(node)
            node = self.parent[node]
        for n in stack:
            self.parent[n] = node
        return node

    def Sunion(self, u, v):  # Union by size
        rep_u = self.find(u)
        rep_v = self.find(v)
        if rep_u == rep_v:
            return
        if self.size[rep_u] < self.size[rep_v]:
            self.parent[rep_u] = rep_v
            self.size[rep_v] += self.size[rep_u]
        else:
            self.parent[rep_v] = rep_u
            self.size[rep_u] += self.size[rep_v]

    def Runion(self, u, v):  # Union by rank
        rep_u = self.find(u)
        rep_v = self.find(v)
        if rep_u == rep_v:
            return
        if self.rank[rep_u] < self.rank[rep_v]:
            self.parent[rep_u] = rep_v
        elif self.rank[rep_v] < self.rank[rep_u]:
            self.parent[rep_v] = rep_u
        else:
            self.parent[rep_v] = rep_u
            self.rank[rep_u] += 1

def solve():
    n = int(input())
    p = list(map(int , input().split()))
    uf = DSU(n)
    for i in range(n):
        uf.Sunion(p[i], i + 1)
    print(*[uf.size[uf.find(i)] for i in range(1, n + 1)])

for _ in range(int(input())):
    solve()

What if we think in reverse: from a graph with no edges to adding edges based on distance?