Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
[x.reverse() for x in s]

class Trie:
    class Node:
        def __init__(self,c):
            self.c=c
            self.next_c_id={}
            self.common=0
            self.end=-1

    def __init__(self):
        self.trie=[self.Node('')]
    
    def add(self,id,s):
        i=0
        now=0
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            self.trie[now].common+=1
            i+=1
        while i<len(s):
            self.trie[now].next_c_id[s[i]]=len(self.trie)
            now=len(self.trie)
            self.trie.append(self.Node(s[i]))
            self.trie[now].common+=1
            i+=1
        self.trie[now].end=id
    
    def search(self,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            i+=1
        if i<len(s):return []
        return ary

tr=Trie()
#s.sort(key=lambda x:len(x))
for id,x in enumerate(s):
    tr.add(id,x)
ans=0
for i,x in enumerate(s):
    ary=tr.search(x)
    seen=set(())
    #print(x,ary)
    while ary:
        id=ary.pop()
        for nv in seen.intersection(tr.trie[id].next_c_id.keys()):
            if tr.trie[tr.trie[id].next_c_id[nv]].end>=0 and tr.trie[tr.trie[id].next_c_id[nv]].end!=i:
                ans+=1
        seen.add(tr.trie[id].c)
    #print(x,ans)
print(ans)


### FIXED CODE ###

class Trie:
    class Node:
        def __init__(self,c):
            self.c=c
            self.next_c_id={}
            #self.common=0
            self.end=-1

    def __init__(self):
        self.trie=[self.Node('')]
    
    def add(self,id,s):
        i=0
        now=0
        ary=[0]
        while i<len(s) and s[i] in self.trie[now].next_c_id:
            now=self.trie[now].next_c_id[s[i]]
            ary.append(now)
            #self.trie[now].common+=1
            i+=1
        while i<len(s):
            self.trie[now].next_c_id[s[i]]=len(self.trie)
            now=len(self.trie)
            ary.append(now)
            self.trie.append(self.Node(s[i]))
            #self.trie[now].common+=1
            i+=1
        self.trie[now].end=id
        return ary

def main(s):
    tr=Trie()
    s.sort(key=lambda x:len(x))
    ans=0
    for i,x in enumerate(s):
        ary=tr.add(i,x)
        seen=set(())
        while ary:
            id=ary.pop()
            for nv in seen&tr.trie[id].next_c_id.keys():
                if tr.trie[tr.trie[id].next_c_id[nv]].end>=0 and tr.trie[tr.trie[id].next_c_id[nv]].end!=i:
                    ans+=1
            seen.add(tr.trie[id].c)
    print(ans)

if __name__=='__main__':
    a2n=lambda x:ord(x)-ord('a')
    n=int(input())
    s=[list(map(a2n,list(input()))) for _ in range(n)]
    [x.reverse() for x in s]
    main(s)
### BUGGY CODE ###

import sys
import heapq

heap = []
while True:
	input_line = sys.stdin.readline()
	input_line = input_line.strip().split(' ')
	if input_line[0][0] == 'i' :
		heapq.heappush(heap,-int(input_line[1]))
		heapq.heapify(heap)
	elif input_line[0][1] == 'x' :
		print(-int(heapq.heappop(heap)))
	else :
		break

### FIXED CODE ###

import sys
import heapq

heap = []
while True:
	input_line = sys.stdin.readline()
	input_line = input_line.strip().split(' ')
	if input_line[0][0] == 'i' :
		heapq.heappush(heap,-int(input_line[1]))
	elif input_line[0][1] == 'x' :
		print(-int(heapq.heappop(heap)))
	else :
		break
### BUGGY CODE ###

import sys

class UnionFind():
    def __init__(self, num, V):
        self.par = [-1]*num
        #self.size = [1]*num
        self.unused = [0]*num
        self.cost = V
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return 0
        if ry > rx:
            rx, ry = ry, rx
        self.par[ry] = rx
        #self.size[rx] += self.size[ry]
        self.cost[rx] += self.cost[ry]
        self.unused[rx] += self.unused[ry]
        self.unused[ry] = 0
        return 1

def solve():
    
    N, M = map(int, input().split())
    X = list(map(int, sys.stdin.readline().split()))
    Edge = [None]*M
    for i in range(M):
        a, b, y = list(map(int, sys.stdin.readline().split()))
        Edge[i] = (y, a-1, b-1)
    
    Edge.sort()
    Tr = UnionFind(N, X)
    for y, a, b in Edge:
        Tr.union(a, b)
        pa = Tr.find(a)
        if Tr.cost[pa] >= y:
            Tr.unused[pa] = 0
        else:
            Tr.unused[pa] += 1
    
    print(sum(Tr.unused))
    return

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys

class UnionFind():
    def __init__(self, num, V):
        self.par = [-1]*num
        #self.size = [1]*num
        self.unused = [0]*num
        self.cost = V
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return 0
        if ry > rx:
            rx, ry = ry, rx
        self.par[ry] = rx
        #self.size[rx] += self.size[ry]
        self.cost[rx] += self.cost[ry]
        self.unused[rx] += self.unused[ry]
        self.unused[ry] = 0
        return 1

def solve():
    
    N, M = map(int, input().split())
    X = list(map(int, sys.stdin.readline().split()))
    Edge = [None]*M
    for i in range(M):
        a, b, y = list(map(int, sys.stdin.readline().split()))
        Edge[i] = (y, a-1, b-1)
    
    Edge.sort()
    Tr = UnionFind(N, X)
    for y, a, b in Edge:
        Tr.union(a, b)
        pa = Tr.find(a)
        if Tr.cost[pa] >= y:
            Tr.unused[pa] = 0
        else:
            Tr.unused[pa] += 1
    
    print(sum(Tr.unused))
    return

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

h = int(input())


li = list()
ans = 0
def dfs(x):
    global ans
    ans += 1
    if x == 1:
        return
    else:
        dfs(x//2)
        dfs(x//2)

dfs(h)
print(ans)

### FIXED CODE ###

h = int(input())

ans = 0
count = 0
while h>=1:
    count += 1
    ans += 2 ** (count-1)
    h //= 2
print(ans)
### BUGGY CODE ###

import bisect as bc
from collections import defaultdict
from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
q = deque([i for i in range(N)])
 
for i in range(N):
    ai = A[i]
    itr = list(q)
    for j in itr:
        if j == i:
            continue
        if A[j] % ai == 0:
            del q[bc.bisect_left(q,j)]
 
print(len(q))
 
 

### FIXED CODE ###

import bisect as bc

N = int(input())
A = list(map(int,input().split()))
A.sort()

dp = [True for _ in range(A[-1]+1)]

for i in range(N):
    ai = A[i]
    for j in range(2,A[-1]+1):
        if ai*j > A[-1]:
            break
        if dp[ai*j]:
            dp[ai*j] = False

ans = 0
finish = [True for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]] and finish[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
            finish[A[i]] = False

print(ans)
### BUGGY CODE ###

import itertools
n,K = list(map(int,input().split()))

mod = 10**9 + 7
M = 10**100%mod 

ans = set()
for k in range(K,n+2):
  for i in itertools.combinations(range(n+1),k):
    ans.add(sum([M+a%mod for a in i]))

print(len(ans))

### FIXED CODE ###

n,K = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for k in range(K,n+2):
  #ans += (n+1)*n//2 -(n+1-k)*(n-k)//2-k*(k-1)//2 + 1
  #ans += (n**2+n)//2 - (n**2-n*k+n-k-n*k+k**2)//2 - (k**2-k)//2 + 1
  #ans += (n**2+n - (n**2-n*k+n-k-n*k+k**2) -k**2 + k)//2 + 1
  #ans += (n**2 + n - n**2 + n*k - n + k + n*k - k**2 - k**2 + k)//2 + 1
  #ans += (2*n*k + 2*k - 2*k**2)//2 + 1
  ans += n*k - k**2 + k  + 1
print(ans%mod)
### BUGGY CODE ###

from collections import deque

D = deque(input())

for i in range(int(input())):
  q = input().split()
  
  if int(q[0])==1:
    D = deque(reversed(D))
  else:
    if int(q[1])==1:
      D.appendleft(q[2])
    else:
      D.append(q[2])

print(*D,sep="")

### FIXED CODE ###

S = input()
Q = int(input())
T = ""

for q in range(Q):
  que = input().split()
  if que[0]=="1":
        S,T = T,S
  else:
    if que[1]=="1":
      T+=que[2]
    else:
      S+=que[2]

print(T[::-1]+S)
### BUGGY CODE ###

N=int(input())
S=input()
count=0
r=[]
g=[]
b=[]
for i in range(N):
	if S[i]=="R":
		r.append(i+1)
	if S[i]=="G":
		g.append(i+1)
	if S[i]=="B":
		b.append(i+1)
for x in r:
	for y in g:
		for z in b:
			L=[x,y,z]
			#print(L)
			L=sorted(L)
			if (L[1]-L[0])!=(L[2]-L[1]):
				count+=1
print(count)


### FIXED CODE ###

N=int(input())
S=input()
count=0
r=S.count("R")
g=S.count("G")
b=S.count("B")

count+=r*g*b
#print(r,g,b)
for i in range(0,N-1):
	for j in range(i+1,N):
		k=2*j-i
		if k>=N:break
		if S[i]!=S[j] and S[j]!=S[k] and S[i]!=S[k]:
			count-=1
print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [[100000 for i in range(n)]for j in range(n)]

for i in range(n):
    for j in range(k+1):
        if i+j<n:
            if i == 0:
                dp[i][j] = abs(h[j]-h[0])
            else:
                dp[i][i+j] = min(dp[i-1][i] + abs(h[i] - h[i + j]), dp[i-1][i+j])
print(dp[n-1][n-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [1000000000 for i in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(k+1):
        if i+j<n:
            dp[i + j] = min(dp[i] + abs(h[i] - h[i + j]), dp[i + j])
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i+1,N):
        if sorted(S[i]) == sorted(S[j]):
            ans += 1
            #print(S[i],S[j])
print(ans)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]

dic = {}
ans = 0
for s in S:
    sortstr = str(sorted(s))
    if sortstr in dic:
        ans += dic[sortstr]
        dic[sortstr] += 1
    else:
        dic[sortstr] = 1
print(ans)
### BUGGY CODE ###

N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1

A = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        A[i][i + j] = min(abs(x- i) +1 +abs(y-i-j),j)
A[X-1][Y-1] = 1
ans = []
ans.append(sum(A, []))
for t in range(N):
    if t == 0:
        continue
    sum =  A.count(t)
    print(ans[0].count(t))

### FIXED CODE ###


N, X, Y = input().split()
N = int(N)
X = int(X)
x = X - 1
Y = int(Y)
y = Y -1
ans = [0] * (N)
A = [[] * N for _ in range(N)]
for i in range(N):
    for j in range(N-i):
        path = min(abs(x- i) +1 +abs(y-i-j),j)
        ans[path] += 1
for _ in range(len(ans)):
    if _ == 0:
        continue
    print(ans[_])
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

d = [0] * n

if k >= n:
    k = n-1


for i in range(1, k):
    d[i] = min(d[j]+abs(h[i]-h[j]) for j in range(i))

for i in range(n-k):
    d[i+k] = min(d[i+j]+abs(h[i+k]-h[i+j]) for j in range(k))

print(d[n-1])

### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法3 - セグ木
"""
ダメージ量をセグ木の区間で管理する。
なお、61行目までセグ木のコードなのでそれ以降を読めば良い。

この解法では、
自分の座標より右側の巻き込める量を調べる
ではなく、
自分より右側なんてしったこっちゃ無いので自分より左側のダメージが足りてるかどうかを
逐一確認し、足りないなら自分の座標に必要なだけのダメージを記録する
という考え方をする。
故に、変数kは左側であるx - 2*dを参照する。
"""
#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

#process
x = []
for i in lst1:
    x.append(i[0])


ans = 0

for i in range(n):
    k = bisect.bisect_left(x,lst1[i][0]-2*d) #手前側にあるダメージ量を確認

    r = query(k,i) #kからiまでの合計ダメージを取得

    if lst1[i][1] > r:
        need = math.ceil((lst1[i][1]-r)/a)
        ans += need
        update(i,need*a)

print(ans)




### FIXED CODE ###

import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法2 - imos法
"""
単純に座標に対してimos法を行うと、座標の制約は10**9なので間に合わない。
process1
そこで、各モンスターに対して、そのモンスターを左端で攻撃を行った際、右側の巻き込めるモンスターのインデックスを
保存するリストを作る。
process2
これにより、imosのテーブルはn+1個で答えを求めることができる。
また、imosの累積和は順次求めていく感じになる。
"""
x = []
for i in lst1:
    x.append(i[0])

#process1
index = 0
reach = []
for i in range(n):
    index = bisect.bisect_right(x,lst1[i][0]+2*d)
    reach.append(index)

#process2
ans = 0
imos = [0]*(n+1) #その座標に効いている魔法の回数(ダメージ量ではない)

for i in range(n):
    if imos[i]*a < lst1[i][1]: #ダメージが足りないなら
        need = math.ceil((lst1[i][1]-imos[i]*a)/a)
        imos[i] += need
        imos[reach[i]] -= need #届かなくなったとこでマイナス
        ans += need
    imos[i+1] += imos[i] #累積和を逐一とる

print(ans)
### BUGGY CODE ###

n=int(input())
s=sorted([input() for k in range(n)])
p=[]
if(len(set(s))==len(s)):
    for u in range(len(s)):
        print(s[u])
    exit()
else:
    s1 = [m for m in sorted(list(set(s))) if s.count(m)>1]
    for i in s1:
        p.append(s.count(i))
max=max(p)
for j, x in enumerate(p):
    if(x == max):
        print(s1[j])

### FIXED CODE ###

N = int(input())
d = {}
for _ in range(N):
  s = input()
  if(s not in d):
    d[s] = 1
  else:
    d[s] += 1
d2 = sorted(d.items(),key=lambda x:x[1], reverse=True)
s1=[]
s1.append(d2[0][0])
p=d2[0][1]
for t in d2[1:]:
  q=t[1]
  if(q==p):
    s1.append(t[0])
  else:
    break
s1=sorted(s1)
for i in s1:
  print(i)
### BUGGY CODE ###


N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10
DP = [INF]*N
DP[0] = 0
DP[1] = abs(h[1]-h[0])
for i in range(2,N):
    for j in range(1,min(K,i)+1):
        DP[i] = min(DP[i], DP[i-j] + abs(h[i-j]-h[i]))
    #print(DP[i])
print(DP[-1])

### FIXED CODE ###


def frog2(H,N,K):
    #print(H)
    DP = [10**10]*N
    #DP = [0]*N
    DP[0] = 0
    DP[1] = abs(H[1]-H[0])
    for i in range(2,N):
        for j in range(1,K+1):
            DP[i] = chmin(DP[i],DP[i-j]+abs(H[i]-H[i-j]))
    return DP[-1]

def chmin(a,b):
    if a < b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,K = map(int,input().split())
    H = list(map(int,input().split()))
    ans = frog2(H,N,K)
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
N = int(input())
h = list(map(int, input().split()))
from functools import lru_cache
@lru_cache(maxsize=1000)
def dp(i):
    if i == 0:
        return 0
    if i>=2:
        return min(dp(i-1)+abs(h[i]-h[i-1]), dp(i-2)+abs(h[i]-h[i-2]))
    else:
        return dp(i-1)+abs(h[i]-h[i-1])
print(dp(N-1))



### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
dp = [0]*N
for i in range(1, N):
    if i-2>=0:
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    else:
        dp[i] = dp[i-1]+abs(h[i]-h[i-1])
print(dp[-1])
### BUGGY CODE ###

# a b c
# b e d
# c d f
# について、
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]
# [a  b  c  a  b]
# [b  e  d  b  e]
# 左上の1,1から始まるものが条件を満たすなら、
# 2,2から始まるものも3,3から始まるものも条件を満たす
# 一つ条件を満たすのであれば、N個条件を満たすことになる。
# 従い、以下を順にチェックして答えをN倍すれば良い
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]

import sys
readline = sys.stdin.readline

N = int(readline())
grid = [None] * N
for i in range(N):
  S = readline().rstrip()
  grid[i] = S + S[:-1]
  
# 左上の頂点を(0,0)~(N-1,0)の全てをチェックする
ans = 0
for p in range(N):
  # 左上の頂点はp
  ok = True
  for i in range(N):
    for j in range(i+1):
      if grid[i][j + p] != grid[j][i + p]:
        ok = False
        break
    if not ok:
      break
  if ok:
    ans += 1

print(ans * N)


### FIXED CODE ###

# a b c
# b e d
# c d f
# について、
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]
# [a  b  c  a  b]
# [b  e  d  b  e]
# 左上の1,1から始まるものが条件を満たすなら、
# 2,2から始まるものも3,3から始まるものも条件を満たす
# 一つ条件を満たすのであれば、N個条件を満たすことになる。
# 従い、以下を順にチェックして答えをN倍すれば良い
#  a  b  c [a  b]
#  b  e  d [b  e]
#  c  d  f [c  d]

import sys
readline = sys.stdin.readline

N = int(readline())
grid = [None] * N
for i in range(N):
  S = readline().rstrip()
  grid[i] = S + S[:-1]
  
# 左上の頂点を(0,0)~(N-1,0)の全てをチェックする
ans = 0
for p in range(N):
  # 左上の頂点はp
  ok = True
  for i in range(N):
    for j in range(i+1):
      if grid[i][j + p] != grid[j][i + p]:
        ok = False
        break
    if not ok:
      break
  if ok:
    ans += 1

print(ans * N)
### BUGGY CODE ###

#!/usr/bin/env pypy3


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    n, k, l = (int(x) for x in input().split())
    uf_roads = UnionFind(n)
    for _ in range(k):
        p, q = (int(x) - 1 for x in input().split())
        uf_roads.unite(p, q)
    uf_rails = UnionFind(n)
    for _ in range(l):
        r, s = (int(x) - 1 for x in input().split())
        uf_rails.unite(r, s)
    ans = [sum(1 for y in range(n) if
               uf_roads.in_the_same_set(x, y) and
               uf_rails.in_the_same_set(x, y)) for x in range(n)]
    print(" ".join(str(z) for z in ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3

import collections


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = list(range(number_of_nodes))
        self.rank = [0] * number_of_nodes

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    n, k, l = (int(x) for x in input().split())
    uf_roads = UnionFind(n)
    for _ in range(k):
        p, q = (int(x) - 1 for x in input().split())
        uf_roads.unite(p, q)
    uf_rails = UnionFind(n)
    for _ in range(l):
        r, s = (int(x) - 1 for x in input().split())
        uf_rails.unite(r, s)
    ctr = collections.Counter((uf_roads.root(i), uf_rails.root(i))
                              for i in range(n))
    ans = [ctr[(uf_roads.root(i), uf_rails.root(i))] for i in range(n)]
    print(" ".join(str(a) for a in ans))

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
A_s=set(A)
for i in range(N):
    Com=0
    A_k=A.copy()
    A_k[i]=""
    for k in A_s:
        x=A_k.count(k)
        Com+=int(x*(x-1)/2)
    print(Com)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=[int(x) for x in input().split()]
Com=0

A_C=Counter(A)

for name,x in A_C.items():
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A_C[A[i]]
    print(Com-y+1)
### BUGGY CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        S.reverse()
    else:
        if q[1] == '1':
            S.appendleft(q[2])
        else:
            S.append(q[2])
print(''.join(S))


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

flag = False
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        flag = True if flag is False else False
    else:
        if flag is False:
            if q[1] == '1':
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if q[1] == '1':
                S.append(q[2])
            else:
                S.appendleft(q[2])

if flag is True:
    S.reverse()
print(''.join(S))
### BUGGY CODE ###

# D - Line++
from collections import deque

INF = 1001001001

n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0]*n

for i in range(n):
    dist = [INF]*n
    q = deque()
    dist[i] = 0
    q.append(i)
    
    while len(q)>0:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0:
            if dist[v-1]==INF:
                q.append(v-1)
                dist[v-1]=d+1
        if v+1 < n:
            if dist[v+1]==INF:
                q.append(v+1)
                dist[v+1]=d+1
        if v==x:
            if dist[y]==INF:
                q.append(y)
                dist[y]=d+1
        if v==y:
            if dist[x]==INF:
                q.append(x)
                dist[x]=d+1
    for d in dist:
        if d!=0 and d!=INF:
            ans[d] += 1

for a in ans[1:]:
    print(int(a//2))


### FIXED CODE ###

# D - Line++

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
cnt = [0] * N

for i in range(N):
    for j in range(i+1,N):
         tmp = min(j-i, abs(i-X)+abs(j-Y)+1)
         cnt[tmp] += 1

for k in range(1, N):
    print(cnt[k])
### BUGGY CODE ###

n = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    b = [0] * n
    for j in range(n):
        if i >> j & 1:
            b[j] = 1
    X = sum([v for i, v in enumerate(V) if b[i] == 1])
    Y = sum([c for i, c in enumerate(C) if b[i] == 1])
    ans = max(ans, X - Y)
print(ans)

### FIXED CODE ###

n = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for v, c in zip(V, C):
    if v > c:
        ans += v - c
print(ans)
### BUGGY CODE ###

mod = 10**9 + 7

n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]

dp = {}
for i in range(n + 1):
    dp[i] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)


### FIXED CODE ###

mod = 10**9 + 7

n, m = list(map(int, input().split()))
a = set([int(input()) for _ in range(m)])

dp = {}
for i in range(n + 1):
    dp[i] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)