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?

We are given a tree, and for each integer $$$k$$$ from 1 to $$$n$$$, we must count the number of connected components in a graph $$$Gk$$$​, where an edge exists between two nodes only if their distance in the tree is at least $$$k$$$. Instead of checking all pairs of nodes for each $$$k$$$, which would be too slow $$$O(n^2)$$$, we take advantage of tree properties:

• In a tree, there's a unique path between any two nodes. So we can define the "distance" easily using BFS or DFS.

• Let’s fix a special node the farthest node from any random node (say, node $$$0$$$). From that, perform BFS to find the node furthest from it this gives one endpoint of the diameter. Do a final BFS from this endpoint to get the actual diameter and each node’s distance from it. We then compute the maximum distance for each node from either endpoint of the diameter. If the maximum distance of a node is less than $$$k$$$, then this node becomes isolated in $$$Gk$$$ since no other node is at distance ≥ $$$k$$$.

Hence, for each $$$k$$$, we count how many nodes become isolated (i.e., their max distance $$$k$$$, and increment the number of components accordingly. This gives an $$$O(n)$$$ solution using just a few BFS traversals and basic counting.

from collections import deque

def bfs(tree, start):
    n = len(tree)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        node = q.popleft()
        for neighbor in tree[node]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[node] + 1
                q.append(neighbor)
    return dist

def main():
    n = int(input())

    tree = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        # Convert to 0-based index  
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    # Step 1: BFS from arbitrary node (0) to find one endpoint of diameter
    d1 = bfs(tree, 0)
    far1 = d1.index(max(d1))

    # Step 2: BFS from far1 to get distances and find farthest point (diameter)
    d2 = bfs(tree, far1)
    diameter = max(d2)
    far2 = d2.index(diameter)

    # Step 3: BFS from far2 to get second set of distances
    d3 = bfs(tree, far2)

    # For each node, take the maximum distance to either end of diameter
    max_dist = [max(d2[i], d3[i]) for i in range(n)]

    # Count how many nodes have max_dist < k
    isolated_count = [0] * (n + 2)
    for d in max_dist:
        isolated_count[d] += 1

    result = [1]  # G_1 has 1 component (the whole tree)
    for k in range(2, n + 1):
        if k > diameter:
            result.append(n)
        else:
            result.append(result[-1] + isolated_count[k - 1]) 

    print(' '.join(map(str, result)))

main()