Harryxun/stf_run huggingface dataset:
def common():
????X = raw_input()
  Y = raw_input()
????a = len(X)
????b = len(Y)
????k1 = [0 for t in range(b+1)]

????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]

  return k1[-1]

  n = input()
  for l in range(n):
????  print common()

### FIXED CODE ###

def common():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  k1 = [0 for i in range(b+1)]
 
  for i in range(a):
     k2 = k1 + []
     for j in range(b):
       if X[i] == Y[j]:
          k1[j+1] = k2[j] + 1
       elif k1[j+1] < k1[j]:
          k1[j+1] = k1[j]
 
  return k1[-1]
 
n = input()
for l in range(n):
  print common()
n = int(input())

ans = list()

for i in range(2, n):
    a = sum([int(j) for j in str(i)])
    b = sum([int(j) for j in str(n - i)])
    ans.append(a + b)

print(min(ans))

### FIXED CODE ###

n = int(input())

ans = list()

for i in range(2, n // 2):
    a = sum([int(j) for j in str(i)])
    b = sum([int(j) for j in str(n - i)])
    ans.append(a + b)

if len(ans) > 0:
    print(min(ans))
else:
    print(2)
S = input()
t = input()

tmp1 = 0
tmp2 = 0
res = ''
flag = False
for i in range(len(S) - len(t)+1):
    h = True
    for j in range(len(t)):
        if S[i+j] != t[j]:
            h = False
    if h == True:
        flag = True
        break
        
if h != True:
            
    while True:
        if S[-tmp1 - 1] == t[-tmp2 - 1]  or S[-tmp1 - 1] == '?':
            res = t[-tmp2 - 1] + res
            tmp1 += 1
            tmp2 += 1
        else:
            tmp1 += 1
            tmp2 = 0
            res = ''


        if tmp2 == len(t):
            flag = True
            break

        if tmp1 == len(S):
            break
      
tmp3 = ''
k = 0
for i in range(len(S)):
    if len(S) - tmp1 <= i < len(S) - tmp1 + len(t):
        tmp3 += t[k]
        k += 1
    elif S[i] == '?':
        tmp3 += 'a'
    else:
        tmp3 += S[i]
        
res = tmp3 
 
if flag:
    print(res)
else:
    print('UNRESTORABLE')


### FIXED CODE ###

S = input()
T = input()


    
if True:
    tmp = -1
    for i in range(len(S) - len(T) + 1):
        start = -1
        for j in range(len(T)):
            if S[i+j] == T[j] or S[i+j] == '?':
                start = i
            else:
                start = -1
                break
                
        
        if start != -1:
                tmp = i
    if tmp == -1:
        print('UNRESTORABLE')
    else:
        res = ''
        count = 0
        for i in range(len(S)):
            if tmp <= i < tmp + len(T):
                res += T[count]
                count += 1
            elif S[i] == '?':
                res += 'a'
            else:
                res += S[i]

        print(res)
s = input()
s_list = list(s)
while True:
    l5 = s_list[-5:]
    l6 = s_list[-6:]
    l7 = s_list[-7:]
    s5 = s6 = s7 = ''

    for ch in l5:
        s5 += ch
    print("s5 :", s5)
    for ch in l6:
        s6 += ch
    print("s6 :", s6)
    for ch in l7:
        s7 += ch
    print("s7 :", s7)

    if (s5 == 'erase') | (s5 == 'dream'): 
        s_list = s_list[:-5]
        print("s_list:", s_list)
    elif s6 == 'eraser':
        s_list = s_list[:-6]
        print("s_list:", s_list)
    elif s7 == 'dreamer':
        s_list = s_list[:-7]
        print("s_list:", s_list)
    else:
        print('NO')
        print("s_list:", s_list)
        exit()

    if  s_list == []:
        print('YES')
        exit()



### FIXED CODE ###

s = input()
while True:
    temp = s
    s5 = temp[-5:]
    s6 = temp[-6:]
    s7 = temp[-7:]

    if (s5 == 'erase') | (s5 == 'dream'): 
        s = temp[:-5]
    elif s6 == 'eraser':
        s = temp[:-6]
    elif s7 == 'dreamer':
        s = temp[:-7]
    else:
        print('NO')
        exit()

    if s == '':
        print('YES')
        exit()
# coding: utf-8
# Your code here!
A=input()
Y=int(A[0])*10+int(A[1])
M=int(A[2])*10+int(A[3])
code=0
if Y<20:
    if M>0 and M<13:
        code=1

if M<20:
    if Y>0 and Y<13:
        if code==1:
            code=3
        else:
            code=2
if Y==19:
    M==12:
        code=2
if Y=12:
    M=19:
        code=1
        
if code == 0:
    print("NA")
if code ==1:
    print("YYMM")
if code ==2:
    print("MMYY")
if code == 3:
    print("AMBIGUOUS")



### FIXED CODE ###

# coding: utf-8
# Your code here!
A=input()
Y=int(A[0])*10+int(A[1])
M=int(A[2])*10+int(A[3])
code=0
if Y<100:
    if M>0 and M<13:
        code=1

if M<100:
    if Y>0 and Y<13:
        if code==1:
            code=3
        else:
            code=2

if code == 0:
    print("NA")
if code ==1:
    print("YYMM")
if code ==2:
    print("MMYY")
if code == 3:
    print("AMBIGUOUS")
x,y,z,k = [int(num) for num in input().split()]
a_cake,b_cake,c_cake = [sorted([int(num) for num in input().split()],reverse=True) for _ in range(3)]

sum_cake = sorted([a+b+c for a in a_cake for b in b_cake for c in c_cake],reverse=True)[:k]
print(sum_cake)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if e-a<=k:
    print("Yay!")
else:
    print(":(")
s = input()

core = []

for c in s:
    if c != 'x':
        core.append(c)
l = 0
r = len(core) - 1
while l <= r:
    if core[l] != core[r]:
        print(-1)
        exit()
    l += 1
    r -= 1

ans = 0
l = 0
r = len(s) - 1
while l <= r:
    lx = 0
    rx = 0
    while s[l] == 'x':
        l += 1
        lx += 1
    while s[r] == 'x':
        r -= 1
        rx += 1
    ans += abs(lx - rx)
    l += 1
    r -= 1
print(ans)


### FIXED CODE ###

s = input()

core = []

for c in s:
    if c != 'x':
        core.append(c)
if core == []:
    print(0)
    exit()
l = 0
r = len(core) - 1

while l <= r:
    if core[l] != core[r]:
        print(-1)
        exit()
    l += 1
    r -= 1

ans = 0
l = 0
r = len(s) - 1

while l <= r:
    lx = 0
    rx = 0
    while s[l] == 'x':
        l += 1
        lx += 1
    while s[r] == 'x':
        r -= 1
        rx += 1
    ans += abs(lx - rx)
    l += 1
    r -= 1
print(ans)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = sorted(list(zip(b, a)))
 
a.sort()
b.sort()
for i in range(n):
  if a[i] > b[i]:
    print('No')
    exit()
 
p = 0
for i, (x, y) in enumerate(l):
  if x >= y:
    if y >= a[i] or i == 0 or l[i - 1][0] >= a[i]
      print('Yes')
      exit()
 
print('No')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = list(zip(b, a))
 
a.sort()
b.sort()
for i in range(n):
  if a[i] > b[i]:
    print('No')
    exit()

ptr, pos = {}, {}
for i in range(n):
  if i > 0 and a[i] <= b[i - 1]:
    print('Yes')
    exit()
  ptr[l[i][1]] = l[i][0]
  pos[b[i]] = i

sta, now, cnt = a[0], a[0], 1
while True:
  now = a[pos[ptr[now]]]
  if now == sta:
    break
  cnt += 1
if cnt == n:
  print('No')
else:
  print('Yes')
a,b=int(input.split())
print(a-b+1)

### FIXED CODE ###

a,b= (int(i) for i in input().split())  
print(a-b+1)
N = int(input())
H = list(map(int,input().split()))

count_list = []
count = 0

for i in range(N-1):
  if  H[i] >= H[i+1]:
    count += 1
  else:
    count_list.append(count)
    count = 0
else:
  countlist.apend(count)

print(max(count_list))

### FIXED CODE ###

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

count_list = []
count = 0

for i in range(N-1):
  if H[i] >= H[i+1]:
    count += 1
  else:
    count_list.append(count)
    count = 0
else:
  count_list.append(count)
    
print(max(count_list))
import sys
L, R = map(int,input().split())
a=[]

for i in range(L, R):
	for j in range(i+1,R+1):
		x = (i*j)%2019
		if x == 0:
			print(0)
			sys.exit()
		else:
			a.append()

print(min(a))

### FIXED CODE ###

import sys
l,r = map(int,input().split())
a=[]

for i in range(l,r):
	for j in range(i+1,r+1):
		a.append((i*j)%2019)

		if (i*j)%2019 == 0:
			print(0)
			sys.exit()
print(min(a))
from math import gcd

def lcm(*args):
    ans = 1
    for x in args:
        ans = ans * x // gcd(ans, x)
    return ans

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

l = lcm(*(int(x) // 2 for x in input().split()))

print(m // l - m // (2*l))

### FIXED CODE ###

from fractions import gcd

def lcm(*args):
    ans = 1
    for x in args:
        ans = ans * x // gcd(ans, x)
    return ans

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

def log(x):
    ans = 0
    while x % 2 == 0:
        ans += 1
        x //= 2
    return ans

def solve(a):
    tmp = None
    for ta in a:
        if tmp is None:
            tmp = log(ta)
        else:
            if tmp == log(ta):
                continue
            else:
                print(0)
                return
    l = lcm(*a)
    print(m // (l//2) - m // l)

solve(a)
i = 1
while True:
    print('Case '+str(i)+': '+input())
    i +=1


### FIXED CODE ###

i = 1
while True:
    a = input()
    if a =='0':
        break
    else:
        print('Case '+str(i)+': '+a)
        i +=1
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
  
def main():
  n,a,b = map(int,input().split())
  cnt = 0
  new = ""
  while True:
    if cnt + a <= n:
      cnt += a
      new += 'b' * a
    else:
      #print(cnt)
      a = n-cnt
      cnt += n-cnt
      #print(n-cnt)
      new += 'b' * (a)
      break
    if cnt + b <= n:
      cnt += b
      new += 'r'*b
    else:
      a = n-cnt
      cnt += n-cnt
      new += 'r' * (a)
      break
  #print(new)
  print(new.count('b'))
if __name__ == '__main__':
  main()

### FIXED CODE ###

#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""
  
def main():
  n,a,b = map(int,input().split())
  ans = n//(a+b) * a
  rem = n % (a+b)
  ans += min(rem,a)
  print(ans)
if __name__ == '__main__':
  main()
#B
import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())))
ans = 1
for i in A:
    ans *= i
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 1

for i in A:
    ans *= i
    if ans > 10**18:
        ans = -1
        print(ans)
        break
else:
    print(ans)
n,m = map(int,input().split())
d = {}
for _ in range(m):
  s,c = map(int,input().split())
  if s > n:
    print(-1)
    exit()
  if s in d:
    if d[s] == c:
      continue
    else:
      print(-1)
      exit()
  else:
    d[s] = c

ans = ''
for i in range(n):
  if i+1 in d:
    ans += str(d[i+1])
  else:
    ans += '1'
print(ans)



### FIXED CODE ###

import math
n = int(input())
print(int(math.ceil(n/2)))
N, A, B = map(int, input().split())
S = list(input())
 
ok_count = 0
ok_fcount = 0
for i in range(N):
  if S[i] == a:
    if ok_count < A+B-1
      print('Yes')
      ok_count +=1
      
    else:
      print('No')
      
  elif S[i] == b:
    if ok_count <= A+B-1 and ok_fcount < B-1:
      print('Yes')
      ok_count+=1
      ok_fcount+=1
      
    else:
      print('No')
      
  else:
    print('No')

### FIXED CODE ###

N, A, B = map(int, input().split())
S = input()
 
ok_count = 0
ok_fcount = 0
for i in range(N):
  if S[i] == 'a':
    if ok_count < A+B:
      print('Yes')
      ok_count +=1
      
    else:
      print('No')
      
  elif S[i] == 'b':
    if ok_count < A+B and ok_fcount < B:
      print('Yes')
      ok_count+=1
      ok_fcount+=1
      
    else:
      print('No')
      
  else:
    print('No')
k, s = map(int, input().split())

ans = 0
for i in range(0,k+1):
  for j in range(0,k+1):
    if i+j <= s and s-(i+j) <= k:
      ans += 1
print(ans)

### FIXED CODE ###

s = str(input())

for i in range(len(s)):
  if s[i] == ",":
    s = s[:i]+" "+s[i+1:]
print(s)
a,b = map(int,input().split())
ans = ''
if a <= b:
    for _ in range(b):
        ans.join(a)
else: 
    for _ in range(a):
        ans.join(b)
print(ans)


### FIXED CODE ###

a,b = map(int,input().split())
ans = ''
if a <= b:
    for _ in range(b):
        ans+=str(a)
else: 
    for _ in range(a):
        ans+=str(b)
print(ans)
if set(s[l[i]:l[i+1]])=={"L"}:
            ans[l[i]]=p
        if set(s[l[i]:l[i+1]])=={"R"}:
            ans[l[i+1]-1]=p


### FIXED CODE ###

s=input()

l=[0]
ans=[0]*(len(s))
for i in range(len(s)-1):
    if s[i]=="L" and s[i+1]=="R":
        l.append(i+1)
       
n=len(l)+1
l.append(len(s))
#print(set(s[l[0]:l[1]]))

for i in range(n-1):
    #print(s[l[i]:l[i+1]])
    for j in range(len(s[l[i]:l[i+1]])-1):
        p=len(s[l[i]:l[i+1]])
        if s[l[i]]=="L":
            ans[l[i]]=p
            break
        if s[l[i+1]-1]=="R":
            ans[l[i+1]-1]=p
            break
        if s[l[i]:l[i+1]][j]=="R" and s[l[i]:l[i+1]][j+1]=="L":
            if j%2==1:
                ans[l[i]+j]=p//2
                ans[l[i]+j+1]=p-p//2
                break
            else:
                ans[l[i]+j]=p-p//2
                ans[l[i]+j+1]=p//2
                break
print(*ans)
from math import ceil

X, N = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
l2 = [abs(int(x)-X) for x in l]
l2.sort()
for i in range(N):
    if ceil(i/2) != l2[i]:
        t = ceil(i/2)
        break
if X - t in l:
    print(X + t)
else:
    print(X - t)

### FIXED CODE ###

N = int(input())
l = [int(x) for x in input().split()] + [1000001]
l.sort()
ans = 0
t = 0
M = [False] * 10 ** 6
for i in range(N):
    if not M[l[i]-1]:
        if l[i] != l[i+1]:
            ans += 1
        t = l[i]
        while t <= 10 ** 6:
            M[t-1] = True
            t += l[i]
print(ans)
K = int(input())
A,B = map(int,input().split())
for i in range(A,B+1)
    if i % K == 0:
        print('OK')
        quit()
else : 
    print('NG')


### FIXED CODE ###

K = int(input())
A,B = map(int,input().split())
for i in range(A,B+1):
    if i % K == 0:
        print( 'OK' )
        quit()
else:
    print( 'NG' )
# coding: utf-8
import math

A, B = [int(x) for x in input().split(" ")]

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(A, B))

### FIXED CODE ###

# coding: utf-8
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

 #最小公倍数
def lcm(a,b):
  return a*b//gcd(a,b)
 
A, B = [int(x) for x in input().split(" ")]
 
print(lcm(A, B))
n=int(input())
A=list(int,input(),split())
print("YES" if len(set(A))==len(A) else "NO")

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
print("YES" if len(set(A))==len(A) else "NO")
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0]
V = UV[:,1]
S,T = map(int,input().split())
if M == 0:
  print(-1)
  exit()
rows = np.concatenate([3*U, 3*U+1, 3*U+2])
cols = np.concatenate([3*V+1, 3*V+2, 3*V])

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)


### FIXED CODE ###

# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = map(int,input().split())
  edge[u].append(v)
S,T = map(int,input().split())

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)
A = [list(map(int,input().split())) for _ in range(3)]
N = int(input())
b = list(map(int,input().split()))
    
import numpy as np
A = np.array(A)
l = []
for i in range(N):
  if b[i] in A:
    l.append(tuple(nd[0] for nd in np.where(A == b[i])))
if (0, 0) in l and (1, 0) in l and (2, 0) in l:
  print("Yes")
elif (0, 0) in l and (1, 1) in l and (2, 2) in l:
  print("Yes")
elif (0, 1) in l and (1, 1) in l and (2, 1) in l:
  print("Yes")
elif (0, 2) in l and (1, 1) in l and (2, 0) in l:
  print("Yes")
elif (0, 2) in l and (1, 2) in l and (2, 2) in l:
  print("Yes")
elif (0, 0) in l and (0, 1) in l and (0, 2) in l:
  print("Yes")
elif (1, 0) in l and (1, 1) in l and (1, 2) in l:
  print("Yes")
elif (2, 0) in l and (2, 1) in l and (2, 2) in l:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

A = [list(map(int,input().split())) for _ in range(3)]
N = int(input())
b = [int(input()) for i in range(N)]
    
import numpy as np
A = np.array(A)
l = []
for i in range(N):
  if b[i] in A:
    l.append(tuple(nd[0] for nd in np.where(A == b[i])))
if (0, 0) in l and (1, 0) in l and (2, 0) in l:
  print("Yes")
elif (0, 0) in l and (1, 1) in l and (2, 2) in l:
  print("Yes")
elif (0, 1) in l and (1, 1) in l and (2, 1) in l:
  print("Yes")
elif (0, 2) in l and (1, 1) in l and (2, 0) in l:
  print("Yes")
elif (0, 2) in l and (1, 2) in l and (2, 2) in l:
  print("Yes")
elif (0, 0) in l and (0, 1) in l and (0, 2) in l:
  print("Yes")
elif (1, 0) in l and (1, 1) in l and (1, 2) in l:
  print("Yes")
elif (2, 0) in l and (2, 1) in l and (2, 2) in l:
  print("Yes")
else:
  print("No")
l = input("Enter: ")
if len(l)<= 6 and l==[a-z]:
	print("Yes" if (l[2]==l[3] and l[4]==l[5]) else "No")

### FIXED CODE ###

l = input()
print("Yes" if (l[2]==l[3] and l[4]==l[5]) else "No")
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #辺につながっている頂点に使った色
color_side =[0]*(N-1)
color =0
color_all =set(j for j in range(1,color_max +1) )
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    #while True:
    color =(color_all - color_vertex[v_a] -color_vertex[v_b]).pop() #全ての色-使った色[a]-使った色[b]

    color_side[i] =color          #辺の色を出力用に決める
    color_vertex[v_a].add(color)    #前の頂点に使った色として追加
    color_vertex[v_b].add(color)    #先の頂点に使った色として追加
              
#出力
print(color_max)
print(*color_side, sep="\n")

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
import fractions
n=int(input())
a=1
for i in range(n):
  b=int(input())
  a=a//fractions.gcd(a,b)*b
print(int(a))


### FIXED CODE ###

s=input()
if(s[0]==s[2]):
  print("Yes")
else:
  print("No")
w,h,n=[int(i) for i in input().split(' ')]
x1,x2,y1,y2=0,w,0,h
for i in range(n):
  x,y,a=[int(i) for i in input().split(' ')]
  if a==1:
    x1=max(x1,x)
  if a==2:
    x2=min(x2,x)
  if a==3:
    y1=max(y1,y)
  if a==4:
    y2=min(y2,y)
print(max(0,(y2-y1)*(x2-x1))

### FIXED CODE ###

w,h,n=[int(i) for i in input().split(' ')]
x1,x2,y1,y2=0,w,0,h
for i in range(n):
  x,y,a=[int(i) for i in input().split(' ')]
  if a==1:
    x1=max(x1,x)
  if a==2:
    x2=min(x2,x)
  if a==3:
    y1=max(y1,y)
  if a==4:
    y2=min(y2,y)
    
if y2<=y1 or x2 <= x1:
  print(0)
else:
  print(max(0,(y2-y1)*(x2-x1)))
#f

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
for i in range(n):
    I.append(I[-1] * pow(2, mod-2, mod) % mod)

ans = 0
for i in range(n):
    ans += (1-I[i])*(1-I[n-i])
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)



### FIXED CODE ###

#f
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)
 

n = int(input())
E = [[] for _ in range(n)]
mod = 10**9 + 7

for i in range(n-1):
    a,b = [int(x) for x in input().split()]
    E[a-1].append((b-1, i)) 
    E[b-1].append((a-1, i)) 
    
X = [0] * n
    
def dfs(u,e):
    num = 1
    for v,c in E[u]:
        if c != e:
            num += dfs(v,c)
    X[e] = num 
    return num

dfs(0, -1)

I = [1]
inv = pow(2, mod-2, mod)
for i in range(n):
    I.append(I[-1] * inv % mod)

ans = 0
for i in range(n):
    x = X[i]
    ans += (1-I[x])*(1-I[n-x]) % mod
    
ans -= n * I[1]
ans += 1 - I[n]
ans %= mod
print(ans)
from itertools import combinations
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]

dd = dict()
t = 0

for n ,m in combinations(d, 2):
    if n[0] == m[0]:
        t += 1
    else:
        a = (m[1]-n[1])/(m[0]-n[0])
        if a in dd:
            dd[a] += 1
        else:
            dd.setdefault(a, 1)

print(N-max(t, *dd.values()))


### FIXED CODE ###

N = int(input())
S = list(tuple(map(int, input().split())) for _ in range(N))
A = []
if N == 1:
    print(1)
else:
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            a, b = S[i]
            c, d = S[j]
            for k in range(len(A)):
                e, f, g = A[k]
                if e == a-c and f == b-d:
                    A[k] = (e, f, g+1)
                    break
            else:
                A.append((a-c, b-d, 1))
    print(N-max(list(x[2] for x in A)))
N=int(input())

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

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)

print(max(L))
for l in L:
  print(l)


### FIXED CODE ###

N=int(input())
#再起のlimitを上げる
import sys
sys.setrecursionlimit(4100000)
S=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  S[a-1].append((b-1, i))
  S[b-1].append((a-1, i))

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)

print(max(L))
for l in L:
  print(l)
x = int(input())

z = []
u = []
for a in range(1,100):
    for b in range(-100,100):
        z.append(a**5-b**5)
        u.append((a,b))

for i in range(10**9+1):
    if z[i] == x:
        print(u[i][0],u[i][1])
        break

### FIXED CODE ###

x = int(input())

from collections import deque
z = []
u = deque([])
for a in range(0,1000):
    for b in range(-1000,1000):
        z.append(a**5-b**5)
        u.append((a,b))

for i in range(10**6+1):
    if z[i] == x:
        print(u[i][0],u[i][1])
        break