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

import sys
input=sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())

    d = {i:set() for i in range(1, N+1)}
    block = {i:set() for i in range(1, N+1)}
    candidate = {i:set() for i in range(1, N+1)}

    uft = UnionFind(N)

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        block[C].add(D)
        block[D].add(C)

    for i in range(1, N+1):
        cd = set(range(1, N+1))-d[i]
        for j in cd:
            if i>=j:continue
            if uft.isunited(i, j) and not j in block[i]:
                candidate[i].add(j)
                candidate[j].add(i)

    print(*map(len, candidate.values()))


if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys
input=sys.stdin.readline


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


def solve():
    N, M, K = map(int, input().split())
    uft = UnionFind(N)
    d = {i:set() for i in range(1, N+1)}
    e = {i:0 for i in range(1, N+1)}
    f = {i:0 for i in range(1, N+1)}

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        f[A] += 1
        f[B] += 1
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        if uft.isunited(C, D):
            if not D in d[C]:
                e[C] += 1
            if not C in d[D]:
                e[D] += 1

    print(*(uft.getsize(i)-e[i]-f[i]-1 for i in range(1, N+1)))


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

from collections import deque
import bisect

n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
l, r = deque([b[1]]), deque(b[3 : n])
lenl, lenr = len(l), len(r)
ans = 1145141919810
for i in range(2, n - 1):
    cl, cr = b[i] / 2, (b[n] - b[i]) / 2
    ml = bisect.bisect_left(l, cl)
    mr = bisect.bisect_left(r, cr + b[i])
    if ml == 0:
        x = b[1]
    elif ml == lenl:
        x = l[-1]
    else:
        if l[ml] - cl <= cl - l[ml - 1]:
            x = l[ml]
        else:
            x = l[ml - 1]
    if mr == 0:
        y = r[0]
    elif mr == lenr:
        y = b[-2]
    else:
        if r[mr] - (cr + b[i]) <= (cr + b[i]) - r[mr - 1]:
            y = r[mr]
        else:
            y = r[mr - 1]
    s = [x, b[i] - x, y - b[i], b[n] - y]
    ans = min(ans, max(s) - min(s))
    l.append(b[i])
    r.popleft()
    lenl += 1
    lenr -= 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = b[i] + a[i]
x = [[0, 0] for _ in range(n - 3)]
j = 1
for i in range(2, n - 1):
    while True:
        if i == j + 1:
            x[i - 2][0] = b[j]
            break
        if abs(b[i] - 2 * b[j]) > abs(b[i] - 2 * b[j + 1]):
            j += 1
        else:
            x[i - 2][0] = b[j]
            break
j = n - 1
for i in range(n - 2, 1, -1):
    while True:
        if i == j - 1:
            x[i - 2][1] = b[j]
            break
        if abs(b[n] + b[i] - 2 * b[j]) > abs(b[n] + b[i] - 2 * b[j - 1]):
            j -= 1
        else:
            x[i - 2][1] = b[j]
            break
ans = 1145141919810
for i in range(n - 3):
    s = [x[i][0], b[i + 2] - x[i][0], x[i][1] - b[i + 2], b[n] - x[i][1]]
    ans = min(ans, max(s) - min(s))
print(ans)
### BUGGY CODE ###

from collections import defaultdict
#from functools import lru_cache
import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = []
    R = []
    for i, a in enumerate(A):
        L.append(i+a)
        R.append(i-a)
    #print(L)
    #print(R)
    L_t = defaultdict(list)
    for i, l in enumerate(L):
        L_t[l].append(i)
    R_t = defaultdict(list)
    for j, r in enumerate(R):
        R_t[r].append(j)

    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        if len(l_candidate) == 0 or len(r_candidate) == 0:
            continue
        else:
            cnt += len(l_candidate) * len(r_candidate)
            #answer_set = set()
            #print(x)
            #print(l_candidate)
            #print(r_candidate)
            #for i,j in itertools.product(l_candidate, r_candidate):
            #    answer_set.add((i,j))
            #cnt += len(answer_set)

    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#解説を見て実装
from collections import Counter

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)

    #はじめL_t = defaultdict(list)としてiの候補を追加していったが、iとjは重複しないのでチェックが不要
    L_t = Counter(L)
    R_t = Counter(R)
    cnt = 0
    x_candidate = set(L) & set(R)
    for x in x_candidate:
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        cnt += l_candidate * r_candidate

    print(cnt)

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

n = int(input())
a = []

for i in range(n):
    x = int(input())
    if x not in a:
        a.append(x)
    else:
        a.remove(x)

print(len(a))

### FIXED CODE ###

n = int(input())
a = sorted([int(input()) for _ in range(n)])
ans = 0
count = 0
pre = a[0]

for i in range(n):
    if a[i] == pre:
        count+=1
    else:
        pre = a[i]
        if count%2 == 1:
            ans += 1
        count = 1
if count%2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

# ABC 118 D

def resolve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)

    costs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

    dp = [0] * (N+1)
    for i in range(1, N+1):
        for a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    while match > 0:
        for a in A:
            if match - costs[a] < 0 or match - costs[a] == 1:
                continue

            if dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

# ABC 118 D

def resolve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)

    costs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

    dp = [-1] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        for a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    minCosts = 10
    for a in A:
        minCosts = min(minCosts, costs[a])

    while match > 0:
        for a in A:
            if match - costs[a] < 0 or 1<= match - costs[a] < minCosts:
                continue

            if dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


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

#gが目標点数
d,g=map(int,input().split())

cnt=10*1000+1
numberOfMondai=0
KindOfMondai = {}
kindOfMondaiBin=""
zero=""

for i in range(1,d+1):
    c,p=map(int,input().split())
    if c>1:
        for j in range(c):
            KindOfMondai[zero+"0"*(c-j-1)+"1"+"0"*(j)]=i*100
    else:
        KindOfMondai[zero+"1"]=i*100
    kindOfMondaiBin=zero+"1"*c
    zero=zero+"0"*c
    KindOfMondai[kindOfMondaiBin]=p
    numberOfMondai+=c

KindOfMondaiZero={}
for key in KindOfMondai.keys():
    KindOfMondaiZero[int(key+"0"*(numberOfMondai-len(key)),2)]=KindOfMondai[key]

#print(KindOfMondaiZero)

number=10**9
for i in range(2**numberOfMondai):
    point=0

    for key in KindOfMondaiZero.keys():
        if (key&i)==key:
            point+=KindOfMondaiZero[key]
    #print(bin(i),point)

    if point>=g:
        number=min(number,bin(i).count("1"))

print(number)







### FIXED CODE ###

from collections import defaultdict

d, g = map(int, input().split())

scores = []

for i in range(1, d + 1):
    p, c = map(int, input().split())
    scores.append([100 * i, p, c])


result = 10 ** 9
#print(scores)
n = 2 ** d
for i in range(n):
    #print(bin(i))
    cnt = 0
    point = 0
    memo = -1
    for j in range(d):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            point += scores[j][0] * scores[j][1] + scores[j][2]
            cnt += scores[j][1]
        else:
            memo = j

    #print(memo)
    if point >= g:
        result = min(result, cnt)
    else:
        if memo > -1:
            for k in range(scores[memo][1] - 1):
                cnt += 1
                point += scores[memo][0]
                if point >= g:
                    result = min(result, cnt)
                    break

print(result)
### BUGGY CODE ###

s = input()

s = s[::-1]

dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]

l = len(s)


if s[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1

m = 1
MOD = 10**9 +7

for i in range(1,len(s)):
    m = m*10 % 13

    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
                dp[i-1][k] % MOD
    else:
        for k in range(13):
            dp[i][(int(s[i])*m + k) %13] += dp[i-1][k]
            dp[i-1][k] % MOD

print(dp[len(s)-1][5] % MOD )

### FIXED CODE ###

s = input()
 
s = s[::-1]
 
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
 
l = len(s)
 
 
if s[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1
 
m = 1
MOD = 10**9 +7
 
for i in range(1,len(s)):
    m = m*10 % 13
 
    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
                dp[i][k] %= MOD
    else:
        for k in range(13):
            dp[i][(int(s[i])*m + k) %13] += dp[i-1][k]
            dp[i][k] %= MOD
 
print(dp[len(s)-1][5] % MOD )
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=0
min_a=min(a)
for i in range(N-1,0,-1):
    num=a[i]
    for j in range(max(i-num+1-min_a,0)):
        if a[j]+num==i-j:
            ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=0
L={}
R={}
for i in range(N):
    if a[i]+i in L:
         k=L.get(a[i]+i)
         del L[a[i]+i]
         L[a[i]+i]=k+1
    else:
        L[a[i]+i]=1
    if i-a[i]>0:
        if i-a[i] in R:
             k=R.get(i-a[i])
             del R[i-a[i]]
             R[i-a[i]]=k+1
        else:
            R[i-a[i]]=1
for x in L.keys():
    if x in R:
        ans+=L.get(x)*R.get(x)
print(ans)
### BUGGY CODE ###

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
for i in range(t+1):
  if a<b:
    a+=v
    b+=w
    if a==b:
      print("YES")
      break
  else:
    a-=v
    b-=w
    if a==b:
      print("YES")
      break
else:
  print("NO")

### FIXED CODE ###

import math
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if v>w and abs(a-b)/(v-w)<=t:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

N = int(input())
S = input()
 
lis = [0 for _ in range(1000)]
 
for i in range(N-2):
  for j in range(i+1, N-1):
    for k in range(j+1, N):
      lis[100*int(S[i])+10*int(S[j])+int(S[k])] = 1
      
print(sum(lis))

### FIXED CODE ###

N = int(input())
S = input()
numbers=[str(i).zfill(3) for i in range(1000)]
 
count=0
for num in numbers:
  j=0
  for i in range(N):
    if num[j]==S[i]:
      j+=1
      if j==3:
        count+=1
        break
print(count)
### BUGGY CODE ###

k = int(input())
s = 7
num = 1
if k == 2:
    print(-1)
else:
    while 1:
        s %= k
        if s == 0:
            print(num)
            break
        num += 1
        s *= 10
        s += 7


### FIXED CODE ###

k = int(input())
s = 7
num = 1
res = True
if k == 2:
    print(-1)
else:
    for i in range(k):
        s %= k
        if s == 0:
            res = False
            print(num)
            break
        num += 1
        s *= 10
        s += 7
    if res:
        print(-1)
### BUGGY CODE ###

N = int(input())
R = [tuple(map(int, input().split())) for _ in range(N)]
B = [tuple(map(int, input().split())) for _ in range(N)]


def check(v, p):
    return p & (1 << v)


def visit(v, p):
    return p ^ (1 << v)


def count(p):
    return bin(p).count('1')


def solve(i, p):
    if i == N:
        return count(p)

    a, b = R[i]
    # ペアにならなかった
    m = solve(i+1, p)
    for j, (c, d) in enumerate(B):
        # すでにペアを持つ要素は無視
        if check(j, p):
            continue
        # ペアになった
        if a < c and b < d:
            m = max(m, solve(i+1, visit(j, p)))
    return m


print(solve(0, 0))


### FIXED CODE ###

N = int(input())
R = [tuple(map(int, input().split())) for _ in range(N)]
B = [tuple(map(int, input().split())) for _ in range(N)]


R.sort(reverse=True, key=lambda k: k[1])
B.sort()

p = []
q = []
for c, d in B:
    for a, b in R:
        if (a, b) in p:
            continue
        if a < c and b < d:
            p.append((a, b))
            q.append((c, d))
            break

print(len(p))
### BUGGY CODE ###

N = int(input())
XYH = [list(map(int, input().split())) for _ in range(N)]
H_max = max([XYH[i][2] for i in range(N)])

ans = []

# 高さH,中心座標を(Cx, Cy)として総当たりで試す
for H in range(H_max - 200, H_max + 201):
    for Cx in range(0, 101):
        for Cy in range(0, 101):
            count = 0
            for X, Y, h in XYH:
                if h == max(H - abs(X - Cx) - abs(Y - Cy), 0):
                    count += 1
                else:
                    break

            if count == N:
                ans = [str(Cx), str(Cy), str(H)]

print(' '.join(ans))



### FIXED CODE ###

N = int(input())
XYH = [list(map(int, input().split())) for _ in range(N)]
H_list= [XYH[i][2] for i in range(N)]
H_max = max(H_list)
H_min = min(H_list)
H_diff = H_max - H_min
ans = []

# 高さH,中心座標を(Cx, Cy)として総当たりで試す
for H in range(H_max - (200 - H_diff), H_max + (201 - H_diff)):
    for Cx in range(0, 101):
        for Cy in range(0, 101):
            count = 0
            for X, Y, h in XYH:
                if h == max(H - abs(X - Cx) - abs(Y - Cy), 0):
                    count += 1
                else:
                    break

            if count == N:
                ans = [str(Cx), str(Cy), str(H)]

print(' '.join(ans))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=input()
q=int(input())
kl=tuple(map(int,input().split()))
for k in kl:
    d=0
    m=0
    dm=0
    ans=0
    for j in range(n):
        if l[j]=='D':
            d+=1
        elif l[j]=='M':
            m+=1
            dm+=d
        elif l[j]=='C':
            ans+=dm
        if j>=k-1:
            if l[j-k+1]=='D':
                dm-=m
                d-=1
            elif l[j-k+1]=='M':
                m-=1
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
    ans.append(str(a.index(i + 1) + 1))
print(' '.join(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [i for i in range(n)]
a1 = sorted(a)
for i in range(n):
    num = a[i]
    ans[num - 1] = str(i + 1)
    
print(' '.join(ans))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

ans = 0
for l in range(N):
    for r in range(l+1, N+1):
        if sum(A[l:r]) == 0:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]

d = defaultdict(int)

d[0] = 1
sum = 0
for i in range(N):
    sum += A[i]
    d[sum] += 1

ans = 0
for v in d.values():
    if v >= 2:
        ans += (v*(v-1))//2

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

N = int(input())
A = [0] * N
for i in range(N):
  A_temp = input()
  A[i]= sorted([c for c in A_temp])
count = 0

B = sorted(A)
A_unique_count = 1
for i in range(N-1):
  if B[i] != B[i+1]:
    A_unique_count += 1
#print(A_unique_count)
C = 0    
num = 0

#print(B)

for i in range(A_unique_count):
#  print( 'i' + str(i))
  C = B.count(B[num])
  num += C
#  print(num)
#  print(C)
  count += C * (C -1 ) / 2

print(int(count))
  

### FIXED CODE ###

N = int(input())
A = [0] * N
for i in range(N):
  A_temp = input()
  A[i]= sorted([c for c in A_temp])
count = 0

B = sorted(A)
A_unique_count = 1

for i in range(N-1):
  if B[i] == B[i+1]:
    A_unique_count += 1
  else:
    count += A_unique_count * (A_unique_count -1) /2
#    print('i' + str(i))
#    print(count)
    A_unique_count = 1

count += A_unique_count * (A_unique_count -1) /2
print(int(count))
### BUGGY CODE ###

def back(p, N, M):
    x, y = p
    if x == 0 and x == (N - 1) and y == 0 and y == (M - 1):
        return True

    if x == 0 and x == (N - 1) and (y == 0 or y == (M - 1)):
        return False

    if (x == 0 or x == (N - 1)) and y == 0 and y == (M - 1):
        return False

    if x == 0 and x == (N - 1):
        return True

    if y == 0 and y == (M - 1):
        return True

    if x == 0:
        return False

    if x == (N - 1):
        return False

    if y == 0:
        return False

    if y == (M - 1):
        return False

    return True



N, M = [int(i) for i in input().split()]

print(len([p for p in [[i, j] for i in range(N) for j in range(M)] if back(p, N, M)]))


### FIXED CODE ###

N, M = [int(i) for i in input().split()]

if N == 1 and M == 1:
    print(1)
elif N == 1:
    print(M - 2)
elif M == 1:
    print(N - 2)
else:
    print(N * M - ((N - 2) * 2 + (M - 2) * 2) - 4)
### BUGGY CODE ###

N,K,C=map(int,input().split())
S=list(input())

#まず一つ答えをつくる これはたぶん貪欲でいける
days=[]
T=S.copy()
for i in range(N):
    if T[i]=='o':
        days.append(i)
        if C!=0:
            for j in range(1,C+1):
                if i+j>=N:
                    break
                T[i+j]='x'
    if len(days)>=K:
        break

def check(plan):
    cnt=0
    qlan=plan.copy()
    for i in range(N):
        if qlan[i]=='o':
            cnt+=1
            if C!=0:
                for j in range(1,C+1):
                    if i+j>=N:
                        break
                    qlan[i+j]='x'
        if cnt>=K:
            return True  #これなしでも成立する
            break
    return False  #これなしでは成立しない

for i in days:
    p=S
    p[i]='x'
    if not check(p):
        print(i+1)
    p[i]='o'


### FIXED CODE ###

N,K,C=map(int,input().split())
S=input()

maekara=[]
i=1
cnt=0
while i<=N and cnt<K:
    if S[i-1]=='o':
        maekara.append(i)
        i+=C+1
        cnt+=1
    else: i+=1

usirokara=[]
j=N
cnt=0
while j>=1 and cnt<K:
    if S[j-1]=='o':
        usirokara.append(j)
        j-=C+1
        cnt+=1
    else: j-=1
usirokara=usirokara[::-1]

for i in range(K):
    if maekara[i]==usirokara[i]:
        print(maekara[i])
### BUGGY CODE ###

import bisect

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


fathers = [a.pop()]
for _ in range(N):
    sons = list()
    for father in fathers:
        son = a.pop(bisect.bisect_left(a,father)-1)
        
        if son >= father:
            pass
        else:
            sons.append(son)

    fathers.extend(sons)
    
if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
A = sorted((int(x) for x in input().split()))
 
parent = [A[-1]]
rest = A[:-1]
bl = True
for _ in range(N):
    next_parent = []
    next_rest = []
    for p in parent[::-1]:
        while rest:
            x = rest.pop()
            if x < p:
                next_parent.append(x)
                break
            else:
                next_rest.append(x)
                continue
    parent += next_parent
    parent.sort()
    rest = rest + next_rest[::-1]
 
bl = len(parent) == (2**N)
answer = 'Yes' if bl else 'No'
print(answer)
### BUGGY CODE ###

import queue

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

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

Q, K = map(int, input().split())
K -= 1

depth = [0 for _ in range(N)]

def bfs(v, p = -1, d = 0):
    q = queue.Queue()
    q.put([v, p, d])
    while not q.empty():
        cur = q.get()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.put([i, cur[0], cur[2] + j])

bfs(K)

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print (depth[x] + depth[y])

### FIXED CODE ###

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

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

Q, K = map(int, input().split())
K -= 1

depth = [0 for _ in range(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    # 空のシーケンスは偽になる
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

for i in range(Q):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    print (depth[x] + depth[y])
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]

if 1 in a:
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if i in a:
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = fibs[1] + fibs[0]
    if next > 1000000007:
      next -= 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])

### FIXED CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
a.sort(reverse=True)

if 1 in a:
  a.pop()
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if len(a) > 0 and i == a[-1]:
    a.pop()
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = fibs[1] + fibs[0]
    if next > 1000000007:
      next -= 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])