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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
n,m=map(int,input().split())
p = [int(i)-1 for i in input().split() ]

uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.union(x-1,y-1)

ans=0
groups = uf.all_group_members().values()

for c in groups:
    ans+= len( set(c) & set(p[i] for i in c ) ) 
print(ans)
      


### FIXED CODE ###

n,m=map(int,input().split())
p = [int(i)-1 for i in input().split() ]


tree=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

from collections import deque

groups=[]
been=[0]*n
for i in range(n):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                q.append((x,y))#子ノードを追加
        groups.append(group)

ans=0
for group in groups:
    ans+= len( set(group) & set(p[g] for g in group) )

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

k, s = map(int, input().split())

count = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1

print(count)


### FIXED CODE ###

k, s = map(int, input().split())

count = 0

for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1

print(count)
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp[l]
    dp[ss] = tmp/(len(tree[ss])-1) + 1
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp[b]
        dp[a] = tmp/len(tree[a]) + 1
    
    return dp[0]

for i in range(n-1):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)



### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
tree = [[] for _ in range(n)]
for i in range(m):
    s,t = mi()
    tree[s-1].append(t-1)
dp = [0]*n
for i in reversed(range(n-1)):
    size = len(tree[i])
    for k in tree[i]:
        dp[i] += dp[k] 
    dp[i] /= size
    dp[i] += 1
ans = dp[0]

def func(ss,tt):
    tmp = 0
    for l in tree[ss]:
        if l == tt:
            continue
        tmp += dp[l]
    tmp = tmp/(len(tree[ss])-1) + 1
    if tmp > dp[ss]:
        return dp[0]
    else:
        dp[ss] = tmp
    
    for a in reversed(range(ss)):
        tmp = 0
        for b in tree[a]:
            tmp += dp[b]
        dp[a] = tmp/len(tree[a]) + 1
    
    return dp[0]

for i in range(n-1):
    if len(tree[i]) == 1:
        continue
    for k in tree[i]:
        ans = min(ans,func(i,k))
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    while a != b:
        if a < b:
            b = b - a
        else:
            a = a - b
    return a

def m(a):
    a.sort()
    l = len(a)
    b = []
    for i in range(len(a) // 2):
        b.append(gcd(a[i], a[i + 1]))
    if l % 2 == 1:
        b.append(a[l - 1])
    return b

    
n = int(input())
a = [int(x) for x in input().split(" ")]

while len(a) > 1:
    a = m(a)

print(a[0])


### FIXED CODE ###

def gcd(a, b):
    while b != a:
        if a < b:
            b = b % a
            if b == 0:
                return a
        elif b < a:
            a = a % b
            if a == 0:
                return b
    return a

def m(a):
    a.sort()
    l = len(a)
    b = []
    for i in range(l // 2):
        b.append(gcd(a[i], a[l - i - 1]))
    if l % 2 == 1:
        b.append(a[l // 2])
    return list(set(b))

    
n = int(input())
a = [int(x) for x in input().split(" ")]

while len(a) > 1:
    a = m(a)

print(a[0])
### BUGGY CODE ###

n,h=map(int,input().split())
l=list(map(int,input().split()))
c=[0]*n
c[1]=abs(l[0]-l[1])
for i in range(2,n):
    c[i]=min( c[j]+abs(l[i]-l[j]) for j in range(max(0,i-h),i) )
print(c[-1])


### FIXED CODE ###

n,h=map(int,input().split())
l=list(map(int,input().split()))
c=[10**9]*n
c[0]=0
c[1]=abs(l[0]-l[1])
for i in range(2,n):
    c[i]=min( c[j]+abs(l[i]-l[j]) for j in range(max(0,i-h),i) )
print(c[-1])
### BUGGY CODE ###

import numpy as np

n = int(input())
aa = np.array(list(map(int,input().split())))
a=np.sort(aa)
ah=[1]*len(a)

for i in range(n-1):
    if ah[i]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j],a[i])
            ah[j]=min(wk0,ah[j])
            if wk1==1 and wk0==0:
                ah[i]=0
print(sum(ah))

### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int,input().split())))

amax=max(a)+1
ah=[0]*amax

for i in a:
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)
### BUGGY CODE ###

import re
import sys

line = next(sys.stdin).strip()

count = 0
to_add = len(re.findall('BW', line))
while to_add:
    count += to_add
    line = line.replace('BW', 'WB')
    to_add = len(re.findall('BW', line))

print(count)


### FIXED CODE ###

import re
import sys

line = next(map(str.strip, sys.stdin))

count = 0
nb_bs = 0
for i, c in enumerate(line):
    if c == 'W' and nb_bs > 0:
        count += nb_bs
    elif c == 'B':
        nb_bs += 1

print(count)
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())

    g = [list("#" * (w + 2))]
    for _ in range(h):
        g.append(["#"] + list(input()) + ["#"])
    g += [list("#" * (w + 2))]

    DX = [0, 1, 0, -1]
    DY = [1, 0, -1, 0]

    #print(*g, sep="\n")


    def cnt_dot(k, l):
        if g[k][l] == ".":
            cnt = 1
            for dx, dy in zip(DX, DY):
                x, y = k + dx, l + dy
                while g[x][y] == ".":
                    cnt += 1
                    x, y = x + dx, y + dy
            return cnt
        else:
            return 0


    res = 0
    for i in range(h + 2):
        for j in range(w + 2):
            res = max(res, cnt_dot(i, j))
    print(res)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    h, w = map(int, input().split())

    g = [list("#" * (w + 2))]
    for _ in range(h):
        g.append(["#"] + list(input()) + ["#"])
    g += [list("#" * (w + 2))]
    area = [[0] * (w + 2) for _ in range(h + 2)]

    for i in range(h + 2):
        cnt = 0
        for j in range(w + 2):
            if g[i][j] == "#":
                for k in range(j - cnt, j):
                    area[i][k] += cnt
                cnt = 0
            else:
                cnt += 1

    for i in range(w + 2):
        cnt = 0
        for j in range(h + 2):
            if g[j][i] == "#":
                for k in range(j - cnt, j):
                    area[k][i] += cnt
                cnt = 0
            else:
                cnt += 1

    res = 0
    for i in range(h + 2):
        for j in range(w + 2):
            res = max(res, area[i][j])
    print(res - 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
N = int(input())
ListA = list(map(int,input().split()))
Maxcomb = 0
Maxij = []
for i in range(N):
    for j in range(N):
        if ListA[i]<ListA[j] or i==j:
            continue
        else:
            Comb = (math.factorial(ListA[i])//(math.factorial(ListA[i]-ListA[j])*math.factorial(ListA[j])))
            if Maxcomb<Comb:
                Maxij = [ListA[i],ListA[j]]
                Maxcomb = max(Comb,Maxcomb)

print(Maxij[0],Maxij[1])


### FIXED CODE ###

import math
N = int(input())
ListA = list(map(int,input().split()))
ListA.sort()
Minj = 10e8
Maxj = ListA[-1]

for j in range(N-1):
    if abs(ListA[j]*2-ListA[-1])<Minj:
        Maxj = ListA[j]
        Minj = min(abs(ListA[j]*2-ListA[-1]),Minj)

    else:
        continue


print(ListA[-1],Maxj)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.9 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

aa = list(reversed(A))

cnt = 0
for i in range(0,N):
    if aa[i] == min(aa[i:]):
        cnt += 1
print(cnt)



### FIXED CODE ###

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

m = A[0]
cnt = 1
for i in range(1,N):
    m = min(m, A[i])
    if A[i] <= m:
        cnt += 1
print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
li = [(int(j) + 1) / 2 for j in input().split()]

if k == 1:
  print(max(li))
else:
  li2 = [sum(li[m:m+k]) for m in range(0, len(li) - k + 1, 1)]
  print(max(li2))

### FIXED CODE ###

n, k = map(int, input().split())
li = [(int(j) + 1) / 2 for j in input().split()]

if k == 1:
  print(max(li))
else:
  a = 0
  for i in range(n-k+1):
    if i == 0:
      xe = sum(li[0:k])
    else:
      xe = xe - li[i-1] + li[i+k-1]
    a = max(a, xe)
  print(a)
### BUGGY CODE ###

import re
S = input()
ans = 0
a = len(S)
while True:
    S = re.sub('01|10', '', S)
    if ans - len(S) == 0:
        print(a-ans)
        break
    else:
        ans = len(S)



### FIXED CODE ###

import re
S = input()
print(2*min(S.count('0'), S.count('1')))
### BUGGY CODE ###

import collections
import math
from copy import deepcopy

def func(n):
    ans = math.factorial(n)//((math.factorial(n-2))*math.factorial(2))
    return ans

N = int(input())
a = input().split()

for j in range(N):
    sums = 0
    a1 = deepcopy(a)
    del a1[j]
    ans = dict(collections.Counter(a1))
    for i in ans.values():
        if i < 2:
            continue
        else:
            sums += func(i)
    print(sums)
    #print(a1)
    #print(ans)

### FIXED CODE ###

import collections
import math

def func(n):
    ans = math.factorial(n)//((math.factorial(n-2))*math.factorial(2))
    return ans

N = int(input())
a = input().split()
ans = dict(collections.Counter(a))
sums = 0
for i in ans.values():
        if i < 2:
            continue
        else:
            sums += func(i)
            
for j in range(N):  
    print(sums-(ans[a[j]]-1))
### BUGGY CODE ###

import numpy as np

n = int(input())
a = list(map(int, input().split()))

MOD = 10**9 + 7

# format関数で10進数から2進数に変換
max_digits = len(format(max(a), 'b'))  # 最大桁数

# 各位の1の数を記録していく
counter = []
for i in range(n):
    counter.append(list(format(a[i], 'b').zfill(max_digits))[::-1])  # 逆順にする 
cnt_arr = np.array(counter, dtype='int')

ans = 0
n_mod = n % MOD
for i in range(max_digits):
    # 各位ごとの合計は2**k × 1の数 × 0の数
    one_num = np.count_nonzero(cnt_arr[:, i]) % MOD
    ans += (2**i * one_num * (n_mod - one_num)) % MOD
print(ans % MOD)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

max_digits = 60
MOD = 10**9 + 7

ans = 0
for i in range(max_digits):
    one_num = np.count_nonzero((a >> i) & 1)
    radix_mod = 2**i % MOD
    ans += (radix_mod * one_num * (n - one_num)) % MOD
print(ans%MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
list = []
list.append(n)
a = 0
while True:
  n = abs(n - k)
  if list[a] < n:
    n = list[a]
    break
  else:
  	list.append(n)
  a += 1

print(n)

### FIXED CODE ###

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

n = n % k

print(min(n, abs(n - k)))
### BUGGY CODE ###

import bisect

N = int(input())
parts = [[] for i in range(3)]
con = [0] * N

ans = 0

for i in range(3):
  t = sorted(list(map(int,input().split())))
  parts[i] = t

under =parts[2]
middle = parts[1]
upper = parts[0]

for i in range(N):
  p = middle[i]
  q = bisect.bisect_left(upper,p)
  con[i] += q


for i in range(N):
  p = under[i]
  q = bisect.bisect_left(middle,p)
  ans += sum(con[:q])
    
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
parts = [[] for i in range(3)]
con = [0] * N

ans = 0

for i in range(3):
  t = sorted(list(map(int,input().split())))
  parts[i] = t

under =parts[2]
middle = parts[1]
upper = parts[0]

for i in range(N):
  p = middle[i]
  ans += bisect.bisect_left(upper,p) * (N - bisect.bisect_right(under,p))
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    rest_r = []
    rest_g = []
    rest_b = []

    c_r = 0
    c_g = 0
    c_b = 0

    i_r = []
    i_g = []
    i_b = []

    for i in range(N-1, -1, -1):
        if S[i] == 'R':
            c_r+=1
            i_r.append(i)
        if S[i] == 'G':
            c_g+=1
            i_g.append(i)
        if S[i] == 'B':
            c_b+=1
            i_b.append(i)
        rest_r.append(c_r)
        rest_g.append(c_g)
        rest_b.append(c_b)

    rest_r.reverse()
    rest_g.reverse()
    rest_b.reverse()

    i_r.reverse()
    i_g.reverse()
    i_b.reverse()

    sum = 0

    # r, g, b
    for r in i_r:
        for g in i_g:
            i_max = max(r, g)
            sum += rest_b[i_max]
            if (i_max + abs(g - r)) in i_b:
                sum -= 1

    for r in i_r:
        for g in i_b:
            i_max = max(r, g)
            sum += rest_g[i_max]
            if (i_max + abs(g - r)) in i_g:
                sum -= 1

    for r in i_g:
        for g in i_b:
            i_max = max(r, g)
            sum += rest_r[i_max]
            if (i_max + abs(g - r)) in i_r:
                sum -= 1

    print(sum)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    rest_r = []
    rest_g = []
    rest_b = []

    c_r = 0
    c_g = 0
    c_b = 0

    i_r = []
    i_g = []
    i_b = []

    for i in range(N-1, -1, -1):
        if S[i] == 'R':
            c_r+=1
            i_r.append(i)
        if S[i] == 'G':
            c_g+=1
            i_g.append(i)
        if S[i] == 'B':
            c_b+=1
            i_b.append(i)
        rest_r.append(c_r)
        rest_g.append(c_g)
        rest_b.append(c_b)

    rest_r.reverse()
    rest_g.reverse()
    rest_b.reverse()

    i_r.reverse()
    i_g.reverse()
    i_b.reverse()

    sum = 0

    # r, g, b
    for r in i_r:
        for g in i_g:
            i_max = max(r, g)
            sum += rest_b[i_max]
            i = i_max + abs(g - r)
            if i < N and S[i] == 'B':
                sum -= 1
    for r in i_r:
        for g in i_b:
            i_max = max(r, g)
            sum += rest_g[i_max]
            i = i_max + abs(g - r)
            if i < N and S[i] == 'G':
                sum -= 1

    for r in i_g:
        for g in i_b:
            i_max = max(r, g)
            sum += rest_r[i_max]
            i = i_max + abs(g - r)
            if i < N and S[i] == 'R':
                sum -= 1

    print(sum)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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

def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    #c = [[0 for j in range(len(Y))] for i in range(len(X))]
    c = [[0] * len(Y) for i in range(len(X))]
    maxl = 0
    
    for i in range(1,len(X)):
        for j in range(1,len(Y)):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(raw_input())
 
for i in range(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)

### FIXED CODE ###

def lcs(X, Y):
    #X = " " + X
    #Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c2 = [0 for i in xrange(len(Y) + 1)]
    #maxl = 0
     
    for i in xrange(len(X)):
        c1 = c2 + []
        for j in xrange(len(Y)):
            if X[i] == Y[j]:
                c2[j + 1] = c1[j] + 1
            elif c2[j + 1] < c2[j]:
                c2[j + 1] = c2[j]
    return c2[-1]
n = int(raw_input())
  
for i in xrange(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)
### BUGGY CODE ###

tmp = input().rstrip().split()
N = int(tmp[0])

list = [[] for x in range(100000)]
count = [0]*100000

for  i in range(N):
    work = input().rstrip().split()
    for i in range(int(work[0]),int(work[1])+1):
        if int(work[2]) not in list[i-1]:
            list[i-1].append(int(work[2]))
            count[i-1] += 1
            
print(max(count))

### FIXED CODE ###

N,C = map(int,input().split())
tvs = [list(map(int,input().split())) for _ in range(N)]
chans = [[] for _ in range(C+1)]
tvs.sort(key=lambda x:x[0])
targets = []
times = [0]*(pow(10,5)+2)

for tv in tvs:
  chans[tv[2]].append([tv[0],tv[1]])

for chan in chans:
  tmp = []
  if len(chan) == 1:
    targets.append(chan[0])
    continue
  for x in range(len(chan)):
    if len(tmp) == 0:
      tmp = chan[x]
      continue
    if chan[x][0] <= tmp[1] + 1:
      tmp[1] = chan[x][1]
      if x == len(chan)-1:
        targets.append(tmp)
    else:
      targets.append(tmp)
      tmp = chan[x]

for target in targets:
  times[target[0]] += 1
  times[target[1]+1] += -1

for j in range(1,pow(10,5)+2):
  times[j] += times[j-1]

print(max(times))
### BUGGY CODE ###

import itertools
n, k = (int(i) for i in input().split())
l = list(int(j) for j in input().split())
ans = 0
for i in itertools.combinations(l, k):
    if sum(i) > ans:
        ans = sum(i)
print(ans)


### FIXED CODE ###

n, k = (int(i) for i in input().split())
l = list(int(j) for j in input().split())
ans = 0
for i in range(k):
    ans += max(l)
    l.remove(max(l))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
m = [[-1 for _ in range(n)] for _ in range(n)]
np = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[a-1][b-1] = c
    m[b-1][a-1] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[cur-1][p-1]
        dfs(p, cur, master)

dfs(k, -1, master)

for _ in range(q):
    x, y = [int(x) for x in input().strip().split()]
    print(master[x-1] + master[y-1])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n = int(input())
m = {}
np = [deque([]) for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[(a, b)] = c
    m[(b, a)] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[(cur, p)]
        dfs(p, cur, master)

dfs(k, -1, master)

for _ in range(q):
    x, y = [int(x) for x in input().strip().split()]
    print(master[x-1] + master[y-1])
### BUGGY CODE ###

n = int(input())
h = [int(i) for i in input().split()]
ans =  True
for i in range(n-1):
    for j in range(i,n):
        if h[i]-1 > h[j]:
            ans = False
if ans == True:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
ans =  True
maxv = h[0]
for i in range(n-1):
        if h[i] > h[i+1]:
            if maxv-h[i+1] >= 2:
                ans = False
        elif maxv < h[i+1]:
            maxv = h[i+1]
if ans == True:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def main():
    n = int(input())
    a_list = list(map(int,input().split()))
    a = 0
    end = 0
    for i in range(n):
        if i%2 == 0:
            a += a_list[i]*0.5
        else:
            a -= a_list[i]*0.5

    out = str(int(a*2))
    point = a
    for i in range(n-1):
        point = a_list[i]-point
        out += " "+str(int(point*2))
    print(out)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a_list = list(map(int,input().split()))
    a = 0
    end = 0
    for i in range(n):
        if i%2 == 0:
            a += a_list[i]*0.5
        else:
            a -= a_list[i]*0.5

    out = str(int(a*2))
    point = a
    for i in range(n-1):
        point = a_list[i]-point
        out += " "+str(int(point*2))
    print(out)

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

n = int(input())
a = list(map(int, input().split()))

dp = [1]*(max(a)+1)

for i in sorted(a):
  if 2 == dp[i]:
    continue
  if 3 == dp[i]:
    dp[i] = 2
    continue
  dp[i] = 3
  for j in range(2, max(a)//i + 1):
    dp[j * i] = 2

ans=0
for i in a:
  if dp[i] != 2:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ma = max(a)
dp = [0]*(ma+1)

for i in sorted(a):
  if 1 <= dp[i]:
    dp[i] += 1
    continue

  for j in range(1, ma//i + 1):
    dp[j * i] += 1

ans=0
for i in a:
  if dp[i] == 1:
    ans += 1
print(ans)