Harryxun/stf_run huggingface dataset:
N = int(input())

class edge:
    def __init__(self,_to,_cost):
        self.to = _to;
        self.cost = _cost;

tree = [[] for i in range(N)]

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

Q, K = list(map(int, input().split()))
K = K - 1
depth = [0]*N

def DFS(v,p,d):
    depth[v] = d
    for e in tree[v]:
        if e.to==p :
            continue
        DFS(e.to, v, d + e.cost)

DFS(K,-1,0)

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


### FIXED CODE ###

n = input()
s = []
for i in range(len(n)):
    s.append(n[len(n)-1-i])
if(n=="".join(s)):
    print("Yes")
else:
    print("No")
import math

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

MAX = 1000005

is_prime = [1]*MAX
D = [None]*MAX
is_prime[0],is_prime[1] = 0,0

for i in range(2,MAX):
  if is_prime[i]:
    D[i] = i
    for j in range(i*2,MAX,i):
      is_prime[j] = 0
      D[j] = i
      
counts = [0]*MAX
pair = True

for a_i in a:
  while True:
    p = D[a_i]
    if counts[p]>0:
      pair = False
    counts[p] += 1
    if p == a_i:
      break
    else:
      a_i //= p

if pair:
  print('pairwise coprime')
else:
  g = a_i
  for a_i in a:
    g = math.gcd(a_i,g)
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')

### FIXED CODE ###

import math

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

MAX = 1000005
c = [0]*MAX

for i in range(n):
  c[a[i]] += 1

pair = True

for i in range(2,MAX):
  cnt = 0
  for j in range(i,MAX,i):
    cnt += c[j]
  if cnt > 1:
    pair = False

if pair:
  print('pairwise coprime')
else:
  g = a[0]
  for i in range(1,n):
    g = math.gcd(g,a[i])
    
  if g == 1:
    print('setwise coprime')
  else:
    print('not coprime')
[S,Y] = [int(i) for i in input().split()]

if Y % 2 == 1:
  print("No")
else:
  for x in range(S+1):
    y = S - x
    if 4*x + 2*y == Y:
      print("Yes")
      break
  else:
    print("No")

### FIXED CODE ###

array = [int(i) for i in input().split()]
i = 1

for x in array:
  if x == 0:
    print(i)
    break
  i += 1
s = input()
if s.replace('eraser','').replace('erase','').replace('dreamer','').replace('dream','')
:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

s = input()
if s.replace('eraser','').replace('erase','').replace('dreamer','').replace('dream',''):
    print('NO')
else:
    print('YES')
while 1:
h,w = map(int, raw_input().split())
  if h==w==0
    break

for i in range(0,h/2):
  print ("#." * (w/2) + "#" * (w%2))
  print (".#" * (w/2) + "." * (w%2))

if h % 2 == 1:
  print ("#." * (w/2) + "#" * (w%2))

print "\n"

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0:
    break

  for i in range(0,h/2):
    print ("#." * (w/2) + "#" * (w%2))
    print (".#" * (w/2) + "." * (w%2))

  if h % 2 == 1:
    print ("#." * (w/2) + "#" * (w%2))

  print ""
import sys

N, M = map(int, input().split())

def com(n,r):
    ans1 = 1
    ans2 = 1
    tmp = r
    while r != 0:
        ans1 = ans1 * (n)
        ans2 = ans2 * r
        n -= 1
        r -= 1

    return ans1/ans2

print(int(com(N,2)+com(M,2))


### FIXED CODE ###

import sys

N, M = map(int, input().split())

def com(n,r):
    ans1 = 1
    ans2 = 1
    tmp = r
    while r != 0:
        ans1 = ans1 * (n)
        ans2 = ans2 * r
        n -= 1
        r -= 1

    return ans1/ans2

print(int(com(N,2)+com(M,2)))
word = [chr(i) for i in range(97, 97+26)]
word_number = []
line = ""
while(1):
    temp_line = input() 
    line += temp_line
    if temp_line =="":
        break

for target in word:
    count = 0
    for character in line:
        if character.lower() == target:
            count += 1
    word_number.append(count)

for i in range(26):
    print("{0} : {1}".format(word[i],word_number[i]))

### FIXED CODE ###

import sys
word = [chr(i) for i in range(97, 97+26)]
word_number = []
lines = ""
for line in sys.stdin:
    lines += line

for target in word:
    count = 0
    for character in lines:
        if character.lower() == target:
            count += 1
    word_number.append(count)

for i in range(26):
    print("{0} : {1}".format(word[i],word_number[i]))
N=int(input())
A=list(map(int,input().split()))
ans=0
c=0
tmp=10**9
for a in A:
    if a<0:
        c+=1
    ans+=abs(a)
    tmp=min(tmp,abs(a))
if c%2==0:
    print(ans)
else:
    print(ans-tmp*2)

### FIXED CODE ###

A,B,T=map(int,input().split())
print(int((T+0.5)//A*B))
X,Y,A,B,C= map(int, input().split())
R = list(map(int, input().split()))
G = list(map(int, input().split()))
N = list(map(int, input().split()))

R.sort(reverse=True)
G.sort(reverse=True)
N.sort(reverse=True)

R2 = R[:X]
G2 = G[:Y]

W = sorted(R2 + G2 + N, reverse=True)

print(sum(W[0:X+Y]))

### FIXED CODE ###

S = input()
if S[2] == S[3] and S[4] == S[5]:
  print("Yes")
else:
  print("No")
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,M,R = map(int,input().split())

machi = list(map(int,input().split()))

List = [[10**6]*(N) for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  
  if List[a-1][b-1] > c:
    List[a-1][b-1] = c
    List[b-1][a-1] = c
G = csgraph_from_dense(List, null_value=10**6)
d = floyd_warshall(G)

import itertools
a = list(itertools.permutations(machi))
arr = []
for i in a:
  ans = 0
  for j in range(R):
    if j != R-1 :
      ans += d[i[j]-1][i[j+1]-1]
  arr.append(ans) 
  
print(int(min(arr)))

### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,M,R = map(int,input().split())

machi = list(map(int,input().split()))

List = [[10**6]*(N) for i in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  
  if List[a-1][b-1] > c:
    List[a-1][b-1] = c
    List[b-1][a-1] = c
G = csgraph_from_dense(List, null_value=10**6)
d = floyd_warshall(G)

import itertools
a = list(itertools.permutations(machi))
arr = []
for i in a:
  ans = 0
  for j in range(R):
    if j != R-1 :
      ans += d[i[j]-1][i[j+1]-1]
  arr.append(ans) 
  
print(int(min(arr)))
import math

A, B, C, D = map(int, input().split())

s = B - A + 1

if A % C == 0 or A % D == 0:
    A -= 1

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

E = lcm(C, D)

val1 = A // C
val2 = B // C
val3 = A // D
val4 = B // D
val5 = A // E
val6 = B // E

print(s - (val2 - val1 + val4 - val3 - (val6 - val5)))


### FIXED CODE ###

result = "Good"
s = list(input())
if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
    result = "Bad"
print(result)
n,m = map(int, input().split())
l = [0] * m

for i in range(n):
  k = list(map(int, input().split()))
  for j in range(1, k[0]+1):
    l[k[j-1]] += 1
print(l.count(n))

### FIXED CODE ###

n,m = map(int, input().split())
k = [list(map(int, input().split())) for _ in range(n)]
dic = {x:0 for x in range(1,m+1)}
ans = 0
for i in range(n):
  for j in range(1, k[i][0] + 1):
    dic[k[i][j]] += 1

for a,b in dic.items():
  if b == n:
    ans += 1
print(ans)
def f(S,t):
    return T+S
S=input()
T=input()
print(f(S,T))


### FIXED CODE ###

def f(S,T):
    return T+S
S,T= map(str,input().split())
print(f(S,T))
N, X = list(map(int, input().split()))
l = list(map(int, input().split()))

D=0
i=0
c=0
while D <= X:
    D+=l[i]
    i+=1
    c+=1

print(c)

### FIXED CODE ###

N, X = list(map(int, input().split()))
l = list(map(int, input().split()))

D=0
i=0
c=0
while D <= X:
    try:
        c+=1
        # if i>len(l):
        #     break
        D+=l[i]
        i+=1
    except IndexError:
        break

print(c)
n,*a=map(int,open(0).read().split())
t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:exit(-1)
  v+=w
print(v)

### FIXED CODE ###

from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
#大きくしすぎてしまう場合がある
#いや上限を考えろや
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
        #print(b)
f()
n,k = map(int,input().split())
d = [0]*k
A = [[0]*k]*n
l = set()
for i in range(k):
	d[i] = int(input())
	A[i] = list(map(int,input().split()))
for i in range(k):
	l = l.union(A[i])
print(len(set(range(1,n+1))-l))

### FIXED CODE ###

n,k = map(int,input().split())
d = [0]*k
A = [[0]*n]*k
l = set()
for i in range(k):
	d[i] = int(input())
	A[i] = list(map(int,input().split()))
for i in range(k):
	l = l.union(A[i])
if set(range(1,n+1)) == l:
	print(0)
else:
	print(len(set(range(1,n+1))-l))
import fractions
n=int(input())
t=[int(input()) for i in range(n)]
t.sort()
check=t[0]
for i in range(n-1):
    f1=fractions.gcd(t[i],t[i+1])
    f2=check*t[i+1]//f1
    check=f2
print(f2)

### FIXED CODE ###

import fractions
n=int(input())
t=[int(input()) for i in range(n)]
t.sort()
check=t[0]
if n==1:
    print(check)
else:
    for i in range(n-1):
        f1=fractions.gcd(check,t[i+1])
        f2=check*t[i+1]//f1
        check=f2
    print(f2)
s = input()
k = int(input())

sln = len(s)
subs = set()

for ln in range(1, k + 1):
    for i in range(sln):
        subs += s[i:i+ln]
print(sorted(list(subs))[k-1])

### FIXED CODE ###

def f(myC, s, chrs, lst, k):
    if len(lst) == k:
        print(lst[k - 1])
        exit()
    else:
        for c in chrs:
            buf = myC + c
            if buf in s:
                lst += [buf]
                ##print(lst)
                f(buf, s, chrs, lst, k)

if __name__ == '__main__':
    s = input()
    k = int(input())

    chrs = sorted(list(set(s)))
    lst = f('', s, chrs, list(), k)
n=int(input())
d=sorted(list(map(int,input().split())))
print(d[n//2]-d[N//2-1])

### FIXED CODE ###

n=int(input())
d=sorted(list(map(int,input().split())))
print(d[n//2]-d[n//2-1])
a=input()
b=input()
c=input()

if a == b:
    print(int(c))
elif a == c:
    print(int(b))
elif b == c:
    print(int(a))

### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b:
    print(c)
elif b==c:
  print(a)
else:
  print(b)
S = input()
st = []
if len(S) %2 != 0 :
    print('No')
else :
    for i in range(len(S) // 2) :
        st.append(S[i:i+2])
      
    st = list(set(st))) 
    if len(st) == 1 and st[0] == 'hi' :
        print('Yes')
    else :
        print('No')

### FIXED CODE ###


S = input()
st = []
if len(S) %2 != 0 :
    print('No')
else :
    for i in range(len(S) // 2) :
        st.append(S[i*2:i*2+2])
      
    st = list(set(st)) 
    if len(st) == 1 and st[0] == 'hi' :
        print('Yes')
    else :
        print('No')
s = input()
t = input()

n = len(s)
m = len(t)

for i in range(n - m + 1):
    bubun = s[i:i + m]
    flag = True
    for j in range(m):
        x = bubun[j]
        y = t[j]
        if x == y:
            pass
        elif x == '?':
            pass
        else:
            flag = False

    if flag:
        ans = s[:i].replace('?', 'a') + t + s[i + m:].replace('?', 'a')
        break

print(ans) if flag else print('UNRESTORABLE')


### FIXED CODE ###

s = input()
t = input()

n = len(s)
m = len(t)

if t in s:
    print(s.replace('?', 'a'))
else:
    ans = []
    for i in range(n - m + 1):
        bubun = s[i:i + m]
        flag = True
        for j in range(m):
            x = bubun[j]
            y = t[j]
            if x == y:
                continue
            elif x == '?':
                continue
            else:
                flag = False
                break

        if flag:
            ans.append((s[:i] + t + s[i + m:]).replace('?', 'a'))

    print(sorted(ans)[0]) if ans else print('UNRESTORABLE')
s='0131212112121'
print("Yes" if s[x]==s[y] else "No")

### FIXED CODE ###

s='0131212112121'
x,y=map(int,input().split())
print("Yes" if s[x]==s[y] else "No")
import collections

n = int(input())

al = [int(l) for l in input().split()]

a = []
b = []
for i, x in enumerate(al):
    if i%2 == 0:
        a.append(x)
    else:
        b.append(x)

ac = collections.Counter(a).most_common()
bc = collections.Counter(b).most_common()

if ac[0][0] != bc[0][0]:
    print(n-ac[0][1]-bc[0][1])
else:
    if len(ac) >= 2 and ac[0][1] == ac[1][1]:
        print(n-ac[0][1]-bc[0][1])
    elif len(bc) >= 2 and bc[0][1] == bc[1][1]:
        print(n-ac[0][1]-bc[0][1])

    min_c = n//2

    if len(bc) >= 1:
        min_c = min(min_c, n-ac[0][1]-bc[1][1])
    else:
        min_c = min(min_c, n-ac[0][1])
    if len(ac) >= 1:
        min_c = min(min_c, n-ac[1][1]-bc[0][1])
    else:
        min_c = min(min_c, n-bc[0][1])
        
    if len(ac) >= 1 and len(bc) >= 1:
        min_c = min(min_c, n-bc[1][1]-ac[1][1])
    print(min_c)
    


### FIXED CODE ###

import collections

n = int(input())

al = [int(l) for l in input().split()]

a = []
b = []
for i, x in enumerate(al):
    if i%2 == 0:
        a.append(x)
    else:
        b.append(x)

ac = collections.Counter(a).most_common()
bc = collections.Counter(b).most_common()

if ac[0][0] != bc[0][0]:
    print(n-ac[0][1]-bc[0][1])
else:
    if len(ac) == 1 and len(bc) == 1:
        print(n-max(ac[0][1], bc[0][1]))
    elif len(ac) == 1:
        print(n-max(ac[0][1], ac[1][1]+bc[0][1]))
    elif len(ac) == 1:
        print(n-max(bc[0][1], ac[0][1]+bc[1][1]))
    else:
        print(n-max(ac[1][1]+bc[0][1], ac[0][1]+bc[1][1]))
a , b = map(int , input())
if a * b % 2 == 1:
    print("Odd")
elif a * b % 2 == 0:
    print("Even")

### FIXED CODE ###

a , b = map(int , input().split())
if a * b % 2 == 1:
    print("Odd")
elif a * b % 2 == 0:
    print("Even")
N = int(input())

point = []
dist = []
maxDist = 0

for _ in range(N) :
    x, y = map(int, input().split())
    d = abs(x) + abs(y)
    maxDist = max(maxDist, d)
    point.append((x, y, d))
    dist.append(d)

mask = maxDist % 2

for d in dist :
    if d % 2 != mask :  # 実現不可能
        print('-1')
        break
else :  # 実現可能
    print(maxDist) # 腕の数
    out = [1] * maxDist
    print(*out)

    for x, y, d in point :
        if x < 0 :
            for _ in range(-x) :
                print('L', end='')
        elif x > 0 :
            for _ in range(x) :
                print('R', end='')

        if y < 0 :
            for _ in range(-y) :
                print('D', end='')
        elif y > 0 :
            for _ in range(y) :
                print('U', end='')

        R = (maxDist - d) // 2
        if R > 0 :
            for _ in range(R) :
                print('LR', end='')

        print('')


### FIXED CODE ###

N=int(input())

point = []
parity = {}
for _ in range(N) :
    x, y = map(int, input().split())
    point.append((x, y))
    parity[(x + y) % 2] = 1

if len(set(parity)) == 2 :
    print('-1')
else :
    m = 38
    parity = 1 if (1 in parity) else 0
    print(m + 1 - parity)
    if parity == 1 :  # 距離が奇数
        print(*[1 << i for i in range(m)])
    else :
        print(1, *[1 << i for i in range(m)])

    def arm(x, y, m) :
        if abs(x) >= abs(y) :
            if x >= 0 :
                return ('R', x - (1<<m), y)
            else :
                return ('L', x + (1<<m), y)
        else :
            if y >= 0 :
                return ('U', x, y - (1<<m))
            else :
                return ('D', x, y + (1<<m))

    for x, y in point :
        ans = []
        for i in range(m-1, -1, -1) :
            mode, x, y = arm(x, y, i)
            ans.append(mode)
        if parity == 0 :  # 偶数の場合一つ足す
            if x == 1 :
                ans.append('R')
            elif x == -1 :
                ans.append('L')
            elif y == 1 :
                ans.append('U')
            elif y == -1 :
                ans.append('D')
        print(''.join(ans[::-1]))
N, Q = map(int, input().split())
 
AB = [[int(x) for x in input().split()] for _ in range(N-1)] 
PX = [[int(x) for x in input().split()] for _ in range(Q)] 
 
graph = [[] for _ in range(N+1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p, x in PX:
    value[p] +=x
 
def dfs(v, parent, add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x, v, value[v])
 
dfs(1, 0, 0)
ans = ' '.join(map(str,value[1:]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
 
AB = [[int(x) for x in input().split()] for _ in range(N-1)] 
PX = [[int(x) for x in input().split()] for _ in range(Q)] 
 
graph = [[] for _ in range(N+1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p, x in PX:
    value[p] +=x
 
def dfs(v, parent, add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x, v, value[v])
 
dfs(1, 0, 0)
ans = ' '.join(map(str,value[1:]))
print(ans)
N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    for _ in range(0, N):
        U[int(S)%P] += 1
        S = S.lstrip(S[0])
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    t, s = 0, 1
    for i in range(N-1, -1, -1):
        t = (int(S[i])*s+t)%P
        U[t] += 1
        s = s*10%P
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)
#input
N = int(input())
B = list(map(int, input().split()))

A = [0] * N
for i in range(1, N-1):
    if A[i] > B[i]:
        A[i] = B[i]
    A[i+1] = B[i]

print(sum(A))

### FIXED CODE ###

#input
N = int(input())

print(N ** 3)
N, D = map(int, input())
if(N%2*D+1==0):
	print(N//((2*D)+1))
else:
	print(N//((2*D)+1)+1)

### FIXED CODE ###

N, D = map(int, input().split())
x = N//((2*D)+1)
if(x*((2*D)+1)>= N):
	print(N//((2*D)+1))
else:
	print((N//((2*D)+1)+1))
s = input()
if s == "hi" * len(s) // 2:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
if s == "hi" * (len(s) // 2):
  print("Yes")
else:
  print("No")
flag =0
while flag==0:
    a,b,c=[ i for i in input().split()])
    if b=="?":
        flag=1
        break
    elif b=="+":
        n=int(a)+int(c)
    elif b=="-":
        n=int(a)-int(c)
    elif b=="*":
        n=int(a)*int(c)
    elif b=="/":
        n=int(a)/int(c)
    print(int(b)

### FIXED CODE ###

flag =0
while flag==0:
    a,b,c=[ i for i in input().split()]
    if b=="?":
        flag=1
        break
    elif b=="+":
        n=int(a)+int(c)
    elif b=="-":
        n=int(a)-int(c)
    elif b=="*":
        n=int(a)*int(c)
    elif b=="/":
        n=int(a)/int(c)
    print(int(n))
alphabet="abcdefghijklmnopqrstuvwxyz"
st=input()
s=""
for i in range(0,len(st)):
    if alphabet.index(st[i]) % 2 == 0:
        s+=str(st[i])
    else:
        pass

### FIXED CODE ###

X,t = map(int, input().split())
if X-t<0:
    print(str(0))
else:
    print(str(X-t))
import math
import fractions
N=int(input())
A=list(map(int,input().split()))
tmp=A[0]
ans=0

for i in range(N):
    tmp=math.floor((tmp*A[i])/(fractions.gcd(tmp,A[i])))

for i in range(N):
    ans+=(tmp/A[i])
    ans%=1000000007
    
print(int(ans))

### FIXED CODE ###

MOD=10**9+7
def factorization(n):
    arr=[]
    tmp=n
    for i in range(2,int(n**0.5)+1):
        if(tmp%i==0):
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
    if(not arr):
        arr.append([1,1])
    if(tmp!=1):
        arr.append([tmp,1])
    return arr
def moddiv(a,m):
    return pow(a,m-2,m)
N=int(input())
A=list(map(int,input().split()))
cnt={}
for i in range(N):
    arr=factorization(A[i])
    for a,b in arr:
        cnt[a]=max(cnt.get(a,0),b)
g=1;res=0
for k,v in cnt.items():
    g=g*(pow(k,v,MOD))%MOD
for i in range(N):
    res=(res+(g*moddiv(A[i],MOD))%MOD)%MOD
print(res)
n = int(input())

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

# n が 2なら 大きい方を出力して終わり

#def euclid(m, n):
#  if n == 0:
#    return m
#  new_m = n
#  new_n = m % n
#  return euclid(new_m, new_n)
#
#def array_euclid(numbers):
#  n = len(numbers)
#  v = numbers[n-1] % numbers[n-2]
#  if v == 0:
#    if n == 2:
#      return numbers[0]
#    
#    numbers.pop()
#    return array_euclid(numbers)
#
#  numbers[n-1] = numbers[n-2]
#  numbers[n-2] = v
#  return array_euclid(numbers)

#print(array_euclid(a))

#if n == 2:
#  print(euclid(a[0], a[1]))
#if n > 2:
#  max_list = []
#  max_list.append(array_euclid(a[:]))
#  for i in range(n):
#    a2 = a[:]
#    a2.pop(i)
#    max_list.append(array_euclid(a2))
#  print(max(max_list))
#


# n が3になるまでやって、大きい方が答え？

#for i in range(n-1):


#print(euclid(a[0],a[1]))


# 最大公約数を求めるには math.gcd を使う

from fractions import gcd
from functools import reduce

def gcd_list(numbers):
  return reduce(gcd, numbers)

max_list = []
max_list.append(gcd_list(a))
for i in range(n):
  a2 = a[0:i] + a[i+1:]
  #a2.pop(i)
  max_list.append(gcd_list(a2))
print(max(max_list))



### FIXED CODE ###

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

print((t // a) * b)
s = input()

if s == "A":
  print("T")
elif s == "T":
  print("A")
elif  == "G":
  print("C")
else:
  print("G")

### FIXED CODE ###

s = input()

if s == "A":
  print("T")
elif s == "T":
  print("A")
elif s == "G":
  print("C")
else:
  print("G")
from collections import deque


def solve(N, K, ABs):
    # print(N, ",", K, ", ", ABs)
    Ds = [0 for _ in range(N + 1)]
    Ws = {i: [] for i in range(N + 1)}
    for a, b in ABs:
        Ws[a].append(b)
        Ws[b].append(a)

    Ds[1] = K
    s = Ws[1][0]
    Ds[s] = K - 1

    queue = deque()
    queue.append(1)
    queue.append(s)

    while queue:
        s = queue.popleft()
        k = K - 2
        for w in Ws[s]:
            if Ds[w] == 0:
                Ds[w] = k
                k -= 1
                queue.append(w)
    ans = 1
    for i in range(1, N + 1):
        ans *= Ds[i]
        ans %= 1000000007
    return ans


# print(solve(4, 3, [(1, 2), (2, 3), (3, 4)]))
# assert (solve(4, 3, [(1, 2), (2, 3), (3, 4)]) == 6)
# assert(solve(5, 4, [(1, 2), (1, 3), (1, 4), (4, 5)]) == 48)

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, K, ABs))


### FIXED CODE ###

from collections import deque


def solve(N, K, ABs):
    if N == 1:
        return K

    Ds = [-1 for _ in range(N + 1)]
    Ws = {i: [] for i in range(N + 1)}
    for a, b in ABs:
        Ws[a].append(b)
        Ws[b].append(a)

    for i in range(1, N + 1):
        if Ds[i] == -1:
            Ds[i] = K

            if Ws[i]:
                s = Ws[i][0]
                Ds[s] = K - 1

                queue = deque()
                queue.append(i)
                queue.append(s)

                while queue:
                    s = queue.popleft()
                    k = K - 2
                    for w in Ws[s]:
                        if Ds[w] == -1:
                            Ds[w] = k
                            k -= 1
                            queue.append(w)

    ans = 1
    for i in range(1, N + 1):
        if Ds[i] <= 0:
            return 0
        ans *= Ds[i]
        ans %= 1000000007
    return ans % 1000000007

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N - 1)]
    print(solve(N, K, ABs))
a,b =map(int,input().split())
k = a%3
s = b%3
if k ==s and k != 0:
  print("Impossible)
else:
  print("Possible")

### FIXED CODE ###

a,b =map(int,input().split())
k = a%3
s = b%3
if k == s and k != 0:
  print("Impossible")
else:
  print("Possible")
k,x=map(int,input().split())
sum=''
for i in range(x-k+1,k+x):
  sum+=i
print(sum)

### FIXED CODE ###

a,b=map(int,input().split())
x=[]
for i in range(b-a+1,b+a):
  x.append(str(i))
print(' '.join(x))