CodeEff/ECCO huggingface dataset:
# Original solution
N=int(eval(input()))
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100010
for i in range(1,100010):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print((l2[N]))

# Optimized solution
N=int(eval(input()))
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

for i in range(1,100001):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print((l2[N]))
# Original solution
N=int(eval(input()))
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

for i in range(1,100001):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn
print((l2[N]))

# Optimized solution
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
l2=[0]*100001

N=int(eval(input()))

for i in range(1,N+1):
  mn=100000000000000000
  for x in l:
    if i-x>=0 and l2[i-x]<mn:
      mn=l2[i-x]+1
  l2[i]=mn

print((l2[N]))
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    amt = [1]
    a = 6
    while a <= N:
        amt.append(a)
        a *= 6
    a = 9
    while a <= N:
        amt.append(a)
        a *= 9

    dp = [INF] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        for a in amt:
            if i >= a and dp[i] > dp[i - a]:
                dp[i] = dp[i - a] + 1

    print((dp[N]))

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def f(n, a):
    ans = 0
    while n > 0:
        ans += n % a
        n //= a
    return ans


def main():
    N = int(readline())

    ans = INF
    for i in range(N + 1):
        ans = min(ans, f(i, 6) + f(N - i, 9))

    print(ans)
    return


if __name__ == '__main__':
    main()
# Original solution
import sys
readline = sys.stdin.readline
from math import floor, log

def main():
    N = int(readline())
    dp = [i for i in range(N+1)]
    for i in range(N):
        dp[i+1] = min(dp[i+1], dp[i]+1)
        log9 = floor(log(N-i, 9))
        for e in range(1, log9+2):
            if i + 9**e <= N:
	            dp[i+9**e] = min(dp[i+9**e], dp[i]+1)
        log6 = floor(log(N-i, 6))
        for e in range(1, log6+2):
            if i + 6**e <= N:
            	dp[i+6**e] = min(dp[i+6**e], dp[i]+1)
    
    print((dp[N]))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    dp = [i for i in range(N+1)]

    for i in range(N):
        dp[i+1] = min(dp[i+1], dp[i]+1)
        e = 9
        while i + e <= N:
            dp[i+e] = min(dp[i+e], dp[i]+1)
            e *= 9
        e = 6
        while i + e <= N:
            dp[i+e] = min(dp[i+e], dp[i]+1)
            e *= 6

    print((dp[N]))


if __name__ == '__main__':
    main()
# Original solution
n=int(eval(input()))

dp=[0]*(n+1)
for i in range(1,n+1):
    ans=dp[i-1]+1
    j=1
    while i>=6**j:
        ans=min(ans,dp[i-6**j]+1)
        j+=1
    j=1
    while i>=9**j:
        ans=min(ans,dp[i-9**j]+1)
        j+=1
    dp[i]=ans
  
print(ans)


# Optimized solution
n=int(eval(input()))

l=[1]
l_9=[pow(9,i) for i in range(1,7)]
l_6=[pow(6,i) for i in range(1,8)]
l+=l_9
l+=l_6
l.sort(reverse=True)
dp=[10**9 for i in range(n+1)]

dp[0]=0

for i in range(1,n+1):
    for j in l:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
print((dp[n]))
# Original solution
n=int(eval(input()))

l=[1]
l_9=[pow(9,i) for i in range(1,7)]
l_6=[pow(6,i) for i in range(1,8)]
l+=l_9
l+=l_6
l.sort(reverse=True)
dp=[10**9 for i in range(n+1)]

dp[0]=0

for i in range(1,n+1):
    for j in l:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
print((dp[n]))

# Optimized solution
n=int(eval(input()))
m=[int(pow(6,i)) for i in range(7)]
m9=[int(pow(9,i)) for i in range(1,6)]
m+=m9
m.sort(reverse=True)
# print(m)
dp=[10**18 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
  for j in m:
    if i-j>=0:
      dp[i]=min(dp[i],dp[i-j]+1)
# print(dp)
print((dp[n]))
# Original solution
N = int(eval(input()))

INF = 10 ** 6
dp = [INF] * (10**5+1)
dp[0] = 0

for n in range(1, 100001):
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 6
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 9

print((dp[N]))


# Optimized solution
N = int(eval(input()))

INF = 10 ** 5 + 1

dp = [0 for _ in range(INF)]

for n in range(1, N + 1):
    dp[n] = INF
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 6

    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 9

print((dp[N]))
# Original solution
# 配るDP
N = int(eval(input()))

INF = 10 ** 5 + 1

dp = [INF for _ in range(N + 1)]
dp[0] = 0

for n in range(N):
    power = 1
    while n + power <= N:
        dp[n + power] = min(dp[n + power], dp[n] + 1)
        power *= 6

    power = 1
    while n + power <= N:
        dp[n + power] = min(dp[n + power], dp[n] + 1)
        power *= 9

print((dp[N]))


# Optimized solution
# 貰うDP
N = int(eval(input()))

INF = 10 ** 5 + 1

dp = [INF for _ in range(N + 1)]
dp[0] = 0

for n in range(N + 1):
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 6

    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 9

print((dp[N]))
# Original solution
# 貰うDP
N = int(eval(input()))

INF = 10 ** 5 + 1

dp = [INF for _ in range(N + 1)]
dp[0] = 0

for n in range(N + 1):
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 6

    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 9

print((dp[N]))


# Optimized solution
INF = float('inf')
N = int(eval(input()))

dp = [INF for _ in range(N+1)]
dp[0] = 0

for i in range(1, N+1):
    # 1円玉を使う場合
    dp[i] = min(dp[i], dp[i-1] + 1)
    # 6べき円玉を使う場合
    power = 6
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 6
    # 9べき円玉を使う場合
    power = 9
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9

print((dp[N]))
# Original solution
N = int(eval(input()))
INF = float('inf')
dp = [INF] * (N+1)
dp[0] = 0

for n in range(N + 1):
    power = 0
    while pow(6, power) <= N:
        dp[n] = min(dp[n], dp[n - pow(6, power)] + 1)
        power += 1

    power = 0
    while pow(9, power) <= N:
        dp[n] = min(dp[n], dp[n - pow(9, power)] + 1)
        power += 1

print((dp[N]))


# Optimized solution
N = int(eval(input()))
INF = float('inf')
dp = [INF] * (N+1)
dp[0] = 0

for n in range(N + 1):
    power = 0
    while pow(6, power) <= n:
        dp[n] = min(dp[n], dp[n - pow(6, power)] + 1)
        power += 1

    power = 0
    while pow(9, power) <= n:
        dp[n] = min(dp[n], dp[n - pow(9, power)] + 1)
        power += 1

print((dp[N]))
# Original solution
n = int(eval(input()))

ans = 10 ** 5

for i in range(n + 1):
    count = 0
    
    s = i
    while s > 0:
        count += s % 6
        s //= 6
    
    t = n - i
    while t > 0:
        count += t % 9
        t //= 9
    
    ans = min(count, ans)
    
print(ans)

# Optimized solution
n = int(eval(input()))
ans = 1000000

for i in range(n+1):
    count = 0
    s = i
    while s > 0:
        count += s % 6
        s //= 6
        
    t = n - i
    while t > 0:
        count += t % 9
        t //= 9
        
    ans = min(ans, count)
    
print(ans)
# Original solution
N = int(eval(input()))
dp = [N + 1 for i in range(N+1)]
dp[0] = 0
for i in range(1,N+1):
    j = 0
    while i - pow(6,j) >= 0:
        if dp[i-pow(6,j)] + 1 < dp[i]:
            dp[i] = dp[i-pow(6,j)] + 1
        j += 1
    j = 0
    while i - pow(9,j) >= 0:
        if dp[i-pow(9,j)] + 1 < dp[i]:
            dp[i] = dp[i-pow(9,j)] + 1
        j += 1
print((dp[N]))

# Optimized solution
inf = float('inf')

N = int(eval(input()))

dp = [inf] * (N+1)
dp[0] = 0

for i in range(N):
    if i+1 < N+1:
        dp[i+1] = min(dp[i+1], dp[i] + 1)
    j = 6
    while i+j < N+1:
        dp[i+j] = min(dp[i+j], dp[i] + 1)
        j *= 6
    j = 9
    while i+j < N+1:
        dp[i+j] = min(dp[i+j], dp[i] + 1)
        j *= 9
    
ans = dp[N]
print(ans)
# Original solution
from collections import deque
N=int(eval(input()))
A=[]
for i in range(N):
    s=int(eval(input()))
    A.append(s)
A.sort()
H=deque()
H.append(A[0])
s=1
t=N-1
i=0
while t-s!=-1:
    x=A[s]
    y=A[t]
    a=abs(H[0]-x)
    b=abs(H[-1]-x)
    c=abs(H[0]-y)
    d=abs(H[-1]-y)
    e=max(a,b,c,d)
    if a==e:
        H.appendleft(x)
        s+=1
    elif b==e:
        H.append(x)
        s+=1
    elif c==e:
        H.appendleft(y)
        t-=1
    else:
        H.append(y)
        t-=1
ans=0
for i in range(N-1):
    ans+=abs(H[i+1]-H[i])
print(ans)

# Optimized solution
import sys
N=int(eval(input()))
A=[int(eval(input())) for i in range(N)]
B=sorted(A)
if N%2==0:
    C=B[:(N//2)]
    D=B[(N//2):]
    print((2*sum(D)-2*sum(C)+C[-1]-D[0]))
    sys.exit()
C=B[:(N//2)]
D=B[((N//2)+1):]
s=B[(N//2)]
print((max(2*sum(D)-2*sum(C)+C[-1]-s,2*sum(D)-2*sum(C)+s-D[0])))
# Original solution
from collections import deque
N = int(eval(input()))
A = deque(sorted([int(eval(input())) for i in range(N)]))

X = deque([A.popleft()])
ans = 0
for i in range(N - 1):
    # Aのどちらから取り出してXのどちらに入れるか
    left_left = abs(X[0] - A[0])
    left_right = abs(X[-1] - A[0])
    right_left = abs(X[0] - A[-1])
    right_right = abs(X[-1] - A[-1])

    if left_left >= max(left_right, right_left, right_right):
        ans += left_left
        X.appendleft(A.popleft())

    elif left_right >= max(left_left, right_left, right_right):
        ans += left_right
        X.append(A.popleft())

    elif right_left >= max(left_left, left_right, right_right):
        ans += right_left
        X.appendleft(A.pop())

    else:
        ans += right_right
        X.append(A.pop())

print(ans)


# Optimized solution
N = int(eval(input()))
A = sorted([int(eval(input())) for i in range(N)])

if N % 2 == 0:
    X = [-2] * ((N - 2) // 2) + [-1, 1] + [2] * ((N - 2) // 2)
    ans = sum([a * x for a, x in zip(A, X)])
    print(ans)
else:
    X1 = [-2] * ((N - 2) // 2 + 1) + [1, 1] + [2] * ((N - 2) // 2)
    X2 = [-2] * ((N - 2) // 2) + [-1, -1] + [2] * ((N - 2) // 2 + 1)
    ans1 = sum([a * x for a, x in zip(A, X1)])
    ans2 = sum([a * x for a, x in zip(A, X2)])
    print((max(ans1, ans2)))
# Original solution
# coding: utf-8
# Your code here!

n=int(eval(input()))
a=[]
for _ in range(n):
    a.append(int(eval(input())))
    a.sort()

#print(a)    


ans=0

if n%2==0:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += a[n//2] - a[n//2-1]

if n%2==1:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += max(a[n//2+1] + a[n//2] - 2*a[n//2-1], 2*a[n//2+1] - a[n//2] - a[n//2-1])

print(ans)

# Optimized solution
# coding: utf-8
# Your code here!

n=int(eval(input()))
a=[]
for _ in range(n):
    a.append(int(eval(input())))

a.sort()

#print(a)    


ans=0

if n%2==0:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += a[n//2] - a[n//2-1]

if n%2==1:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += max(a[n//2+1] + a[n//2] - 2*a[n//2-1], 2*a[n//2+1] - a[n//2] - a[n//2-1])

print(ans)
# Original solution
N = int(eval(input()))
A = []
for i in range(N):
	A.append(int(eval(input())))
A.sort()
ary1 = [A[0]]
ary2 = [A[N-1]]
fst = 0
lst = N
fst_flg = False
sum1, sum2 = 0,0
while fst + 1 < lst:
	if fst_flg:
		fst_flg = False
		if fst + 2 != lst:
			fst += 1
			ary1 = [A[fst]] + ary1 + [A[fst+1]]
			ary2 = [A[N-1-fst]] + ary2 + [A[N-1-fst-1]]
			fst += 1
			l = len(ary1)
			sum1 += abs(ary1[0]-ary1[1]) + abs(ary1[l-1]-ary1[l-2])
			sum2 += abs(ary2[0]-ary2[1]) + abs(ary2[l-1]-ary2[l-2])
		else:
			fst += 1
			ary1 = [A[fst]] + ary1
			ary2 = [A[N-1-fst]] + ary2
			sum1 += abs(ary1[0]-ary1[1])
			sum2 += abs(ary2[0]-ary2[1])
	else:
		fst_flg = True
		if fst + 2 != lst:
			lst -= 1
			ary1 = [A[lst]] + ary1 + [A[lst-1]]
			ary2 = [A[N-1-lst]] + ary2 + [A[N-lst]]
			lst -= 1
			l = len(ary1)
			sum1 += abs(ary1[0]-ary1[1]) + abs(ary1[l-1]-ary1[l-2])
			sum2 += abs(ary2[0]-ary2[1]) + abs(ary2[l-1]-ary2[l-2])
		else:
			lst -= 1
			ary1 = [A[lst]] + ary1
			ary2 = [A[N-1-lst]] + ary2
			sum1 += abs(ary1[0]-ary1[1])
			sum2 += abs(ary2[0]-ary2[1])
print((max(sum1,sum2)))

# Optimized solution
N = int(eval(input()))
A = []
for i in range(N):
	A.append(int(eval(input())))
A.sort()
if N % 2 == 0:
	print((-2*sum(A[:N//2-1]) + 2*(sum(A[N//2+1:])) + A[N//2] - A[N//2-1]))
	exit()

a = 2*sum(A[N//2+1:]) - 2*sum(A[:N//2-1]) - A[N//2] - A[N//2-1]
b = 2*sum(A[N//2+2:]) - 2*sum(A[:N//2]) + A[N//2] + A[N//2+1]
print((max(a,b)))
# Original solution
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni, sets):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  sets[ra] += sets[rb]
  uni[rb] = ra
  return True


##
N, K, L = map(int, input().split())

road = [0]*(N+1)
rail = [0]*(N+1)

road_sets = [0]*(N+1)
rail_sets = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i
  road_sets[i] = [i]
  rail_sets[i] = [i]

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road, road_sets)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail, rail_sets)

for i in range(1, N+1):
  tmp = set(road_sets[root(i, road)]) & set(rail_sets[root(i, rail)])
  ans = len(tmp)
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")


# Optimized solution
# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni, sets):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  sets[ra] = sets[ra] | sets[rb]
  uni[rb] = ra
  return True


##
N, K, L = map(int, input().split())

road = [0]*(N+1)
rail = [0]*(N+1)

road_sets = [0]*(N+1)
rail_sets = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i
  road_sets[i] = set([i])
  rail_sets[i] = set([i])

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road, road_sets)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail, rail_sets)

for i in range(1, N+1):
  tmp = road_sets[root(i, road)] & rail_sets[root(i, rail)]
  ans = len(tmp)
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")
# Original solution
n, k, l = list(map(int, input().split()))

def root(x):
    if x == parent[x]: return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

parent = list(range(n))
for i in range(k):
    p, q = list(map(int, input().split()))
    unite(p-1, q-1)
parent1 = parent
for i in range(n):root(i)

parent = list(range(n))
for i in range(l):
    r, s = list(map(int, input().split()))
    unite(r-1, s-1)
parent2 = parent
for i in range(n):root(i)

dic = {}
for p1, p2 in zip(parent1, parent2):
    dic[p1, p2] = dic.get((p1, p2), 0) + 1

ans = [dic[p1, p2] for p1, p2 in zip(parent1, parent2)]
print(" ".join(map(str, ans)))


# Optimized solution
n, k, l = list(map(int, input().split()))

def root(x):
    if x != parent[x]: parent[x] = x = root(parent[x])
    return x
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

parent = list(range(n))
for i in range(k):
    p, q = list(map(int, input().split()))
    unite(p-1, q-1)
parent1 = parent
for i in range(n):root(i)

parent = list(range(n))
for i in range(l):
    r, s = list(map(int, input().split()))
    unite(r-1, s-1)
parent2 = parent
for i in range(n):root(i)

dic = {}
for p1, p2 in zip(parent1, parent2):
    dic[p1, p2] = dic.get((p1, p2), 0) + 1

ans = [dic[p1, p2] for p1, p2 in zip(parent1, parent2)]
print(" ".join(map(str, ans)))
# Original solution
import sys
from collections import deque
sys.setrecursionlimit(1000000)
N, K, L = list(map(int, input().split()))
pq = [list(map(int, input().split())) for _ in range(K)]
rs = [list(map(int, input().split())) for _ in range(L)]

G_r = [[] for _ in range(N+1)]
for elem in pq:
    G_r[elem[0]].append(elem[1])
    G_r[elem[1]].append(elem[0])
G_t = [[] for _ in range(N+1)]
for elem in rs:
    G_t[elem[0]].append(elem[1])
    G_t[elem[1]].append(elem[0])


field_r = [[] for _ in range(N+1)]


def dfs_r(i):
    q = deque()
    q.append(i)
    field_r[i].append(i)
    while q:
        tmp = q.pop()
        for pos in G_r[tmp]:
            if pos not in field_r[i]:
                field_r[i].append(pos)
                q.append(pos)
            else:
                continue
for i in range(1, N+1):
    if not field_r[i]:
        dfs_r(i)

field_t = [[] for _ in range(N+1)]
cnt = [1 for _ in range(N+1)]


def dfs_t(i):
    q = deque()
    q.append(i)
    field_t[i].append(i)
    while q:
        tmp = q.pop()
        for pos in G_t[tmp]:
            if pos not in field_t[i]:
                field_t[i].append(pos)
                if pos in field_r[i]:
                    cnt[i] += 1
                q.append(pos)
            else:
                continue
for i in range(1, N+1):
    if not field_t[i]:
        dfs_t(i)

ans = []
for i in range(1, N+1):
    ans.append(cnt[i])
print((' '.join(map(str, ans))))


# Optimized solution
import sys
from collections import deque, Counter
sys.setrecursionlimit(1000000)
N, K, L = list(map(int, input().split()))
pq = [list(map(int, input().split())) for _ in range(K)]
rs = [list(map(int, input().split())) for _ in range(L)]

G_r = [[] for _ in range(N+1)]
for elem in pq:
    G_r[elem[0]].append(elem[1])
    G_r[elem[1]].append(elem[0])
G_t = [[] for _ in range(N+1)]
for elem in rs:
    G_t[elem[0]].append(elem[1])
    G_t[elem[1]].append(elem[0])


field_r = [None]*(N+1)


def dfs_r(i, idx):
    q = deque()
    q.append(i)
    field_r[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_r[tmp]:
            if field_r[pos] is None:
                field_r[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_r[i] is None:
        dfs_r(i, idx)
        idx += 1


field_t = [None]*(N+1)


def dfs_t(i, idx):
    q = deque()
    q.append(i)
    field_t[i] = idx
    while q:
        tmp = q.pop()
        for pos in G_t[tmp]:
            if field_t[pos] is None:
                field_t[pos] = idx
                q.append(pos)
            else:
                continue
idx = 0
for i in range(1, N+1):
    if field_t[i] is None:
        dfs_t(i, idx)
        idx += 1

m = list(zip(field_r[1:], field_t[1:]))
cnt = Counter(m)
ans = []
for elem in list(m):
    ans.append(cnt[elem])
print((' '.join(map(str, ans))))
# Original solution
from collections import defaultdict as dd
road = dd(list)
train = dd(list)
rd = dict()
td = dict()
ans = []
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
n,k,l = list(map(int, input().split()))
for _ in range(k):
    a,b = list(map(int, input().split()))
    road[a].append(b)
    road[b].append(a)
for _ in range(l):
    a,b = list(map(int, input().split()))
    train[a].append(b)
    train[b].append(a)
for i in range(1,n+1):
    if i not in rd:
      tempr = gr(road,i)
      for x in tempr:
        rd[x] = tempr
    if i not in td:
      tempt = gr(train,i)
      for x in tempt:
        td[x] = tempt
    ans.append(str(len(rd[i]&td[i])))
print((" ".join(ans)))

# Optimized solution
from collections import defaultdict as dd
def find(u,x):
    if u[x]<0:
        return x
    u[x] = find(u,u[x])
    return u[x]

def unite(u,a,b):
    a = find(u,a)
    b = find(u,b)
    if a == b:
        return False
    if u[b] < u[a]:
        a,b = b,a
    u[a] += u[b]
    u[b] = a
    return True
n,k,l = list(map(int, input().split()))
ufr = [-1]*(n+1)
uft = [-1]*(n+1)
for _ in range(k):
    a,b = list(map(int, input().split()))
    unite(ufr,a,b)
for _ in range(l):
    a,b = list(map(int, input().split()))
    unite(uft,a,b)
tot = dd(int)
for i in range(1,n+1):
  tot[(find(ufr,i),find(uft,i))] += 1
print((" ".join([str(tot[(find(ufr,i),find(uft,i))]) for i in range(1,n+1)])))
# Original solution
import queue
N,K,L=list(map(int,input().split()))
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=list(map(int,input().split()))
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=list(map(int,input().split()))
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=queue.Queue()
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.put(i)
        while(not(q.empty())):
            r=q.get()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.put(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print((" ".join(ans)))




# Optimized solution
N,K,L=list(map(int,input().split()))
G=[[] for i in range(N)]
H=[[] for i in range(N)]
#T=[-1 for i in range(N)]
#B=[-1 for i in range(N)]
for i in range(K):
    p,q=list(map(int,input().split()))
    G[p-1].append(q-1)
    G[q-1].append(p-1)
for i in range(L):
    r,s=list(map(int,input().split()))
    H[r-1].append(s-1)
    H[s-1].append(r-1)
def bfs(A):
    k=1
    q=[]
    reached=[0 for i in range(N)]
    res=[0 for i in range(N)]
    for i in range(N):
        if reached[i]==1:
            continue
        q.append(i)
        while(len(q)>0):
            r=q[-1]
            q.pop()
            res[r]=k
            for p in A[r]:
                if reached[p]==1:
                    continue
                q.append(p)
                reached[p]=1
        k+=1
    return res
T=bfs(G)
B=bfs(H)
TB=[(T[i],B[i]) for i in range(N)]
D=dict()
for i in range(N):
    if TB[i] in D:
        D[TB[i]]+=1
    else:
        D[TB[i]]=1
ans=[str(D[TB[i]]) for i in range(N)]
print((" ".join(ans)))