Harryxun/stf_run huggingface dataset:
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y+1,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=map(int,input().split())
  print(max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]))
if'__main__'==__name__:s()


### FIXED CODE ###

def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):
   P[i+1][1:-1]=map(int,input().split())
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()
k=list(map(int,input().split().strip()))
kk=max(k)
k.remove(kk)
print(sum(k))

### FIXED CODE ###

a=[int(n) for n in input().split()]
a.sort()
print(a[0]+a[1])
t[i] == '?' and t[i+1] == 'D':

### FIXED CODE ###

t= list(input())
if t[-1] == '?':
  t[-1] = 'D'

if t[0] == '?':
  if t[1] == 'D':
    t[0] = 'P'
  elif t[1] == 'P':
    t[0] = 'D'
  else:
    t[0] = 'P'
    t[1] = 'D'

for i in range(1, len(t)-1):
  if t[i] == '?':
    if t[i-1] == 'P':
      t[i] = 'D'
    elif t[i-1] == 'D':
      if t[i+1] == 'P':
        t[i] = 'D'
      elif t[i+1] == 'D':
        t[i] = 'P'
      else:
        t[i] = 'P'
        t[i+1] = 'D'
    
    
print(''.join(t))
import sys
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
xy = []
for _ in range(q):
  x, y = map(int, input().split())
  xy.append((x, y))

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    try:
      if i==p_node:
        continue
    except TypeError:
      sys.exit(0)
    DFS(i, node, length+j)

DFS(k, -1, 0)
for x, y in xy:
  print(l[x]+l[y])

### FIXED CODE ###

import sys
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a-=1
    b-=1
    graph[a].append((b, c))
    graph[b].append((a, c))
q, k = map(int, input().split())
k -= 1
xy = []
for _ in range(q):
    x, y = map(int, input().split())
    x-=1
    y-=1
    xy.append((x, y))

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * n)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])
N = int(input())
import numpy
div = np.zeros(N+1, np.int64)
for n in range(1, N+1):
  for m in range(n, N+1, n):
    div[m] += m
print(sum(div))

### FIXED CODE ###

n = int(input())
res = 0
for i in range(1, n + 1):
  d = n // i
  res += d * (d + 1) // 2 * i
print(res)
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    if q<0 or q>=n:
        b=1
        while True:
            b+=1

    while p<n and a[q]+a[p]<=md:
        p+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)


### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
n = int(input())
t, a = list(map(int, input().split(' ')))
hs = list(map(int, input().split(' ')))

diff_a = list(map(lambda h: int(abs(a - t + h * 0.006)), hs))
ans = 100_000
result = -1
for i in range(n):
    if diff_a[i] <= ans:
        result = i + 1
        ans = diff_a[i]

print(result)


### FIXED CODE ###

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

def get_dif(h):
    temp = t - h * 0.006
    dif = abs(temp - a)
    return dif

result = hn.index(min(hn, key=get_dif)) + 1
print(result)
a,b,k=map(int,input().split(' '))
if(a>k):
    a=a-k
elif (a<=k):
    aa=0
    b=max(b+a-k,0)
print(str(aa)+' '+str(b))

### FIXED CODE ###

a,b,k=map(int,input().split(' '))
if(a>k):
    aa=a-k
elif (a<=k):
    aa=0
    b=max(b+a-k,0)
print(str(aa)+' '+str(b))
a,b = map(int, input.split())

print(a * b)

### FIXED CODE ###

a,b = map(int, input().split())

print(a * b)
import sys
sys.setrecursionlimit(5000)
n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)
dp = [-1] * (2*10**5+1)
def f(n):
    if dp[n] > 0:
        return dp[n]
    pc = bin(n).count('1')
    nn = n%pc
    if nn == 0:
        return 1

    dp[n] = f(nn) + 1
    return dp[n]

for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまりi**2を引く
    tmp = pow(2, i)
    if (nx>>i)&1:
        nx -= tmp
        r = nx%(pc-1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
        nx += tmp
    else:
        nx += tmp
        r = nx%(pc+1)
        if r > 0:
            print(f(r) + 1)
        else:
            print(1)
        nx -= tmp

### FIXED CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n %= bin(n).count('1')
        c += 1
    return c

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)
#!/usr/bin/env python3

from itertools import product

def get_label(labels, target):
    if labels[target] == -1:
        return target
    else:
        temp = get_label(labels, labels[target])
        labels[target] = temp
        return temp


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]
    labels = [-1] * n
    groups = {}
    for i in range(n):
        groups[i] = 1

    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        label_a = get_label(labels, ai)
        label_b = get_label(labels, bi)
        if label_a != label_b:
            next_val = result[-1]
            next_val -= groups[label_a] * groups[label_b]
            result.append(next_val)
            groups[label_a] += groups[label_b]
            labels[label_b] = label_a
            del groups[label_b]
        else:
            result.append(result[-1])

    result.reverse()
    for v in result[1:]:
        print(v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from itertools import product
import sys
sys.setrecursionlimit(100000)

def get_label(labels, target):
    if labels[target] == -1:
        return target
    else:
        temp = get_label(labels, labels[target])
        labels[target] = temp
        return temp


def main():
    n, m = list(map(int, input().split()))
    a = []
    b = []
    for _ in range(m):
        ai, bi = list(map(int, input().split()))
        a.append(ai-1)
        b.append(bi-1)

    # 不便さのMAX
    result = [n * (n-1) // 2]
    labels = [-1] * n
    groups = {}
    for i in range(n):
        groups[i] = 1

    for j in range(m):
        i = m - 1 - j
        ai = a[i]
        bi = b[i]
        label_a = get_label(labels, ai)
        label_b = get_label(labels, bi)
        if label_a != label_b:
            next_val = result[-1]
            next_val -= groups[label_a] * groups[label_b]
            result.append(next_val)
            groups[label_a] += groups[label_b]
            labels[label_b] = label_a
            del groups[label_b]
        else:
            result.append(result[-1])

    result.reverse()
    for v in result[1:]:
        print(v)

if __name__ == '__main__':
    main()
s=input()
print(2*min(s.count("0"),mins.count("1")))


### FIXED CODE ###

s=input();print(min(s.count("0"),s.count("1"))*2)
import collections
N=int(input())
siritori=collections.defaultdict(int)
prev=""
for i in range(N):
  word = imput()
  if word in siritori:
    print("No")
  elif prev[-1]==word[0]:
    print("No")
  siritori[word]+=1
  prev=word
print("Yes")

### FIXED CODE ###

import collections
N=int(input())
siritori=collections.defaultdict(int)
prev=" "
for i in range(N):
  word = input()
  if word in siritori:
    print("No")
    exit(0)
  elif prev[-1]!=word[0] and i != 0:
    print("No")
    exit(0)
  siritori[word]+=1
  prev=word
print("Yes")
N=input()
S=input()
K=int(input())
W=S[K-1]
for i in range(N):
  if S[i]!=W:
    S=S.replace(S[i],'*')
print(S)

### FIXED CODE ###

N=int(input())
S=str(input())
K=int(input())
W=S[K-1]
for i in range(N):
  if S[i]!=W:
    S=S.replace(S[i],'*')
print(S)
a, b, c = mapt(int, input().split(" "))

print("Yes" if len(set({a,b,c})) == 2 else "No")

### FIXED CODE ###

a, b, c = map(int, input().split(" "))

print("Yes" if len(set({a,b,c})) == 2 else "No")
number = [int(i) for i in input().split()]
number.sort()
print(' '.join(number))



### FIXED CODE ###

number = [i for i in input().split()]
number.sort()
print(' '.join(number))
N = int(input())
As = list(map(int, input().split()))
sort_as = sorted(As)
shine = [x + 1 for x in range(N)]
c = 0
s = 0
j = 0
for x in range(N):
  for y in range(len(As)):
    if shine[x] == As[y]:
      c += 1
  print(c)
  c = 0
  if len(As) != 0:
    As.remove(shine[x])


### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
 
x = [0] * n
for i in As:
    x[i-1] += 1
for y in x:
    print(y)
c = input()
if c == "a", "i", "u", "e", "o":
  print("vowel")
else:
  print("consonant")

### FIXED CODE ###

c = input()
if c in ["a", "i", "u", "e", "o"]:
  print("vowel")
else:
  print("consonant")
from collections import defaultdict


def main():
    people_count, info_count = [int(x) for x in input().split()]
    frieds_circle_ids = [-1] * people_count
    id_counter = defaultdict(int)
    new_id = 0
    for _ in range(info_count):
        a, b = [int(x) - 1 for x in input().split()]
        id_a = frieds_circle_ids[a]
        id_b = frieds_circle_ids[b]
        if id_a == -1 == id_b:
            frieds_circle_ids[a] = new_id
            frieds_circle_ids[b] = new_id
            id_counter[new_id] += 2
            new_id += 1
        elif id_a == -1:
            frieds_circle_ids[a] = id_b
            id_counter[id_b] += 1
        elif id_b == -1:
            frieds_circle_ids[b] = id_a
            id_counter[id_a] += 1
        else:
            pass
    return max(count for count in id_counter.values())


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

from collections import deque, defaultdict


def main():
    people_count, info_count = [int(x) for x in input().split()]
    if info_count == 0:
        return 1
    if info_count == 1:
        return 2

    friends = [set() for _ in range(people_count)]
    for _ in range(info_count):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    seen = [False] * people_count
    circle_id = 0
    counter = defaultdict(int)
    for i, circle in enumerate(friends):
        if seen[i]:
            continue
        circle_id += 1
        qu = deque()
        qu.append(i)
        seen[i] == 1
        while qu:
            now = qu.popleft()
            for new in friends[now]:
                if seen[new]:
                    continue
                qu.append(new)
                seen[new] = True
                counter[circle_id] += 1
    return max(v for v in counter.values())


if __name__ == '__main__':
    print(main())
n=int(input())
A=list(map(int,input().split()))
print(abs((max(A)-min(A))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
print(abs(max(A)-min(A)))
N = int(input())
X = [int(x) for x in input().split()]
result = []
sum = 0
goal = round(mean(X))
for i in range(len(X)):
    sum += (X[i] - goal) ** 2
print(sum)


### FIXED CODE ###

from statistics import mean
N = int(input())
X = input().split()
for i in range(len(X)):
    X[i] = int(X[i])
goal = round(mean(X)) 
sum = 0
for i in range(len(X)):
    sum += (X[i] - goal) ** 2
print(sum)
N = int(input())
res = ""

for i in list(input()):
    ascii = ord(i)
    n = ascii - 65
    n = (n + N) % 26
    res += chr(n + 65)
print(res == input())

### FIXED CODE ###

N = int(input())
res = ""

for i in list(input()):
    ascii = ord(i)
    n = ascii - 65
    n = (n + N) % 26
    res += chr(n + 65)
print(res)
n, k  =map(int, input().split())

ans = 0
#ｋで割り切れるn以下の数のリスト
odd = [i for i in range(k, n+1, k)] #kから始まり、nまで、ｋ刻み
ans += len(odd) ** 3 #abcの選び方のため3乗

if k % 2 == 0:
  #k/2から始まり、nまでで、kで割ると余りがk/2になる
  even = [i ofr i in range(k//2, n+1, k)]
  ans += even
  
print(ans)


### FIXED CODE ###

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

ans = 0
#ｋで割り切れるn以下の数のリスト
odd = [i for i in range(k, n+1, k)] #kから始まり、nまで、ｋ刻み
ans += len(odd) ** 3 #abcの選び方のため3乗

if k % 2 == 0:
  #k/2から始まり、nまでで、kで割ると余りがk/2になる
  even = [i for i in range(k//2, n+1, k)]
  ans += len(even) ** 3
  
print(ans)
import bisect
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
point = bisect.bisect_right(a, 0)
a_minus = a[:point]
a_plus = a[point:]
len_plus = len(a_plus)
if len(a_minus) > 0:
    ans = sum(a_plus) - sum(a_minus)
    print(ans)
    for i in range(len(a_plus)):
        if i == 0:
            x = a_minus.pop(0)
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
        elif i == len_plus - 1:
            y = x - y
            x = a_plus.pop(0)
            print(str(x) + " " + str(y))
        else:
            x = x - y
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
    for j in range(len(a_minus)):
        x = x - y
        y = a_minus.pop(0)
        print(str(x) + ' ' + str(y))
else:
    ans = sum(a_plus) - ((a[0]) * 2)
    print(ans)
    for i in range(len(a_plus) - 1):
        if i == 0:
            x = a_plus.pop(0)
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
        elif i == len_plus - 2:
            y = x - y
            x = a_plus.pop(0)
            print(str(x) + " " + str(y))
        else:
            x = x - y
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))

### FIXED CODE ###

import bisect
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
point = bisect.bisect_right(a, 0)
a_minus = a[:point]
a_plus = a[point:]
len_plus = len(a_plus)
if (len(a_minus) > 0) & (len(a_plus) > 0):
    ans = sum(a_plus) - sum(a_minus)
    print(ans)
    for i in range(len(a_plus)):
        if len_plus == 1:
            x = a_plus.pop(0)
            y = a_minus.pop(0)
            print(str(x) + " " + str(y))
        elif (i == 0):
            x = a_minus.pop(0)
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
        elif i == len_plus - 1:
            y = x - y
            x = a_plus.pop(0)
            print(str(x) + " " + str(y))
        else:
            x = x - y
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
    for j in range(len(a_minus)):
        x = x - y
        y = a_minus.pop(0)
        print(str(x) + ' ' + str(y))
elif len(a_plus) > 0:
    ans = sum(a_plus) - ((a[0]) * 2)
    print(ans)
    for i in range(len(a_plus) - 1):
        if i == 0:
            x = a_plus.pop(0)
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
        elif i == len_plus - 2:
            y = x - y
            x = a_plus.pop(0)
            print(str(x) + " " + str(y))
        else:
            x = x - y
            y = a_plus.pop(0)
            print(str(x) + " " + str(y))
elif len(a_minus) > 0:
    ans = (a_minus[-1] * 2) - sum(a_minus)
    print(ans)
    for i in range(len(a_minus) - 1):
        if i == 0:
            x = a_minus[-1]
            y = a_minus.pop(0)
            print(str(x) + " " + str(y))
        elif i == len_plus - 2:
            x = x - y
            y = a_minus.pop(0)
            print(str(x) + " " + str(y))
        else:
            x = x - y
            y = a_minus.pop(0)
            print(str(x) + " " + str(y))
N = int(input())
print('ABC') if N / 999 <= 1 else print('ABD')

### FIXED CODE ###

a, b = input().split(' ')
a, b = int(a), int(b)
diff = b - a
a_orig = sum([i for i in range(1, diff)])
snow = a_orig - a
print(snow)
N = int(raw_input())
a = raw_input()
aa = a.split(" ")
aaa = []
for i in range(len(aa)):
	aaa.append((i+1,int(aa[i])))

ctr = 0

for (x,y) in aaa:
	if (y,x) in aaa:
		ctr = ctr + 1
		aaa.remove( (y,x) )
	aaa.remove((x,y))
print(str(ctr))

### FIXED CODE ###

s = raw_input()
s2 = s[:4] + " " + s[4:]
print(s2)
a,b,c=input().split()

if b=='+':
  print(a+c)
else:
  print(a-c)
  

### FIXED CODE ###

a,b,c=input().split(' ')

if b=='+':
  print(int(a)+int(c))
else:
  print(int(a)-int(c))
def main():
    N = int(input())
 
    if (N < 0 or N > 100):
            return 0
        array_len = len([N for i in range(1, N+1) if(i%2==1)])
        result = array_len / N
        return result
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    print((n+n%2)/2/n)

    
if __name__ == "__main__":
    main()
import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0][1]]
w_ans = [w_lst[0][1]]
s = 1
while h_lst[s][0] == Max_h:
  h_ans.append(h_lst[s][1])
  s+= 1   
t=1  
while w_lst[t][0] == Max_w:
  w_ans.append(w_lst[t][1])
  t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for j in h_ans:
  for k in w_ans:
    if (j,k) not in memo:
      print(Max_h+Max_w)
      sys.exit()
print((Max_h+Max_w)-1)        
  



### FIXED CODE ###

import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0][1]]
w_ans = [w_lst[0][1]]
if h != 1:
  s = 1
  while s < h and h_lst[s][0] == Max_h:
    h_ans.append(h_lst[s][1])
    s+= 1  
if w!= 1:  
  t=1  
  while t < w and w_lst[t][0] == Max_w:
    w_ans.append(w_lst[t][1])
    t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for j in h_ans:
  for k in w_ans:
    if (j,k) not in memo:
      print(Max_h+Max_w)
      sys.exit()
print((Max_h+Max_w)-1)
from heapq import heappush, heappop
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

# グラフにコストを格納
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

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


# コストの初期化
INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0

#　スタート地点
q = [(0, k)]

# ３からの距離
while q:
    cost, curr = heappop(q)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(q, (cost + nc, after))

print("\n".join(map(str, (dist[x] + dist[y]
                          for x, y in (map(int, input().split()) for _ in range(q))))))

### FIXED CODE ###

from heapq import heappush, heappop
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

# グラフにコストを格納
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

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


# コストの初期化
INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0

#　スタート地点
que = [(0, k)]

# ３からの距離
while que:
    cost, curr = heappop(que)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(que, (cost + nc, after))
            
print(*([dist[x] + dist[y] for x, y in (map(int, input().split()) for _ in range(q))]), sep="\n")
while True:
    H, W =[int(i) for i in input().split()]
    if H == W == 0:
        break

    for i in range(H):
        for i in range(W):
            if h == 0 or h == H - 1 or w == 0 or w == W - 1:
                print('#', end='')
            else:
                print('.', end='')


    print()

print()

### FIXED CODE ###

while True:
    H, W =[int(i) for i in input().split()]
    if H == W == 0:
        break

    for h in range(H):
        for w in range(W):
            if h == 0 or h == H - 1 or w == 0 or w == W - 1:
                print('#', end='')
            else:
                print('.', end='')

        print()

    print()
def is_bool(x):
  return isinstance(x, int) and bool(1 <= x) and bool(x >= 10000)

if is_bool(a) and is_bool(b):
      if (a*b) % 2 == 0:
      	return 'Even'
      else:
        return 'Odd'


### FIXED CODE ###

a, b = map(int, input().split())
if (a * b) % 2 == 0:
    print('Even')
else:
    print('Odd')
s=str(input())
x=s[0]+s[1]
y=s[2]+s[3]
x=int(x)
y=int(y)
if x==0 or y==0:
    ans="NA"
if 0<x<13:
    if 0<y<13:
        ans="AMBIGUOUS"
    elif y>=13:
        ans="MMYY"
        
elif x>=13:
    if 0<y<13:
        ans="YYMM"
    else:
        "NA"
print(ans)

### FIXED CODE ###

s=str(input())
a="Y"
b="Y"
if 0<int(s[0:2])<13:
    a="MY"
if 0<int(s[2:5])<13:
    b="MY"

if a==b=="Y":
    ans="NA"
elif a=="Y" and b=="MY":
    ans="YYMM"
elif a=="MY" and b=="Y":
    ans="MMYY"
else:
    ans="AMBIGUOUS"
print(ans)
a11, a12, a13 = map(int, input().split())
a21, a22, a23 = map(int, input().split())
a31, a32, a33 = map(int, input().split())
N = int(input())
num = []
for _ in range(N):
  num.append(int(input()))
  
bingo = [
  [a11, a12, a13], 
  [a21, a22, a23], 
  [a31, a32, a33]
]

for n in range(3):
  for m in range(3): 
    if bingo[n][m] in num:
      bingo[n][m] = 0

row1 = bingo[0][0] + bingo[0][1] + bingo[0][2]
row2 = bingo[1][0] + bingo[1][1] + bingo[1][2]
row3 = bingo[2][0] + bingo[2][1] + bingo[2][2]

col1 = bingo[0][0] + bingo[1][0] + bingo[2][0]
col2 = bingo[0][1] + bingo[1][1] + bingo[2][1]
col3 = bingo[0][2] + bingo[1][2] + bingo[2][2]

cross1 = bingo[0][0] + bingo[1][1] + bingo[2][2]
cross2 = bingo[2][0] + bingo[1][1] + bingo[2][0]

if 0 in [row1, row2, row3, col1, col2, col3, cross1, cross2]:
  print("Yes")
else:
  print("No")



### FIXED CODE ###

a = int(input())

b = int(a/2)

if b < a / 2:
  b = b + 1
 
print(b)
n = int(raw_input())
s = raw_input()
x = []
cnt = 0
for i in s:
if s[i] == 'I':
cnt += 1
x.append(cnt)
elif s[i] == 'D':
cnt -= 1
x.append(cnt)
else:
x.append(cnt)
print max(x)


### FIXED CODE ###

n = int(raw_input())
s = raw_input()

cnt =0
x =[0]
for i in xrange(n):
    if s[i] == 'I':
        cnt += 1
        x.append(cnt)
    elif s[i]  == 'D':
        cnt -= 1
        x.append(cnt)

print max(x)