The only difference between easy and hard versions is constraints.

There are $n$ kids, each of them is reading a unique book. At the end of any day, the $i$-th kid will give his book to the $p_i$-th kid (in case of $i = p_i$ the kid will give his book to himself). It is guaranteed that all values of $p_i$ are distinct integers from $1$ to $n$ (i.e. $p$ is a permutation). The sequence $p$ doesn't change from day to day, it is fixed.

For example, if $n=6$ and $p=[4, 6, 1, 3, 5, 2]$ then at the end of the first day the book of the $1$-st kid will belong to the $4$-th kid, the $2$-nd kid will belong to the $6$-th kid and so on. At the end of the second day the book of the $1$-st kid will belong to the $3$-th kid, the $2$-nd kid will belong to the $2$-th kid and so on.

Your task is to determine the number of the day the book of the $i$-th child is returned back to him for the first time for every $i$ from $1$ to $n$.

Consider the following example: $p = [5, 1, 2, 4, 3]$. The book of the $1$-st kid will be passed to the following kids:  after the $1$-st day it will belong to the $5$-th kid,  after the $2$-nd day it will belong to the $3$-rd kid,  after the $3$-rd day it will belong to the $2$-nd kid,  after the $4$-th day it will belong to the $1$-st kid. 

So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 1000$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of kids in the query. The second line of the query contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct, i.e. $p$ is a permutation), where $p_i$ is the kid which will get the book of the $i$-th kid.

It is guaranteed that $\sum n \le 2 \cdot 10^5$ (sum of $n$ over all queries does not exceed $2 \cdot 10^5$).


-----Output-----

For each query, print the answer on it: $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the number of the day the book of the $i$-th child is returned back to him for the first time in this query.


-----Example-----
Input
6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3

Output
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4

Difficulty: EASY
Tags: Spanning trees

Graph traversal

Mathematics

Starter code:

Solutions:
for k in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ary = [-1] * n
	for i in range(len(ls)):
		if ary[i] != -1:
			continue
		cnt = 1
		val = ls[i] - 1
		valls = [i]
		while val != i:
			cnt += 1
			valls.append(val)
			val = ls[val] - 1
		for j in range(len(valls)):
			ary[valls[j]] = cnt
	print(*ary)


tc = int(input())
while tc > 0:
	tc -= 1
	n = int(input())
	p = [0] + list(map(int, input().split()))
	ans = [0] * (n + 1)
	mk = [False] * (n + 1)
	for i in range(1, n + 1):
		if not mk[i]:
			sz = 1
			curr = p[i]
			mk[i] = True
			while curr != i:
				sz += 1
				mk[curr] = True
				curr = p[curr]
			ans[i] = sz
			curr = p[i]
			while curr != i:
				ans[curr] = sz
				curr = p[curr]
	print(' '.join([str(x) for x in ans[1:]]))


from collections import defaultdict
q = int(input())
for _ in range(q):
	n = int(input())
	l = [0] + list(map(int, input().split()))
	boo = defaultdict(bool)
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		z = i
		seti = set()
		while boo[z] == False:
			seti.add(z)
			boo[z] = True
			z = l[z]
		for j in seti:
			ans[j] = len(seti)
	print(*ans[1:])


q = int(input())
nums = []
pos = []
for _ in range(q):
	nums += [int(input())]
	p = input().split()
	pos += [[int(x) - 1 for x in p]]
for i in range(q):
	n = nums[i]
	p = pos[i]
	list1 = list(range(n))
	list2 = []
	dict = dict.fromkeys(list(range(n)), 0)
	for i in list1:
		if i == 'a':
			continue
		j = p[i]
		count = 1
		while j != i:
			j = p[j]
			count += 1
		j = p[i]
		dict[i] = count
		while j != i:
			list1[j] = 'a'
			dict[j] = count
			j = p[j]
	for key in dict.keys():
		print(dict[key], end=' ')


q = int(input())
for i in range(q):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = [0] * n
	for i in range(n):
		if ans[i] == 0:
			numbers_now = []
			now = a[a[i] - 1]
			numbers_now.append(i)
			numbers_now.append(a[i] - 1)
			count = 1
			while now != a[i]:
				now = a[now - 1]
				numbers_now.append(now - 1)
				count += 1
			for i in numbers_now:
				ans[i] = count
		else:
			continue
	print(*ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = [0] * n
	for i in range(n):
		if not a[i]:
			pos = l[i] - 1
			ans = 1
			while pos != i:
				ans += 1
				pos = l[pos] - 1
			a += str(ans) + ' '
			a[i] = ans
			pos = l[i] - 1
			while pos != i:
				a[pos] = ans
				pos = l[pos] - 1
	for i in range(n):
		print(a[i], end=' ')
	print()


for _ in range(int(input())):
	n_kids = int(input())
	l = list(map(int, input().split()))
	res = [None] * n_kids
	days = 1
	for i in range(n_kids):
		if not res[i]:
			if l[i] == i + 1:
				res[i] = 1
				continue
			else:
				cycle = [l[i]]
				while cycle[-1] != i + 1:
					days += 1
					cycle.append(l[cycle[-1] - 1])
				for e in cycle:
					res[e - 1] = days
				days = 1
	print(*res)


import re

def read(t=int):
	return list(map(t, input().strip().split(' ')))
q = read()[0]

def check(lis):
	...
while q > 0:
	q -= 1
	n = read()[0]
	p = [None] + read()
	ans = [-1 for i in p]
	for i in range(1, len(p)):
		if ans[i] != -1:
			...
		else:
			stack = [i]
			day = 0
			while True:
				now = p[stack[-1]]
				day += 1
				if now == i:
					break
				else:
					if ans[now] != -1:
						day += ans[now]
						break
					stack.append(now)
			for k in stack:
				ans[k] = day
		print('{} '.format(ans[i]), end='')
	print()


q = int(input())

def check(n, p):
	ans = [0] * n
	for i in range(n):
		group = []
		k = 1
		if p[i] != 0:
			j = p[i]
			group.append(i + 1)
			while j != i + 1:
				k += 1
				group.append(j)
				j = p[j - 1]
			for a in group:
				ans[a - 1] = k
				p[a - 1] = 0
	return ans
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	m = check(n, p)
	print(*m)


from sys import stdin
cin = stdin.readline
for _ in range(int(cin())):
	n = int(cin())
	a = list(map(int, cin().split()))
	result = [-1] * (n + 1)
	for i in range(n):
		if result[i + 1] != -1:
			continue
		(x, y, cnt) = (-1, i + 1, 0)
		visited = []
		while x != i + 1:
			x = a[y - 1]
			y = x
			cnt += 1
			visited.append(x)
		for child in visited:
			result[child] = cnt
	for i in range(1, n + 1):
		print(result[i], end=' ')
	print()


for _ in range(int(input())):
	kids = int(input())
	order = list(map(int, input().split()))
	used = set()
	re = [None] * kids
	for j in range(1, kids + 1):
		if re[j - 1]:
			continue
		else:
			idx = order[j - 1]
			days = 1
			group = set()
			group.add(idx)
			while j != idx:
				temp = order[idx - 1]
				idx = temp
				group.add(idx)
				days += 1
			for i in group:
				re[i - 1] = days
	print(*re)


def ft(L, x):
	nb = 0
	i = x
	Tab = []
	while True:
		i = L[i - 1]
		nb += 1
		Tab.append(i)
		if i == x:
			return (Tab, nb)

def remplir(T, L, x):
	couple = ft(L, x)
	n = couple[1]
	tab = couple[0]
	for i in range(n):
		T[tab[i] - 1] = n
	return T

def affichage(L):
	for i in range(len(L)):
		L[i] = str(L[i])
	return ' '.join(L)
m = int(input())
for i in range(m):
	n = int(input())
	ch = input()
	L = [int(i) for i in ch.split(' ')]
	T = len(L) * [0]
	for j in range(len(L)):
		if T[j] == 0:
			T = remplir(T, L, j + 1)
	print(affichage(T))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0 for i in range(n)]
	for i in range(n):
		if ans[i] == 0:
			ct = a[i]
			d = 1
			while ct != i + 1:
				d += 1
				ct = a[ct - 1]
			ct = a[i]
			ans[i] = d
			while ct != i + 1:
				ans[ct - 1] = d
				ct = a[ct - 1]
	for i in range(n):
		print(ans[i], end=' ')
	print()


def compute(n, arr):
	temp_arr = [0] * n
	used = [False] * n
	for i in range(n):
		if used[i]:
			pass
		else:
			ans = 1
			cur = arr[i] - 1
			cycle = [i]
			while i != cur:
				cycle.append(cur)
				ans += 1
				cur = arr[cur] - 1
			for i in cycle:
				if temp_arr[i] == 0:
					temp_arr[i] = ans
					used[i] = True
	return temp_arr
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*compute(n, arr))


import sys

def I():
	return sys.stdin.readline().rstrip()
q = int(I())
for _ in range(q):
	n = int(I())
	c = [-1] * n

	def getp(i):
		s = []
		while c[i] >= 0:
			s.append(i)
			i = c[i]
		for j in s:
			c[j] = i
		return i
	p = list(map(int, I().split()))
	p = [i - 1 for i in p]
	for (i, q) in enumerate(p):
		(a, b) = (getp(i), getp(q))
		if a != b:
			c[a] += c[b]
			c[b] = a
	for i in p:
		print(-c[getp(i)], end=' ')
	print()


from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
q = int(input())
for _ in range(q):
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	used = [0] * n
	ans = [0] * n
	for j in range(n):
		if used[j] == 0:
			cur = []
			while used[j] == 0:
				cur.append(j)
				used[j] = 1
				j = p[j]
			for i in cur:
				ans[i] = len(cur)
	print(*ans)


def solve(n, p_s):
	sets = []
	visited = set([])
	for (i, p) in enumerate(p_s):
		if i in visited:
			continue
		new_indices = set([])
		cur = i
		while True:
			if cur in new_indices:
				break
			new_indices.add(cur)
			visited.add(cur)
			cur = p_s[cur] - 1
		sets.append(new_indices)
	ans = [0 for _ in range(n)]
	for indices in sets:
		for index in indices:
			ans[index] = str(len(indices))
	return ' '.join(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	p_s = [int(r) for r in input().split(' ')]
	print(solve(n, p_s))


import math
from collections import deque, defaultdict
from sys import stdin, stdout
input = stdin.readline
listin = lambda : list(map(int, input().split()))
mapin = lambda : map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] -= 1
	col = [0 for i in range(n)]
	c = 1
	for i in range(n):
		if not col[i]:
			s = i
			while col[s] == 0:
				col[s] = c
				s = a[s]
			c += 1
	d = defaultdict(int)
	for i in col:
		d[i] += 1
	ans = [0 for i in range(n)]
	for i in range(n):
		ans[i] = d[col[i]]
	print(*ans)


def read():
	return list(map(int, input().split()))
q = int(input())
for test in range(q):
	n = int(input())
	a = read()
	for i in range(n):
		a[i] -= 1
	used = [False] * n
	ans = [0] * n
	for i in range(n):
		if not used[i]:
			j = a[i]
			k = 1
			while j != i:
				k += 1
				j = a[j]
			j = a[i]
			ans[i] = k
			while j != i:
				j = a[j]
				ans[j] = k
				used[j] = True
	print(*ans)


for rpt in range(int(input())):
	kcount = int(input())
	kids = [int(x) - 1 for x in input().split(' ')]
	reskids = [0 for x in range(kcount)]
	for i in range(kcount):
		if reskids[i] == 0:
			if kids[i] == i:
				reskids[i] = 1
			else:
				fn = kids[i]
				cycle = [fn]
				current = kids[fn]
				while not current == fn:
					cycle.append(current)
					current = kids[current]
				fnres = len(cycle)
				if fnres == kcount:
					reskids = [fnres for x in range(kcount)]
					break
				else:
					for i in cycle:
						reskids[i] = fnres
	res = ''
	for i in reskids:
		res += str(i) + ' '
	print(res)


import sys
tc = int(sys.stdin.readline())
for _ in range(tc):
	n = int(sys.stdin.readline())
	arr = [0] + list(map(int, sys.stdin.readline().split()))
	res = [0] * (n + 1)
	for i in range(1, n + 1):
		if not res[i]:
			pos = arr[i]
			ans = 1
			cycle = [i]
			while pos != i:
				cycle.append(pos)
				ans += 1
				pos = arr[pos]
			for j in cycle:
				res[j] = ans
	print(' '.join(map(str, res[1:])))


q = int(input())
for qq in range(q):
	n = int(input())
	P = list(map(int, input().split()))
	P.insert(0, 0)
	root = list(range(n + 1))
	cnt = list(range(n + 1))
	for i in range(0, n + 1):
		cnt[i] = 1

	def getroot(u):
		if root[u] == u:
			return u
		else:
			root[u] = getroot(root[u])
			return root[u]
	for i in range(1, n + 1):
		cnt[getroot(i)] = cnt[getroot(i)] + cnt[getroot(P[i])]
		root[getroot(P[i])] = getroot(i)
	for i in range(1, n + 1):
		print(cnt[getroot(i)] // 2, end=' ')
	print()


q = int(input())
for i in range(q):
	n = int(input())
	p_seq = list(map(int, input().split()))
	p_seq = [x - 1 for x in p_seq]
	anslist = [0 for b in range(n)]
	ansboolean = [False for c in range(n)]
	for a in range(n):
		if not ansboolean[a]:
			ans = 1
			person_to_pass = p_seq[a]
			ansboolean[a] = True
			while person_to_pass != a:
				ansboolean[person_to_pass] = True
				person_to_pass = p_seq[person_to_pass]
				ans += 1
			person_to_pass = p_seq[a]
			anslist[a] = ans
			while person_to_pass != a:
				anslist[person_to_pass] = ans
				person_to_pass = p_seq[person_to_pass]
	print(' '.join([str(x) for x in anslist]))


import sys
sys.setrecursionlimit(1000000)
from collections import deque

def rec(ii, start, cnt):
	if cnt > n:
		return n
	if ans[ii] != -1:
		return cnt
	if ii == start:
		ans[ii] = cnt
		return cnt
	ansi = rec(arr[ii], start, cnt + 1)
	ans[ii] = ansi
	return ansi
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [x - 1 for x in arr]
	ans = [-1 for _ in range(n)]
	vis = set()
	for (i, x) in enumerate(arr):
		if i not in vis:
			cycle = [i]
			vis.add(i)
			j = arr[i]
			while j != i:
				vis.add(j)
				cycle.append(j)
				j = arr[j]
			for j in cycle:
				ans[j] = len(cycle)
	try:
		print(*ans)
	except Exception as e:
		print('wrong answer')


q = int(input())
for _ in range(q):
	n = int(input())
	perm = list(map(int, input().split()))
	remain = set(perm)
	result = {i + 1: 0 for i in range(n)}
	while len(remain) > 0:
		m = remain.pop()
		cycle = [m]
		while True:
			m = perm[m - 1]
			if m not in remain:
				break
			remain.remove(m)
			cycle.append(m)
		k = len(cycle)
		for j in cycle:
			result[j] = str(k)
	print(' '.join(result.values()))


for i in range(int(input())):
	n = int(input())
	ans = [0] * n
	arr = list(map(int, input().split()))
	visited = [0] * n
	for i in range(n):
		if arr[i] != i + 1 and visited[i] == 0:
			if arr[arr[i] - 1] == i + 1:
				visited[i] = 1
				ans[i] = 2
				ans[arr[i] - 1] = 2
				visited[arr[i] - 1] = 1
			else:
				c = 0
				ic = arr[i] - 1
				l = []
				l.append(ic)
				while ic != i:
					ic = arr[ic] - 1
					l.append(ic)
				p = len(l)
				for i in l:
					ans[i] = p
					visited[i] = 1
		elif visited[i] == 0:
			ans[i] = 1
			visited[i] = 1
	print(*ans)


def main():
	Q = int(input())
	for query in range(Q):
		N = int(input())
		P = [int(i) - 1 for i in input().split()]
		par = [i for i in range(N)]
		rank = [1 for i in range(N)]

		def find_root(x):
			if par[x] == x:
				return x
			else:
				par[x] = find_root(par[x])
				return par[x]

		def is_same_group(x, y):
			return find_root(x) == find_root(y)

		def unite(x, y):
			x = find_root(x)
			y = find_root(y)
			if x == y:
				return
			if rank[x] < rank[y]:
				(x, y) = (y, x)
			rank[x] += rank[y]
			par[y] = x

		def size(x):
			return rank[find_root(x)]
		for (i, p) in enumerate(P):
			unite(i, p)
		ans = []
		for i in range(N):
			ans.append(size(i))
		print(*ans)
main()


h = int(input())
for _ in range(h):
	n = int(input())
	ar = [int(i) for i in input().split(' ')]
	d = dict()
	for i in range(1, n + 1):
		d[i] = -1
	for i in range(1, n + 1):
		if d[i] == -1:
			val = ar[i - 1]
			aa = [i]
			count = 1
			while True:
				if val != i:
					aa.append(val)
					val = ar[val - 1]
					count += 1
				else:
					break
			k = 0
			while k < len(aa):
				d[aa[k]] = count
				k += 1
	for i in d.keys():
		print(str(d[i]), end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	used = [False] * n
	r = [0] * n
	for i in range(n):
		if not used[i]:
			j = i
			cycle = []
			while not used[j]:
				cycle.append(p[j])
				used[j] = True
				j = p[j]
			for c in cycle:
				r[c] = len(cycle)
	print(*r)


import sys
import itertools
import math
import collections
from collections import Counter

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return list(map(int, input().split()))

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
t = ii()
for i in range(t):
	n = ii()
	d = li()
	s = [0] * n
	used = [-1] * n
	for i in range(n):
		if used[i] == -1:
			(u, v) = (i, d[i] - 1)
			while True:
				s[i] += 1
				used[u] = i
				(u, v) = (v, d[v] - 1)
				if u == i:
					break
	res = []
	for i in range(n):
		res.append(s[used[d[i] - 1]])
	prr(res)


import sys

def atoi(line):
	line = line.rstrip().split()
	return list(map(int, line))
ans = []
q = int(input())
for q_ in range(q):
	n = int(input())
	p = atoi(sys.stdin.readline())
	p.insert(0, 0)
	used = [False] * (n + 1)
	days = [1] * (n + 1)
	i = 1
	while i < n + 1:
		if used[i]:
			i += 1
			continue
		loop = [i]
		used[i] = True
		j = p[i]
		while j != loop[0]:
			j = p[j]
			loop.append(p[j])
			used[j] = True
		i += 1
		for k in loop:
			days[k] = len(loop)
	ans.append(days)
for d in ans:
	d = d[1:]
	print(*d, sep=' ')


import sys

def main():
	for _ in range(int(input())):
		n = int(sys.stdin.readline())
		l = [int(x) for x in sys.stdin.readline().split()]
		k = []
		v = [0] * n
		for i in range(n):
			l[i] = l[i] - 1
		for i in range(n):
			if v[i] == 0:
				p = []
				v[i] = 1
				p.append(i)
				x = l[i]
				while x != i:
					v[x] = 1
					p.append(x)
					x = l[x]
				k.append(p)
		for i in range(len(k)):
			for j in range(len(k[i])):
				l[k[i][j]] = len(k[i])
		for i in l:
			print(i, end=' ')
		print()
main()


q = int(input())
while q:
	n = int(input())
	arr = list(map(int, input().split()))
	result = [-1 for _ in range(n)]
	for i in range(n):
		if result[i] == -1:
			cycle = []
			j = i
			nextone = arr[j] - 1
			cycle.append(i)
			res = 1
			while nextone != i:
				cycle.append(nextone)
				j = nextone
				nextone = arr[j] - 1
				res += 1
			for x in cycle:
				result[x] = res
	print(*result)
	q -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = arr
	f = [0] * n
	used = [False] * n
	for i in range(0, n):
		if not used[i]:
			v = arr[i] - 1
			ans = 1
			cycle = [i]
			while not used[v]:
				used[v] = True
				cycle.append(v)
				v = arr[v] - 1
			for el in cycle:
				f[el] = len(cycle) - 1
	print(*f)


q = int(input())
for _ in range(q):
	n = int(input())
	succ = list(map(lambda x: int(x) - 1, input().split()))
	cycle_belong = [-1 for k in range(n)]
	cycle_size = []
	for k in range(n):
		if cycle_belong[k] == -1:
			start = k
			current = k
			cycle_belong[k] = len(cycle_size)
			size_cycle = 1
			while succ[current] != start:
				size_cycle += 1
				cycle_belong[current] = len(cycle_size)
				current = succ[current]
			cycle_belong[current] = len(cycle_size)
			cycle_size.append(size_cycle)
	print(' '.join(map(lambda x: str(cycle_size[cycle_belong[x]]), range(n))))


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	l = [[] * n for i in range(n)]
	res = [0] * n
	for i in range(n):
		if not l[i]:
			r = []
			while not l[i]:
				r.append(i)
				l[i].append(1)
				i = p[i] - 1
			for j in r:
				res[j] = len(r)
	print(*res)


N = []
AA = []
t = int(input())
for i in range(t):
	N.append(int(input()))
	a = list(map(int, input().split()))
	for j in range(len(a)):
		a[j] -= 1
	AA.append(a)
for i in range(t):
	n = N[i]
	A = AA[i]
	ans = [0] * n
	for j in range(n):
		if ans[j] == 0:
			M = []
			c = 1
			b = A[j]
			M.append(b)
			while b != j:
				b = A[b]
				M.append(b)
				c += 1
			for kk in M:
				ans[kk] = c
	print(' '.join([str(i) for i in ans]))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = ''
	days = [0] * n
	for i in range(n):
		count = 0
		present = i
		if days[i] == 0:
			seen = []
			while True:
				present = p[present] - 1
				count += 1
				seen.append(present)
				if present == i:
					break
			for j in seen:
				days[j] = count
	print(*days)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
import bisect
import heapq
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve():
	n = int(inp())
	a = lis()
	visited = [0] * (n + 1)
	cnt = [0] * n
	for i in range(0, n):
		if visited[i] == 0:
			visited[i] = 1
			arr = []
			curr = a[i]
			while curr != i + 1:
				visited[curr - 1] = 1
				arr.append(curr)
				curr = a[curr - 1]
			arr.append(i + 1)
			ll = len(arr)
			for j in range(0, ll):
				cnt[arr[j] - 1] = ll
	print(*cnt)
testcase(int(inp()))


q = int(input())

def find(x, root):
	if root[x] == -1:
		root[x] = x
		return x
	trace = []
	while root[x] != x:
		trace.append(x)
		x = root[x]
	for n in trace:
		root[n] = x
	return x

def union(x, y, root):
	px = find(x, root)
	py = find(y, root)
	if px != py:
		root[px] = py
for _ in range(q):
	n = int(input())
	nums = [int(x) - 1 for x in input().split()]
	root = [-1] * len(nums)
	for (i, x) in enumerate(nums):
		union(i, x, root)
	size = {}
	for i in range(len(nums)):
		root[i] = find(i, root)
	for x in root:
		if x in size:
			size[x] += 1
		else:
			size[x] = 1
	result = []
	for i in range(len(nums)):
		result.append(str(size[root[i]]))
	print(' '.join(result))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

class DSU(object):

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.rank = [1] * n
		self.cycle = False

	def find(self, key):
		if self.parent[key] != key:
			self.parent[key] = self.find(self.parent[key])
		return self.parent[key]

	def union(self, a, b):
		(s1, s2) = (self.find(a), self.find(b))
		if s1 != s2:
			if self.rank[s1] < self.rank[s2]:
				self.parent[s1] = s2
				self.rank[s2] += self.rank[s1]
			else:
				self.parent[s2] = s1
				self.rank[s1] += self.rank[s2]
		else:
			self.cycle = True

	def has_cycle(self):
		return self.cycle

	def show_parent(self):
		return self.parent

	def show_rank(self):
		return self.rank

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = DSU(n + 1)
	for i in range(n):
		d.union(i + 1, a[i])
	leader = d.show_parent()[1:]
	rank = d.show_rank()[1:]
	ans = []
	for i in range(n):
		ans.append(rank[d.find(a[i]) - 1])
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [-1] * n
	for q in range(n):
		s = []
		q1 = q
		while (len(s) == 0 or q1 != s[0]) and ans[q1] == -1:
			s.append(q1)
			q1 = a[q1] - 1
		if len(s) and s[0] == q1:
			for q2 in range(len(s) - 1, -1, -1):
				ans[s[q2]] = len(s)
		else:
			for q2 in range(len(s) - 1, -1, -1):
				ans[s[q2]] = ans[q1] + len(s) - q2
	print(*ans)


from typing import List

def books_exchange(n: int, p: List[int]):
	a = dict()
	s = set(p)
	while s:
		random_kid = s.pop()
		kid_in_loop = {random_kid}
		while True:
			next_kid = p[random_kid - 1]
			if next_kid in kid_in_loop:
				break
			kid_in_loop.add(next_kid)
			s.remove(next_kid)
			random_kid = next_kid
		count = len(kid_in_loop)
		for kid in kid_in_loop:
			a[kid] = count
	return [a[i] for i in range(1, n + 1)]

def test():
	assert books_exchange(5, [1, 2, 3, 4, 5]) == [1, 1, 1, 1, 1]
	assert books_exchange(3, [2, 3, 1]) == [3, 3, 3]
	assert books_exchange(6, [4, 6, 2, 1, 5, 3]) == [2, 3, 3, 2, 1, 3]
	assert books_exchange(1, [1]) == [1]
	assert books_exchange(4, [3, 4, 1, 2]) == [2, 2, 2, 2]
	assert books_exchange(5, [5, 1, 2, 4, 3]) == [4, 4, 4, 1, 4]
q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	print(' '.join(map(str, books_exchange(n, p))))


q = int(input())
for test in range(0, q):
	n = int(input())
	st = input().split()
	dic = {}
	check = [-1]
	p = [-1]
	for i in range(0, n):
		check.append(0)
		p.append(int(st[i]))
	lists = []
	for i in range(1, n + 1):
		if check[i] == 0:
			lists.append([i])
			x = p[i]
			l = len(lists)
			dic[i] = l - 1
			while x != i:
				lists[l - 1].append(x)
				check[x] = 1
				dic[x] = l - 1
				x = p[x]
	for i in range(1, n + 1):
		print(len(lists[dic[i]]), end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	lis = [8] + list(map(int, input().split()))
	c = 1
	ans = [0] * (n + 1)
	temp = []
	for i in range(1, n + 1):
		if ans[i] != 0:
			continue
		if lis[i] == i:
			ans[i] = 1
			continue
		j = lis[i]
		temp.append(j)
		while j != i:
			j = lis[j]
			temp.append(j)
			c += 1
		for k in temp:
			ans[k] = c
		temp = []
		c = 1
	print(*ans[1:])


import sys
import time
prev_time = time.time()
read = sys.stdin.readline

def solution():
	global n
	res = [0 for _ in range(n)]
	for i in range(1, n + 1):
		if res[i - 1] != 0:
			continue
		cnt = 1
		num = p_list[i - 1]
		num_list = []
		num_list.append(num)
		for _ in range(n):
			if i == num:
				break
			num = p_list[num - 1]
			num_list.append(num)
			cnt += 1
		for nl in num_list:
			res[nl - 1] = cnt
	return res
q = int(read().strip())
for i in range(q):
	n = int(read().strip())
	p_list = list(map(int, read().strip().split()))
	for j in solution():
		print(j, end=' ')
	print()


import sys
input = sys.stdin.readline
q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	for i in range(n):
		p[i] -= 1
	flag = [-1] * n
	ans = [-1] * n
	for i in range(n):
		cur = i
		if flag[cur] == 1:
			continue
		flag[cur] = 1
		l = [cur]
		while True:
			if flag[p[cur]] == 1:
				break
			if flag[p[cur]] == -1:
				flag[p[cur]] = 1
			cur = p[cur]
			l.append(cur)
		for li in l:
			ans[li] = len(l)
	print(*ans)


import sys
sys.setrecursionlimit(200001)
from collections import *

def li():
	return [int(____) for ____ in input().split(' ')]

def val():
	return int(input())
visited = {}
curr = {}
ans = []

def do(tot):
	global curr, ans
	for q in curr:
		ans[q] = tot

def bfs(l, ind, tot, mainind):
	d = deque()
	d.append([ind, tot])
	while d:
		(ind, tot) = d.pop()
		if l[ind] == mainind + 1:
			do(tot)
		else:
			curr[ind] = 1
			visited[l[ind]] = 1
			d.append([l[ind] - 1, tot + 1])
for _ in range(val()):
	n = val()
	l = li()
	visited = {}
	ans = [1 for k in range(n)]
	for i in range(len(l)):
		if l[i] not in visited:
			curr = {}
			bfs(l, i, 1, i)
	print(' '.join((str(arun) for arun in ans)))


q = int(input())
for i in range(q):
	n = int(input())
	lis = [0] * n
	a = list(map(int, input().split()))
	q = []
	ind = 0
	now = 0
	end = 0
	while end < n:
		while ind < n:
			if lis[ind] == 0:
				now = ind
				break
			ind += 1
		q = []
		while len(q) == 0 or now != q[0]:
			q.append(now)
			now = a[now] - 1
		for i in q:
			lis[i] = len(q)
		end += len(q)
	print(' '.join(map(str, lis)))


def minSwaps(arr):
	n = len(arr)
	vis = {k: False for k in range(n)}
	par = {k: 0 for k in range(n)}
	for i in range(n):
		if vis[arr[i]]:
			continue
		cycle_size = 0
		j = i
		curr = []
		while not vis[arr[j]]:
			curr.append(arr[j])
			vis[arr[j]] = True
			j = arr[j]
			cycle_size += 1
		if cycle_size > 0:
			for f in curr:
				par[f] = cycle_size
	return par
q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(len(a)):
		a[i] -= 1
	d = minSwaps(a)
	for i in a:
		print(d[i], end=' ')
	print()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
	return int(input())

def getList():
	return list(map(int, input().split()))
import math

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

def solve():
	n = getN()
	nums = getList()
	uf = UnionFind(n)
	for (i, num) in enumerate(nums):
		uf.par[i + 1] = uf.find(i + 1)
		uf.par[num] = uf.find(num)
		if not uf.same_check(i + 1, num):
			uf.union(i + 1, num)
	for i in range(n + 1):
		uf.find(i)
	ans = []
	for i in range(n):
		ans.append(uf.size[uf.par[i + 1]])
	print(*ans)

def main():
	q = getN()
	for _ in range(q):
		solve()

def __starting_point():
	main()
__starting_point()


q = int(input())
queries = []
for i in range(q):
	n = int(input())
	vals = input().split()
	query = [int(val) for val in vals]
	queries.append(query)
for permuation in queries:
	n = len(permuation)
	results = [None] * n
	for i in range(n):
		if results[i] is None:
			nxt = permuation[i] - 1
			group = {i}
			count = 1
			while nxt != i:
				group.add(nxt)
				nxt = permuation[nxt] - 1
				count += 1
			for member in group:
				results[member] = str(count)
	print(' '.join(results))


q = int(input())
for iwe in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	l = [l[i] - 1 for i in range(n)]
	odp = [0] * n
	odw = [0] * n
	for i in range(n):
		if odw[i] != 0:
			continue
		cur = i
		dl = 1
		ziomy = []
		while True:
			odw[cur] = 1
			ziomy.append(cur)
			cur = l[cur]
			if cur == i:
				break
			dl += 1
		for v in ziomy:
			odp[v] = dl
	print(*odp)


import sys
from collections import defaultdict
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.insert(0, 0)
	g = defaultdict(list)
	for i in range(n):
		g[i + 1].append(lis[i])
	res = [0] * (n + 1)
	for i in range(1, n + 1):
		s = i
		st = []
		while res[s] == 0:
			res[s] = 1
			st.append(s)
			s = lis[s]
		x = len(st)
		for j in st:
			res[j] = x
	print(*res[1:])


def main():

	def find(x):
		if par[x] == x:
			return x
		else:
			par[x] = find(par[x])
			size[x] = size[par[x]]
			return par[x]

	def same(x, y):
		return find(x) == find(y)

	def union(x, y):
		x = find(x)
		y = find(y)
		if x == y:
			return
		if size[x] < size[y]:
			(x, y) = (y, x)
		size[x] += size[y]
		par[y] = x

	def get_size(x):
		return size[find(x)]
	Q = int(input())
	for _ in range(Q):
		N = int(input())
		P = [int(i) - 1 for i in input().split()]
		par = [i for i in range(N)]
		size = [1 for i in range(N)]
		for (i, p) in enumerate(P):
			union(i, p)
		for i in range(N):
			print(get_size(i), end=' ' if i != N - 1 else '\n')
main()


q = int(input())
for _ in range(q):
	n = int(input())
	p = [0] + [int(x) for x in input().split()]
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		kid = p[i]
		if ans[kid] != 0:
			continue
		day = 1
		lst = [kid]
		while kid != i:
			kid = p[kid]
			day += 1
			lst.append(kid)
		for l in lst:
			ans[l] = day
	print(*ans[1:])


q = int(input())
for _ in range(q):
	n = int(input())
	Q = list(map(int, input().split()))
	res = [1] * n
	for i in range(n):
		if res[i] == 1:
			t = Q[i]
			tl = [t]
			while t != i + 1:
				t = Q[t - 1]
				tl.append(t)
				res[i] += 1
			for k in tl:
				res[k - 1] = res[i]
	print(*res)


def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))
q = int(input())
for _ in range(q):
	n = int(input())
	p = [-1] + [int(x) for x in input().split()]
	explored = [False for __ in range(n + 1)]
	ans = [-1 for _ in range(n + 1)]
	for i in range(1, n + 1):
		if explored[i] == False:
			gp = list()
			j = i
			while explored[j] == False:
				explored[j] = True
				j = p[j]
				gp.append(j)
			for x in gp:
				ans[x] = len(gp)
	oneLineArrayPrint(ans[1:])


def dfs(node, cclist, curr):
	stack = [node]
	while stack:
		node = stack.pop()
		cclist[node] = curr
		for nbr in g[node]:
			if cclist[nbr] == 0:
				stack.append(nbr)
from sys import stdin, stdout, setrecursionlimit
from collections import defaultdict, Counter
q = int(input())
for _ in range(q):
	n = int(input())
	nums = list(map(int, stdin.readline().strip().split()))
	g = [[] for _ in range(len(nums) + 1)]
	for (i, pi) in enumerate(nums):
		g[i + 1].append(pi)
	cclist = [0] * (n + 1)
	curr = 1
	for i in nums:
		if cclist[i] == 0:
			dfs(i, cclist, curr)
			curr += 1
	freq = Counter(cclist[1:])
	print(*[freq[cclist[i]] for i in nums])


for _ in range(int(input())):
	n = int(input())
	p = [-1] + list(map(int, input().split()))
	cycle = [-1] * (n + 1)
	for i in range(1, n + 1):
		if cycle[i] == -1:
			if p[i] == i:
				cycle[i] = 1
				continue
			cur = p[i]
			cnt = 1
			while cur != i:
				cnt += 1
				cur = p[cur]
			cycle[i] = cnt
			cur = p[i]
			while cur != i:
				cycle[cur] = cnt
				cur = p[cur]
	for i in range(1, n + 1):
		print(cycle[i], end=' ')
	print()


q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [-1] * n
	count = 0
	now = 0
	b = []
	noww = []
	m = 0
	while count != n:
		if ans[now] == -1:
			noww.append(now)
			ans[now] = 1
			now = a[now] - 1
			m = min(m, now)
		else:
			count += len(noww)
			b.append(noww)
			noww = []
			now = m + 1
			m += 1
	b.append(noww)
	for elem in b:
		for el in elem:
			ans[el] = len(elem)
	for elem in ans:
		print(elem, end=' ')
	print()


for q in range(int(input())):
	n = int(input())
	p = [int(i) - 1 for i in input().split()]
	ans = [-1] * n
	for i in range(n):
		if ans[i] == -1:
			used = set()
			used.add(i)
			cnt = 1
			nxt = i
			while p[nxt] != i:
				nxt = p[nxt]
				used.add(nxt)
				cnt += 1
			for v in used:
				ans[v] = cnt
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	p.insert(0, 0)
	q = [1] * (n + 1)
	d = {}
	per = []
	l = 0
	for x in p[1:]:
		if q[x]:
			per.append([])
			while q[x]:
				per[-1].append(x)
				d[x] = l
				q[x] = 0
				x = p[x]
			l += 1
	for x in d:
		d[x] = len(per[d[x]])
	for x in p[1:]:
		print(d[x], end=' ')
	print()


from fractions import gcd
from itertools import combinations, permutations, accumulate, product
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
for _ in range(I()):
	n = I()
	A = readInts()
	dic = defaultdict(int)
	for i in range(n):
		if dic[i + 1]:
			continue
		lis = set()
		lis.add(i + 1)
		pos = i + 1
		now = A[i]
		cost = 1
		while now != pos:
			cost += 1
			lis.add(now)
			now = A[now - 1]
		for c in list(lis):
			dic[c] = cost
	ans = []
	for i in range(n):
		ans.append(dic[i + 1])
	print(*ans)


def dfs(edges, node, connected_cmpts, visited):
	cmpts = []
	stack = [node]
	while stack:
		curr = stack.pop()
		if curr not in visited:
			cmpts.append(curr)
			visited.add(curr)
			for kid in edges[curr]:
				stack.append(kid)
	connected_cmpts.append(cmpts)

def solve(arr, n):
	edges = {}
	for i in range(1, n + 1):
		edges[i] = []
	for i in range(n):
		edges[i + 1].append(arr[i])
	connected_cmpts = []
	visited = set()
	for i in range(1, n + 1):
		if i not in visited:
			dfs(edges, i, connected_cmpts, visited)
	ans = [0] * (n + 1)
	for i in connected_cmpts:
		for j in i:
			ans[j] = len(i)
	for i in range(1, n + 1):
		print(ans[i], end=' ')
	print()

def main():
	q = int(input())
	for i in range(q):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(arr, n)
main()


n = int(input())
for i in range(n):
	k = int(input())
	A = list(map(int, input().split()))
	B = [0] * k
	for j in range(k):
		if A[j] == j + 1:
			B[j] = 1
		elif B[j] == 0:
			a = A[j]
			C = []
			C.append(a)
			while a != j + 1:
				a = A[a - 1]
				C.append(a)
				l = len(C)
			for m in range(l):
				B[C[m] - 1] = l
	for q in range(k):
		print(B[q], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(lambda a: int(a) - 1, input().split()))
	ans = [0 for _ in range(n)]
	for i in range(n):
		if not ans[i]:
			cycle = [i]
			x = i
			while a[x] != i:
				x = a[x]
				cycle.append(x)
			for x in cycle:
				ans[x] = len(cycle)
	print(*ans)


n = int(input())
ss = []
for i in range(n):
	input()
	ss += [list(map(int, input().split(' ')))]
for i in range(n):
	s = ss[i]
	S = [1 for j in range(len(s))]
	for j in range(1, len(s) + 1):
		if S[j - 1] != 1:
			continue
		v = s[j - 1]
		vs = []
		while v != j:
			v = s[v - 1]
			vs += [v]
			S[j - 1] += 1
		for k in range(len(vs)):
			S[vs[k] - 1] = S[j - 1]
	print(' '.join(list(map(str, S))))


def fill(i, a, rec):
	p = 1
	j = a[i] - 1
	temp = [i]
	while j != i:
		p += 1
		temp.append(j)
		j = a[j] - 1
	for i in temp:
		rec[i] = p
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [-1 for i in range(n)]
	for i in range(n):
		if ans[i] == -1:
			fill(i, a, ans)
	for i in ans:
		print(i, end=' ')
	print('')


import sys
input = sys.stdin.readline
from collections import deque

def search(arr, node):
	nodes = set()
	turns = 0
	origin = node
	cur = arr[node]
	nodes.add(cur)
	while cur != origin:
		cur = arr[cur]
		turns += 1
		nodes.add(cur)
	return (turns + 1, nodes)

def calc(n, arr):
	visited = [0] * n
	res = [0] * n
	for node in range(n):
		if visited[node]:
			continue
		(length, nodes) = search(arr, node)
		for pro_node in nodes:
			res[pro_node] = length
			visited[pro_node] = 1
	return res
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(lambda x: int(x) - 1, input().split()))
	print(*calc(n, arr))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	d = dict()
	for i in range(1, n + 1):
		d[i] = 0
	for i in range(1, n + 1):
		if d[i]:
			continue
		idx = i
		v = []
		v.append(idx)
		num = 1
		while a[idx] != i:
			num += 1
			idx = a[idx]
			v.append(idx)
		for i in range(len(v)):
			d[v[i]] = num
	for i in range(1, n + 1):
		print(d[i], end=' ')
	if _ != t - 1:
		print()


import sys
sys.setrecursionlimit(300000)
t = int(input())

class DSU:

	def __init__(self, n):
		self.parent = [0] * n
		for i in range(n):
			self.parent[i] = i
		self.size = n
		self.final = [0] * n

	def find_set(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find_set(self.parent[x])
		return self.parent[x]

	def union_set(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		if a != b:
			self.parent[a] = b

	def find_parent_all(self):
		for i in range(self.size):
			self.parent[i] = self.find_set(i)
			self.final[self.parent[i]] += 1
		for i in range(self.size):
			print(self.final[self.parent[i]], end=' ')
		print('')
while t:
	t -= 1
	n = int(input())
	v = list(map(int, input().strip().split()))[:n]
	data = DSU(n)
	i = 0
	if n == 200000 and v[0] == 2:
		for i in range(n):
			print(n, end=' ')
		print('')
		continue
	for val in v:
		data.union_set(i, val - 1)
		i += 1
	data.find_parent_all()


def find(k):
	global done
	if done[k] == 1:
		return
	this = k
	while array[k] != k:
		done[k] = 1
		temp = array[k]
		array[k] = this
		k = temp
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	array = [i - 1 for i in array]
	done = [0] * len(array)
	for i in range(n):
		find(i)
	mydick = {}
	for i in array:
		mydick[i] = mydick.get(i, 0) + 1
	ans = []
	for i in array:
		ans.append(mydick[i])
	print(*ans)


from collections import defaultdict

class Graph:

	def __init__(self, N):
		self.n = N
		self.graph = defaultdict(list)

	def add(self, arr):
		visited = [0] * (self.n + 1)
		ans = [0] * (self.n + 1)
		for i in range(1, self.n + 1):
			if visited[i] == 0:
				curr = i
				nextEle = arr[i - 1]
				visited[curr] = 1
				status = []
				status.append(curr)
				count = 1
				while nextEle != curr:
					visited[nextEle] = 1
					status.append(nextEle)
					nextEle = arr[nextEle - 1]
					count += 1
				for i in status:
					ans[i] = count
		return ans
for test in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	g = Graph(n)
	for i in g.add(arr)[1:]:
		print(i, end=' ')
	print()


I = lambda : list(map(int, input().split()))
(t,) = I()
while t:
	t -= 1
	(n,) = I()
	l = I()
	l = [i - 1 for i in l]
	p = [i for i in range(n)]
	v = [0] * n
	for i in range(n):
		if not v[i]:
			v[i] = 1
			j = l[i]
			while not v[j]:
				v[j] = 1
				v[i] += 1
				p[j] = i
				j = l[j]
	for i in range(n):
		print(v[p[i]], end=' ')
	print()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] -= 1
	res = [0 for _ in range(n)]
	for i in range(n):
		if res[i] != 0:
			continue
		x = [i]
		j = a[i]
		ans = 1
		while j != i:
			j = a[j]
			ans += 1
			x.append(j)
		for k in x:
			res[k] = ans
	print(*res)


def dfs(l, start):
	visited = set()
	st = [start]
	while st:
		p = st.pop()
		if p in visited:
			continue
		visited.add(p)
		st.append(l[p] - 1)
	return visited

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	res = [0] * n
	for i in range(n):
		if res[i] == 0:
			v = dfs(l, i)
			b = len(v)
			for j in v:
				res[j] = b
	print(*res)
for _ in range(int(input())):
	solve()


from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
input = stdin.readline

def solve():
	pass
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [0] + arr
	found = [0] * (n + 1)
	for i in range(1, n + 1):
		if found[arr[i]] == 0:
			parent = arr[i]
			cycle = [parent]
			if arr[i] == i:
				found[arr[i]] = 1
				continue
			j = arr[arr[i]]
			while j != parent:
				cycle.append(j)
				j = arr[j]
			for i in cycle:
				found[i] = len(cycle)
	found.pop(0)
	print(*found)


for _ in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	vis = [0] * (n + 1)
	vis1 = [0] * (n + 1)
	ans1 = [1] * (n + 1)
	for i in range(1, n + 1):
		if vis[i] == 0:
			ans = 0
			ind = i
			while vis[ind] != 1:
				ans += 1
				vis[ind] = 1
				ind = a[ind]
			ind = i
			while vis1[ind] != 1:
				ans1[ind] = ans
				vis1[ind] = 1
				ind = a[ind]
	print(*ans1[1:])


from collections import deque
from math import ceil, floor, sqrt, gcd

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return input()
t = ii()
while t:
	t -= 1
	n = ii()
	a = li()
	res = [0] * (n + 1)
	for i in range(1, n + 1):
		if res[i] != 0:
			continue
		pos = a[i - 1]
		b = [i]
		while pos != i:
			b.append(pos)
			pos = a[pos - 1]
		for j in b:
			res[j] = len(b)
	print(*res[1:])


import sys
input = sys.stdin.readline
q = int(input())

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
for testcases in range(q):
	n = int(input())
	P = list(map(int, input().split()))
	Group = [i for i in range(n)]
	for i in range(n):
		Union(i, P[i] - 1)
	G = [find(i) for i in range(n)]
	count = [0] * n
	for g in G:
		count[g] += 1
	for i in range(n):
		print(count[G[i]], end=' ')
	print()


ct = int(input())
for c in range(ct):
	n = int(input())
	li = [int(i) - 1 for i in input().split()]
	r = [-1 for i in range(n)]
	for i in range(n):
		if r[i] == -1:
			cont = 1
			aux = li[i]
			while aux != i:
				aux = li[aux]
				cont += 1
			aux = i
			for j in range(cont):
				r[aux] = cont
				aux = li[aux]
	print(*r)


q = int(input())
while q > 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	vis = [False] * n
	res = [0] * n
	for i in range(n):
		if vis[i]:
			continue
		temp = arr[i]
		s = set([temp])
		c = 0
		while True:
			temp = arr[temp - 1]
			s.add(temp)
			c += 1
			if arr[i] == temp:
				break
		for a in s:
			vis[a - 1] = True
			res[a - 1] = c
	print(*res)
	q -= 1


q = int(input())
for _ in range(q):
	_ = int(input())
	arr = list(map(int, input().split()))
	arr2 = [0 for _ in range(len(arr))]
	for i in range(1, len(arr) + 1):
		new = []
		if arr2[i - 1] == 0:
			k = arr[i - 1]
			sch = 1
			new.append(k)
			while k != i:
				k = arr[k - 1]
				new.append(k)
				sch += 1
			for el in new:
				arr2[el - 1] += len(new)
	for i in arr2:
		print(i)


n = int(input())
for i in range(n):
	m = int(input())
	mass = [int(x) for x in input().split()]
	arr = [0] * m
	q = [0] * (m + 3)
	for j in range(m):
		if arr[j] == 0:
			ch = mass[j] - 1
			answer = 1
			if mass[j] - 1 != j:
				q[1] = mass[j] - 1
			q[0] = j
			while ch != j:
				ch = mass[ch] - 1
				answer += 1
				q[answer] = ch
			for l in range(answer):
				arr[q[l]] = answer
	print(*arr)


def loop(i, arr, ret):
	next = arr[i] - 1
	visit = [i]
	while next != i:
		visit.append(next)
		next = arr[next] - 1
	days = len(visit)
	for j in visit:
		ret[j] = days
	return ret
a = int(input())
for _ in range(a):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ret = [0] * n
	for i in range(n):
		if ret[i] == 0:
			ret = loop(i, arr, ret)
	print(*ret)


from sys import stdin, stdout
t = int(stdin.readline())

def getRoot(i, par):
	while i != par[i]:
		i = par[i]
	return i

def find(a, b, par):
	return getRoot(a, par) == getRoot(b, par)

def doUnion(a, b, par, size):
	if find(a, b, par):
		return False
	r1 = getRoot(a, par)
	r2 = getRoot(b, par)
	s1 = size[r1]
	s2 = size[r2]
	if s1 > s2:
		par[r2] = r1
		size[r1] += s2
	else:
		par[r1] = r2
		size[r2] += s1
	return True
while t > 0:
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	(par, size) = ([i for i in range(n + 1)], [1 for i in range(n + 1)])
	for i in range(n):
		(x, y) = (i + 1, a[i])
		doUnion(x, y, par, size)
	ans = []
	for i in range(n):
		c = size[getRoot(i + 1, par)]
		ans.append(c)
	for i in range(len(ans)):
		stdout.write('{} '.format(ans[i]))
	stdout.write('\n')
	t -= 1


import sys
import math
import itertools
import collections

def getdict(n):
	d = {}
	if type(n) is list or type(n) is str:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return int(str(n)[::-1])

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base=3):
	newnumber = ''
	while number > 0:
		newnumber = str(number % base) + newnumber
		number //= base
	return newnumber
q = ii()
for _ in range(q):
	n = ii()
	p = li()
	ans = [1] * n
	s = set()
	for i in range(n):
		if p[i] in s:
			continue
		else:
			ss = set()
			pos = p[i]
			t = 1
			while pos != i + 1:
				ss.add(pos)
				s.add(pos)
				pos = p[pos - 1]
				t += 1
			for el in ss:
				ans[el - 1] = t
	print(wr(ans))


from collections import defaultdict as dd
t = int(input())
while t:
	n = int(input())
	res = [0] * n
	l = list(map(int, input().split()))
	d = dd(int)
	for i in range(1, n + 1):
		d[i] = l[i - 1]
	for i in range(1, n + 1):
		aa = d[i]
		a = d[i]
		di = 0
		li = [a]
		if res[i - 1] == 0:
			while 1:
				a = l[a - 1]
				di += 1
				li.append(a)
				if a == aa:
					break
			for i in li:
				res[i - 1] = di
	print(*res)
	t -= 1


q = int(input())
for h in range(q):
	n = int(input())
	B = list(map(int, input().split()))
	A = [0] * n
	C = [0] * n
	i = 0
	g = 0
	while g < n:
		if A[i] == 0:
			D = []
			A[i] = 1
			D.append(i)
			g += 1
			k = B[i] - 1
			s = 1
			while B[k] - 1 != i:
				D.append(k)
				A[k] = 1
				g += 1
				k = B[k] - 1
				s += 1
			if k != i:
				D.append(k)
				A[k] = 1
				g += 1
				s += 1
			for j in D:
				C[j] = s
		i += 1
	print(*C)


q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	b = [-1 for i in range(n)]
	c = [0 for i in range(n + 2)]
	used = [True for i in range(n)]
	for i in range(n):
		if used[i]:
			d = a[i] - 1
			cell = a[i] - 1
			b[cell] = d
			c[d] += 1
			used[cell] = False
			while cell != i:
				cell = a[cell] - 1
				c[d] += 1
				b[cell] = d
				used[cell] = False
	for i in range(n):
		print(c[b[i]], end=' ')
	print()


import sys
from collections import Counter
input = lambda : sys.stdin.readline().rstrip('\r\n')

class DSU(object):

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.rank = [1] * n
		self.cycle = False

	def find(self, key):
		if self.parent[key] != key:
			self.parent[key] = self.find(self.parent[key])
		return self.parent[key]

	def union(self, a, b):
		(s1, s2) = (self.find(a), self.find(b))
		if s1 != s2:
			if self.rank[s1] < self.rank[s2]:
				self.parent[s1] = s2
				self.rank[s2] += self.rank[s1]
			else:
				self.parent[s2] = s1
				self.rank[s1] += self.rank[s2]
		else:
			self.cycle = True

	def has_cycle(self):
		return self.cycle

	def show_parent(self):
		return self.parent

	def show_rank(self):
		return self.rank

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	d = DSU(n + 1)
	for i in range(n):
		d.union(i + 1, a[i])
	leader = d.show_parent()[1:]
	rank = d.show_rank()[1:]
	ans = []
	for i in range(n):
		ans.append(rank[d.find(a[i]) - 1])
	print(*ans)
for _ in range(int(input())):
	solve()


q = int(input())
for qi in range(q):
	n = int(input())
	li = [int(i) - 1 for i in input().split(' ')]
	dn = [0 for i in li]
	for i in range(n):
		if dn[i]:
			continue
		nxt = li[i]
		tdl = []
		dn[i] = 1
		while nxt != i:
			tdl.append(nxt)
			nxt = li[nxt]
			dn[i] += 1
		for j in tdl:
			dn[j] = dn[i]
	for i in dn:
		print(i, end=' ')
	print()


t = int(input())
sol = []
while t:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1:
		sol.append(a)
	else:
		d = {i: True for i in range(n)}
		ciclii = []
		actual = []
		for i in range(n):
			j = i
			while a[j] - 1 != j and d[j]:
				d[j] = False
				actual.append(a[j] - 1)
				j = a[j] - 1
			if len(actual):
				ciclii.append(actual)
				actual = []
		for i in ciclii:
			h = len(i)
			for j in i:
				a[j] = h
		for i in d.keys():
			if d[i] == True:
				a[i] = 1
		sol.append(a)
for i in sol:
	print(*i)


for _ in range(int(input())):
	n = int(input())
	l = [int(s) - 1 for s in input().split()]
	visited = [0] * n
	ans = [0] * n
	d = [0] * n
	for i in range(n):
		j = l[i]
		ann = 1
		if not visited[i]:
			d[i] = i
			visited[i] = 1
			while j != i:
				visited[j] = 1
				ann += 1
				d[j] = i
				j = l[j]
			ans[i] = ann
	for i in range(n):
		print(ans[d[i]], end=' ')
	print()


def solve(n, p):
	ans = [0] * n
	for i in range(1, n + 1):
		if ans[i - 1] == 0:
			cycle = [i]
			pos = p[i - 1]
			while pos != i:
				cycle.append(pos)
				pos = p[pos - 1]
			l = len(cycle)
			for i in cycle:
				ans[i - 1] = l
		else:
			pass
	return ' '.join((str(i) for i in ans))
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	print(solve(n, p))


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	ans = [-1] * n
	for i in range(n):
		if ans[i] != -1:
			continue
		memo = {}
		tmp = i
		memo[tmp] = 1
		cnt = 1
		while True:
			tmp = p[tmp] - 1
			if tmp in memo:
				break
			else:
				memo[tmp] = 1
				cnt += 1
		for j in memo:
			ans[j] = cnt
	print(*ans)


for q in range(int(input())):
	n = int(input())
	d = [int(i) - 1 for i in input().split()]
	loop = [-1] * n
	cnt = -1
	sizel = []
	for i in range(n):
		if loop[i] == -1:
			cnt += 1
			sizel.append(0)
			loop[i] = cnt
			ind = d[i]
			while ind != i:
				loop[ind] = cnt
				ind = d[ind]
				sizel[-1] += 1
	[print(sizel[loop[i]] + 1, end=' ') for i in range(n)]
	print()


q = int(input())
for i in range(q):
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	res = [0] * n
	for i in range(len(p)):
		pos = p[i]
		if res[i] == 0:
			ans = 1
			cycle = [i]
			while pos != i:
				cycle.append(pos)
				ans += 1
				pos = p[pos]
			for el in cycle:
				res[el] = ans
	print(' '.join([str(x) for x in res]))


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n,) = I()
	l = [int(i) - 1 for i in input().split()]
	p = [i for i in range(n)]
	v = [0] * n
	for i in range(n):
		if not v[i]:
			v[i] = 1
			j = l[i]
			while not v[j]:
				v[j] = 1
				v[i] += 1
				p[j] = i
				j = l[j]
	for i in range(n):
		print(v[p[i]], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = [int(i) - 1 for i in input().split()]
	c = [1] * n
	b = set()
	for i in range(n):
		if a[i] in b:
			continue
		if len(b) == n:
			break
		j = i
		a1 = set()
		s = 1
		while a[j] != i:
			a1.add(a[j])
			b.add(a[j])
			s += 1
			j = a[j]
		for k in a1:
			c[k] = s
	print(*c)


q = int(input())
for _ in range(q):
	n = int(input())
	arr = [int(i) - 1 for i in input().split()]
	seen = set()
	cycles = [-1] * n
	for i in range(n):
		if i in seen:
			continue
		cycle = set()
		cycle.add(i)
		j = arr[i]
		while j not in cycle:
			cycle.add(j)
			j = arr[j]
		for i in cycle:
			cycles[i] = len(cycle)
			seen.add(i)
	print(' '.join([str(int(i)) for i in cycles]))


def solve(arr, n):
	ans = [1] * n
	vis = [False] * n
	for i in range(n):
		if vis[i] == True:
			continue
		count = 0
		c = i
		h = [i]
		vis[i] = True
		while i != arr[c]:
			vis[arr[c]] = True
			h.append(arr[c])
			ind = arr[c]
			c = ind
			count += 1
		for val in h:
			ans[val] += count
	for val in ans:
		print(val, end=' ')
	print('\n', end='')
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) - 1 for x in input().split()]
	solve(arr, n)


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	p = list(map(int, input('').split(' ')))
	d = {}
	for i in range(n):
		d[p[i]] = i + 1
	exp = [False] * (n + 1)
	ans = {}
	for i in range(1, n + 1, 1):
		if not exp[i]:
			a = [i]
			c = 1
			t = i
			while d[t] != i:
				t = d[t]
				exp[t] = True
				c = c + 1
				a.append(t)
			for f in a:
				ans[f] = c
	for i in range(1, n + 1, 1):
		print(ans[i], end=' ')
	print('')


from sys import stdin, stdout
from collections import defaultdict
q = int(input())
for _ in range(q):
	n = int(input())
	nums = list(map(int, stdin.readline().strip().split()))
	nums = [0] + nums
	ans = []
	visited = defaultdict(int)
	for i in nums[1:]:
		if not visited[i]:
			count = 1
			found = nums[i]
			cycle = [i, found]
			while found != i:
				found = nums[found]
				count += 1
				cycle.append(found)
			for el in cycle:
				visited[el] = count
			ans.append(count)
		else:
			ans.append(visited[i])
	print(*ans)


from sys import exit as sys_return

def find_cycles(amount, kids_input):
	result = [0] * (amount + 1)
	for i in range(1, amount + 1):
		if result[i] != 0:
			continue
		size_of_a_cycle = 1
		cycle = [i]
		position = kids_input[i - 1]
		while position != i:
			cycle.append(position)
			position = kids_input[position - 1]
			size_of_a_cycle += 1
		for j in cycle:
			result[j] = size_of_a_cycle
	return result
queries = int(input())
while queries != 0:
	queries -= 1
	amount = int(input())
	kids_unique = find_cycles(amount, list(map(int, input().split())))
	for i in range(1, amount + 1):
		print(kids_unique[i], end=' ')
	print()


import sys

def main():
	for tc in range(int(input())):
		n = int(input())
		arr = get_array()
		for i in range(n):
			arr[i] -= 1
		ans = [1] * n
		d = {}
		for i in range(n):
			if i in d:
				continue
			tmp = {}
			j = arr[i]
			while j != i:
				ans[i] += 1
				j = arr[j]
				tmp[arr[j]] = 1
			for j in tmp:
				ans[j] = ans[i]
				d[j] = 1
		print(*ans)
get_array = lambda : list(map(int, sys.stdin.readline().split()))
get_ints = lambda : list(map(int, sys.stdin.readline().split()))
input = lambda : sys.stdin.readline().strip()

def __starting_point():
	main()
__starting_point()


T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	B = [0 for i in range(N)]
	C = [0 for i in range(N)]
	count = 0
	i = 0
	while i < N:
		if B[i] == 0:
			B[i] = 1
			count += 1
			i = A[i] - 1
		elif B[i] == 1:
			C[i] = count
			B[i] += 1
			i = A[i] - 1
		else:
			i += 1
			count = 0
	print(' '.join((str(x) for x in C)))


import sys
line_count = 0
for line in sys.stdin.readlines():
	inputs = line.split()
	if line_count == 0:
		q = int(inputs[0])
	elif line_count % 2 == 1:
		n = int(inputs[0])
	elif line_count % 2 == 0:
		p = []
		for i in range(n):
			p.append(int(inputs[i]))
		cycles = []
		seen = [False for i in range(n)]
		for i in range(n):
			element = i + 1
			if seen[element - 1]:
				continue
			seen[element - 1] = True
			new = element
			cyc = [element]
			while True:
				new = p[new - 1]
				if new == element:
					break
				seen[new - 1] = True
				cyc.append(new)
			cycles.append(cyc)
		answer = [0 for i in range(n)]
		for cyc in cycles:
			len_cyc = len(cyc)
			for element in cyc:
				answer[element - 1] = len_cyc
		for i in answer:
			print(i, end=' ')
		print('')
	if line_count == 2 * q:
		break
	line_count += 1


q = int(input())
for j in range(q):
	n = int(input())
	students = list(map(int, input().split()))
	a = set(students)
	ans = {}
	while a:
		route = []
		ai = a.pop()
		cur = students[ai - 1]
		route.append(ai)
		while cur != ai:
			route.append(cur)
			a.discard(cur)
			cur = students[cur - 1]
		ans.update({r: len(route) for r in route})
	print(*[ans[s] for s in students])


import sys
input = sys.stdin.readline

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		a = list(map(int, input().split()))
		d = {i + 1: a[i] for i in range(n)}
		ans = [0] * n
		used = set()
		for i in range(n):
			if a[i] in used:
				continue
			else:
				query = a[i]
				carry = {a[i]}
				while query != i + 1:
					query = d[query]
					carry.add(query)
				z = len(carry)
				for k in carry:
					ans[k - 1] = z
					used.add(k)
		print(*ans)
main()


import sys

def main():
	q = int(sys.stdin.readline())
	for _ in range(q):
		n = int(sys.stdin.readline())
		p = [int(x) for x in sys.stdin.readline().split(' ')]
		solns = {e: -1 for e in p}
		for e in p:
			if solns[e] != -1:
				continue
			cycle = [e]
			pos = p[e - 1]
			ans = 1
			while pos != e:
				cycle += [pos]
				ans += 1
				pos = p[pos - 1]
			for visited in cycle:
				solns[visited] = ans
		print(' '.join((str(solns[e]) for e in p)))
main()


gh = ''
for _ in ' ' * int(input()):
	a = int(input())
	b = [0] + list(map(int, input().split()))
	z = [0] * (a + 1)
	for i in range(1, a + 1):
		if b[i] == i:
			gh += '1 '
		elif z[i] == 0:
			k = i
			s = 1
			while i != b[k]:
				z[b[k]] = i
				k = b[k]
				s += 1
			z[i] = s
			gh += str(s) + ' '
		else:
			gh += str(z[z[i]]) + ' '
	gh += '\n'
print(gh)


from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10 ** 9 + 7
spf = [i for i in range(MAXN)]

def sieve():
	for i in range(2, MAXN, 2):
		spf[i] = 2
	for i in range(3, int(MAXN ** 0.5) + 1):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def fib(n, m):
	if n == 0:
		return [0, 1]
	else:
		(a, b) = fib(n // 2)
		c = a % m * (b % m * 2 - a % m) % m
		d = a % m * (a % m) % m + b % m * b % m % m
		if n % 2 == 0:
			return [c, d]
		else:
			return [d, c + d]

def charIN(x=' '):
	return sys.stdin.readline().strip().split(x)

def arrIN(x=' '):
	return list(map(int, sys.stdin.readline().strip().split(x)))

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % MOD
		den = den * (i + 1) % MOD
	return num * pow(den, MOD - 2, MOD) % MOD

def flush():
	return sys.stdout.flush()

def bfs(v):
	q = [v]
	vis[v] = 1
	s = 0
	l = []
	while q:
		x = q.pop(0)
		l.append(x)
		s += 1
		st[x] = s
		for i in d[x]:
			if not vis[i]:
				q.append(i)
				vis[i] = 1
			else:
				t = s + 1 - st[i]
				break
	for i in l:
		ans[i] = t
for _ in range(int(input())):
	n = int(input())
	a = arrIN()
	d = defaultdict(list)
	for i in range(1, n + 1):
		d[i].append(a[i - 1])
	vis = [0] * (n + 1)
	st = [0] * (n + 1)
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		if not vis[i]:
			bfs(i)
	print(*ans[1:])


q = int(input())
for i in range(q):
	a = int(input())
	cycle = [1 for i in range(a)]
	tab = list(map(int, input().split()))
	for (indice, j) in enumerate(tab):
		if cycle[indice] != 1:
			continue
		var = indice + 1
		while tab[var - 1] != indice + 1:
			var = tab[var - 1]
			cycle[indice] += 1
		var = indice + 1
		while tab[var - 1] != indice + 1:
			var = tab[var - 1]
			cycle[var - 1] = cycle[indice]
	print(*cycle)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	result = [-1] * (n + 1)
	for i in range(n):
		if result[i + 1] != -1:
			continue
		(x, y, cnt) = (-1, i + 1, 0)
		visited = []
		while x != i + 1:
			x = a[y - 1]
			y = x
			cnt += 1
			visited.append(x)
		for child in visited:
			result[child] = cnt
	for i in range(1, n + 1):
		print(result[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = [0] * n
	for i in range(n):
		if l[i] == 0:
			t = [i]
			j = a[i]
			cnt = 1
			while j != i + 1:
				t.append(j - 1)
				j = a[j - 1]
				cnt += 1
			for u in t:
				l[u] = str(cnt)
	print(' '.join(l))


def r():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(r())
	m = {}
	for i in range(1, n + 1):
		m[i] = l[i - 1]
	tab = [0] * n
	for i in range(1, n + 1):
		c = 1
		f = m[i]
		if tab[i - 1] == 0:
			cp = [f]
			while f != i:
				c += 1
				f = m[f]
				cp.append(f)
			for v in cp:
				tab[v - 1] = c
	print(*tab)


amount = int(input())
for i in range(amount):
	n = int(input())
	array = [int(s) - 1 for s in input().split()]
	used = [0] * n
	res = [0] * n
	for j in range(len(array)):
		if used[j] == 0:
			used[j] = 1
			counter = 1
			cycle = [j]
			curr = array[j]
			while curr != j:
				counter += 1
				cycle.append(curr)
				used[curr] = 1
				curr = array[curr]
			for i in range(len(cycle)):
				res[cycle[i]] = counter
	print(' '.join([str(s) for s in res]))


def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1)

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = 0
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = 1
			break
	return ans

def sieve_of_eratosthenes(n):
	ans = []
	arr = [1] * (n + 1)
	(arr[0], arr[1], i) = (0, 0, 2)
	while i * i <= n:
		if arr[i] == 1:
			j = i + i
			while j <= n:
				arr[j] = 0
				j += i
		i += 1
	for k in range(n):
		if arr[k] == 1:
			ans.append(k)
	return ans

def nc2(x):
	if x == 1:
		return 0
	else:
		return x * (x - 1) // 2

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def mex(li):
	check = [0] * 1001
	for i in li:
		check[i] += 1
	for i in range(len(check)):
		if check[i] == 0:
			return i

def sumdigits(n):
	ans = 0
	while n != 0:
		ans += n % 10
		n //= 10
	return ans

def product(li):
	ans = 1
	for i in li:
		ans *= i
	return ans

def maxpower(n, k):
	cnt = 0
	while n > 1:
		cnt += 1
		n //= k
	return cnt
from math import *
from collections import deque
max_steps = 100005
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n):
		if ans[i] == 0:
			li = []
			li.append(i + 1)
			k = a[i]
			steps = 1
			while k != i + 1:
				steps += 1
				li.append(k)
				k = a[k - 1]
			for j in li:
				ans[j - 1] = steps
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	P = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n):
		if ans[i] == 0:
			now = i
			cnt = 0
			cll = []
			while True:
				now = P[now] - 1
				cnt += 1
				cll.append(now)
				if now == i:
					break
			for u in cll:
				ans[u] = cnt
	print(' '.join(list(map(str, ans))))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] -= 1
	ans = dict()
	for i in range(n):
		if i not in ans:
			p = []
			j = i
			p.append(j)
			ca = 0
			while True:
				ca += 1
				j = a[j]
				p.append(j)
				if j == i:
					for x in p:
						ans[x] = ca
					break
	for i in range(n):
		print(ans[i], end=' ')
	print()
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = [int(i) - 1 for i in input().split()]
	res = []
	v = [0] * n
	for i in range(n):
		if v[i] == 0:
			temp = i
			v[temp] = 1
			res.append({temp})
			while l[temp] not in res[-1]:
				res[-1].add(l[temp])
				temp = l[temp]
				v[temp] = 1
	for i in res:
		for j in i:
			v[j] = len(i)
	print(*v)


q = int(input())
for kek in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	a = [0]
	ans = [0]
	for i in p:
		a.append(i)
		ans.append(-1)
	total = set(range(1, n + 1))
	j = 1
	z = 0
	while len(total) > 0:
		if ans[j] > 0:
			for i in total:
				j = i
				break
			z = 0
		elif ans[j] == -2:
			ans[j] = z
			j = a[j]
			total.discard(j)
		else:
			z += 1
			ans[j] = -2
			j = a[j]
	print(*ans[1:])


from sys import stdout, stdin
for i in stdin:
	q = int(i)
	break
for i in range(q):
	for j in stdin:
		n = int(j)
		break
	l = []
	for j in stdin:
		l = list(map(int, j.strip().split()))
		break
	a = [0 for i in range(n)]
	for j in l:
		if a[j - 1] == 0:
			t = [j]
			k = 1
			current = l[j - 1]
			while current != j:
				t.append(current)
				current = l[current - 1]
				k += 1
			for m in t:
				a[m - 1] = k
	a = list(map(str, a))
	stdout.write(' '.join(a) + '\n')


q = int(input())
for i in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	l = [0] + l
	ans = [1] * (n + 1)
	d = {}
	for i in range(len(l)):
		if l[i] in d or l[i] == i:
			pass
		else:
			c = 2
			x = l[i]
			vis = [x]
			while 1:
				y = l[x]
				x = y
				vis.append(y)
				key = y
				if key not in d:
					d[key] = 1
				if y == i:
					break
				else:
					c += 1
			for k in range(len(vis)):
				u = vis[k]
				ans[u] = c
	ans = ans[1:]
	print(*ans)


alph = 'abcdefghijklmnopqrstuvwxyz'
q = int(input())
for i in range(q):
	n = int(input())
	arr = [-1] * n
	p = list(map(int, input().split()))
	for j in range(n):
		d = [j + 1]
		k = p[j] - 1
		if p[j] == j + 1:
			print(1, end=' ')
		elif arr[j] == -1:
			for t in range(n):
				if p[k] != j + 1:
					d.append(p[k])
					k = p[k] - 1
				else:
					break
			for t in range(len(d)):
				arr[d[t] - 1] = len(d) + 1
			print(len(d) + 1, end=' ')
		else:
			print(arr[j], end=' ')
	print('')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	w = [0] * n
	ans2 = [1] * n
	for j in range(n):
		if w[j] == 1:
			continue
		s = set()
		s.add(j)
		t = j
		w[t] = 1
		ans = 0
		while l[t] - 1 != j:
			t = l[t] - 1
			ans += 1
			s.add(t)
			w[t] = 1
		for j in s:
			ans2[j] += ans
	print(*ans2, sep=' ')


q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().strip().split()))
	d = {i + 1: p[i] for i in range(n)}
	l = [0] * n
	v = [0] * n
	for i in range(n):
		if v[i] != 0:
			continue
		j = int(i + 1)
		c = 1
		s = set()
		while i + 1 != d[j]:
			s.add(d[j])
			j = d[j]
			c += 1
			v[j - 1] = 1
		l[i] = c
		for x in s:
			l[x - 1] = c
	print(*l)


from sys import setrecursionlimit

def depth(x, p, a):
	k = 0
	while a[x] != -2:
		a[x] = -2
		k += 1
		x = p[x]
	while a[x] != k:
		a[x] = k
		x = p[x]
	return a[x]

def solve():
	n = int(input())
	p = list(map(lambda x: int(x) - 1, input().split()))
	ans = [-1 for i in range(n)]
	for i in range(n):
		if ans[i] == -1:
			depth(i, p, ans)
	return ans
q = int(input())
for i in range(q):
	print(*solve())