Harryxun/stf_run huggingface dataset:
N=int(input())
A,B=map(int,input().split())
p = list(map(int,input().split()))
c=[]
d=[]
e=[]
for i in range(N):
    if p[i]<=A:
        c.append(p[i])
    if A+1 <= p[i] <= B:
        d.append(p[i])
    if B+1 <= p[i]:
        e.append(p[i])

        
print(min(len(c),len(d),len(e))))


### FIXED CODE ###

N=int(input())
A,B=map(int,input().split())
p = list(map(int,input().split()))
c=[]
d=[]
e=[]
for i in range(N):
    if p[i]<=A:
        c.append(p[i])
    if A+1 <= p[i] <= B:
        d.append(p[i])
    if B+1 <= p[i]:
        e.append(p[i])

        
print(min(len(c),len(d),len(e)))
n=int(input())
if n%2==0:
    print(1/2)
else:
    print((n+1)/2/n

### FIXED CODE ###

n=int(input())
if n%2==0:
    print(1/2)
else:
    print((n+1)/2/n)
import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

nums=[]

num=0
pow10=1
for i in range(135):
    num+=pow10
    if i%9==8: pow10*=10
    nums.append(num)

# add a few possible answers
for i in range(1,14):
    for j in range(1,10):
        t=str(j)+"8"+"9"*i
        nums.append(int(t))

# remove some bad numbers
nums.sort()
for i in range(len(nums))[::-1]:
    if i>=len(nums): continue
    ratio=nums[i]/(i+1)
    for j in range(i)[::-1]:
        ratio2=nums[j]/(j+1)
        if ratio2>ratio:
            nums.pop(j)

#print(len(nums))

k=int(input())
for i in range(k):
    print(nums[i])


### FIXED CODE ###


import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

nums=[]

num=0
pow10=1

# add a few possible answers
for i in range(16):
    t="9"*i
    if t!="": nums.append(int(t))
    for j in range(1,1000):
        t=str(j)+"9"*i
        if len(t)>15: continue
        nums.append(int(t))

def dsum(x):
    t=0
    while x:
        t+=x%10
        x//=10
    return t

# remove some bad numbers
out=[]
rat=[]
for i in sorted(set(nums)):
    j=i/dsum(i)
    while rat and rat[-1]>j:
        out.pop(-1)
        rat.pop(-1)
    out.append(i)
    rat.append(j)

#print(len(out))

#for i in range(len(out)): print(i,out[i],rat[i])

#for i in range(len(nums)):
#    print(i,dsum(nums[i]),nums[i]/dsum(nums[i]))

k=int(input())
for i in range(k):
    print(out[i])
r, g, b, n = [int(i) for i in input().split()]
total = 0

rm = n//r
for i in range(rm + 1):
	for j in range(gm + 1):
		bd = n - r * i - g * j
		if bd % b == 0:
			total += 1
print(total)


### FIXED CODE ###

r, g, b, n = [int(i) for i in input().split()]
total = 0
rm = n//r
for rn in range(rm + 1):
	gm = (n - rn * r) // g
	for gn in range(gm + 1):
		bd = n - r * rn - g * gn
		if bd % b == 0:
			total += 1
print(total)
N = int(input())
import math
if N == 1:
    print(1)
else:
    for a in reversed(range(1, (int(math.sqrt(N)))+1)):
        if N % a == 0:
            b = N/a
            ans=max(len(str(int(a))), len(str(int(b))))
            break
print(ans)



### FIXED CODE ###

N = int(input())
import math
if N == 1:
    print(1)
else:
    for a in reversed(range(1, (int(math.sqrt(N)))+1)):
        if N % a == 0:
            b = N/a
            ans=max(len(str(int(a))), len(str(int(b))))
            break
    print(ans)
N=int(input())
l=[]
for i in range(N):
  s,p=input(i).split()
  l.append((s,-int(p),i+1))

list=sorted(l,key=lambda x:(x[0],x[1]))
for i in list:
  print(l[2])


### FIXED CODE ###

N=int(input())
l=[]
for i in range(N):
  s,p=input().split(" ")
  l.append((s,-int(p),i+1))
 
l2=sorted(l,key=lambda x:(x[0],x[1]))
for l in l2:
  print(l[2])
N, M, K = map(int,input().split())
tree = [-1 for i in range(N)]
fc = [0 for i in range(N)]
bc = [0 for i in range(N)]
ans = [0 for i in range(N)]

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if rootx < rooty:
        x , y = y, x
    tree[rooty] += tree[rootx]
    tree[rootx] = rooty

for i in range(M):
    a, b = map(int,input().split())
    fc[a-1] += 1
    fc[b-1] += 1
    unite(a-1, b-1)

for i in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -tree[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)

### FIXED CODE ###

N, M, K = map(int,input().split())
uf = [-1 for _ in range(N)]
fc = [0] * N
bc = [0] * N
ans = [0] * N

def find(x):
    # x を引数に取り、xのroot番号を取得するメモ化再帰
    if uf[x] < 0:
        return x
    uf[x] = find(uf[x])
    return uf[x]

def unite(x, y):
    # x, y を引数に取り、x(自分)をy(相手)のrootに接続する関数
    x = find(x)
    y = find(y)
    if x == y:
        return
    if x < y:
        x , y = y, x
    uf[y] += uf[x]
    uf[x] = y

for m in range(M):
    a, b = map(int,input().split())
    fc[a-1] += 1
    fc[b-1] += 1
    unite(a-1, b-1)

for k in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -uf[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)
N, M = map(int, input().split())
L, R = 1, N

def merge_list(list):
    # sortずみ
    return (list[-1][0], min(map(lambda x: x[1], list)))

data = []
for i in range(0, M):
    l, r = input().split()
    data.append((int(l), int(r)))
data = sorted(data, key=lambda x: x[0])

import math
logM = int(math.floor(math.log2(M)))

# 2つずつくみでしょりしたい
def saiki(totyuu):
    for i in range(0, logM):
        if len(totyuu) < 1000:
            mid = int(math.floor(len(totyuu)/2))
            m1 = merge_list(totyuu[:mid])
            m2 = merge_list(totyuu[mid:])
            return merge_list([m1, m2])
        else:
            return merge_list([saiki(totyuu[:mid]), saiki(totyuu[mid:])])

data = saiki(data)
L = data[0]
R = data[1]

print(max(0, R-L+1))

### FIXED CODE ###

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

Ls = []
Rs = []
for i in range(0, M):
    l, r = input().split()
    Ls.append(int(l))
    Rs.append(int(r))

maxL = max(Ls)
minR = min(Rs)
result = max(0, minR-maxL+1)

print(result)
# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)


cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)

### FIXED CODE ###

# D - Ki TLE
import sys
sys.setrecursionlimit(10**7)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
    
lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

cnt = [0]*N
for p,x in lst:
    cnt[p] += x 
    
seen = [False]*N
def dfs(v):
    seen[v] = True# v を訪問済みにする
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        cnt[next_v] += cnt[v] 
        dfs(next_v)
dfs(0)
print(*cnt)
x=int(input())
if x==0;
    print(1)
else;
    print(0)

### FIXED CODE ###

x=int(input())
if x==0:
    print("1")
else:
    print("0")
a,b,c = int(input()).split()
if a=b and c != b and c != a:
  print('Yes')
elif b=c and a != b and a != c:
  print('Yes')
elif c=a and b != a and b != c:
  print('Yes')
else: print('No')

### FIXED CODE ###

a,b,c = input().split()
if a==b and c != b and c != a:
  print('Yes')
elif b==c and a != b and a != c:
  print('Yes')
elif c==a and b != a and b != c:
  print('Yes')
else: print('No')
N = int(input())
S = input()

ans = ""

for x in range(S)
	num=(ord(x) + N)
  	if(num >90):
    	num=64+num%90
    ans += chr(num)
print(ans)



### FIXED CODE ###

cal = {"SUN":0,"MON":1,"TUE":2,"WED":3,"THU":4,"FRI":5,"SAT":6,}

S=input()
print(7-cal[S])
N = int(input())
A =  []
#l1 = input().split()
#for i in l1:
#    A.append(int(i))
B = []
#l2 = input().split()
#for i in l2:
#    B.append(int(i))
for n in N:
    A.append(int(input()))
for n in N:
    B.append(int(input()))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    ar1.sort(reverse = True)
    ar2.sort(reverse = True)
    b = 0
    for a in ar1:
        while a > ar2[b]:
            ar2[b] = 0
            a -= ar2[b]
            b += 1
        ar2[b] -= a
        ar2.sort(reverse = True)
        if a == ar1[-1] and ar2[b] != 0:
            z = 1
    ans = 0
    for i in ar2:
        if i == 0:
            z +=1
    ans = len(ar1) + z
    print(ans)

### FIXED CODE ###

N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        s = sum(ar1)
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= s:
                b = i+1
                break
        print(len(ar1)+b)
currency = list(map(int,input().split()))

gra = [[0 for i in range(n+1)] for i in range(m)]

for i in range(m):
    for j in range(1,n+1):
        if i == 0:
            gra[i][j] = j
        else:
            if j>=currency[i]:
                gra[i][j] = min(gra[i-1][j],gra[i][j-currency[i]]+1)
            else:
                gra[i][j] = gra[i-1][j]

print(gra[m][n+1])

### FIXED CODE ###

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

currency = sorted(map(int,input().split()))

gra = [float('inf')]*(n+1)
gra[0] = 0
for i in range(m):
    for j in range(currency[i],n+1):
        gra[j] = min(gra[j],gra[j-currency[i]]+1)

print(gra[n])
a=[int(input()) for i in range(5)]
minn=0
for i in a:
  minn=min(minn,i%10)
  summ+=(int(i)+9)//10
print(summ+minn)

### FIXED CODE ###

a=[int(input()) for i in range(5)]
minn,summ=10,0
for i in a:
  minn=min(minn,(i-1)%10)
  summ+=(i+9)//10
print(summ*10+minn-9)
from numpy import *
N=int(input())
x_a=[0]*N
y_a=[0]*N
r_a=[0]*N
x_b=[0]*N
y_b=[0]*N
r_b=[0]*N
for i in range(N):
    x_a[i],y_a[i],r_a[i],x_b[i],y_b[i],r_b[i]=map(float,input().split())
for i in range(N):
    a=array([x_a[i]-x_b[i],y_a[i]-y_b[i]])
    AB=linalg.norm(a)
    r_diff=abs(r_a[i]-r_b[i])
    if AB > r_a[i]+r_b[i]:
        print(0)
    elif r_a[i]+r_b[i] >= AB and AB >= r_diff:
        print(1)
    elif r_diff > AB:
        if r_a[i] > r_b[i]:
            print(2)
        else:
            print(-2)

### FIXED CODE ###


N=int(input())
x_a=[0]*N
y_a=[0]*N
r_a=[0]*N
x_b=[0]*N
y_b=[0]*N
r_b=[0]*N
for i in range(N):
    x_a[i],y_a[i],r_a[i],x_b[i],y_b[i],r_b[i]=map(float,input().split())
for i in range(N):
    AB=((x_a[i]-x_b[i])**2+(y_a[i]-y_b[i])**2)**(1/2)
    r_diff=abs(r_a[i]-r_b[i])
    if AB > r_a[i]+r_b[i]:
        print(0)
    elif r_a[i]+r_b[i] >= AB and AB >= r_diff:
        print(1)
    else:
        if r_a[i] > r_b[i]:
            print(2)
        else:
            print(-2)
z,*s=map(len,input().split('T')+['']);l=sum(s,0);Y=1<<l;X=Y<<z
for t,u in zip(s[::2],s[1::2]):Y=Y>>t|Y<<t;X=X>>u|X<<u
x,y=map(int,input().split());print("Yes"*(X>>l+x&Y>>l+y&1)or"No")

### FIXED CODE ###

s=input()
x,y=map(int, input().split())
cnt = 0; mode = 2
l = len(s) # l + 1 + l
X = Y = 1 << l
for c in s:
    if c is 'F':
        cnt += 1
    else:
        if mode == 0:
            X = (X >> cnt) | (X << cnt)
        elif mode == 1:
            Y = (Y >> cnt) | (Y << cnt)
        else:
            X = X << cnt
            mode = 0
        cnt = 0; mode ^= 1
if cnt > 0:
    if mode == 0:
        X = (X >> cnt) | (X << cnt)
    elif mode == 1:
        Y = (Y >> cnt) | (Y << cnt)
    else:
        X = X << cnt
if (X >> (l + x)) & 1 and (Y >> (l + y)) & 1:
    print("Yes")
else:
    print("No")
# -*- coding: utf-8 -*-
"""
Created on Wed May  6 02:13:01 2020

@author: shinba
"""

N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i+1)
    elif S[i] == "G":
        G.append(i+1)
    else:
        B.append(i+1)

ans = len(R)*len(G)*len(B)

m = min(B)
M = max(B)

for i in R:
    for j in G:
        a = 2*j - i 
        b = (i+j)//2 if (i+j)%2 == 0 else 0
        c = 2*i - j
        if m <= a <= M:
            if S[a-1] == "B":
                ans -= 1
        if b != 0 and S[b-1] == "B":
            ans -= 1
        if m <= c <= M:
            if S[c-1] == "B":
                ans -= 1
            
print(ans)
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed May  6 02:13:01 2020

@author: shinba
"""
import sys

N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i+1)
    elif S[i] == "G":
        G.append(i+1)
    else:
        B.append(i+1)

if R==[] or G==[] or B==[]:
    print(0)
    sys.exit()
    
ans = len(R)*len(G)*len(B)

m = min(B)
M = max(B)

for i in R:
    for j in G:
        a = 2*j - i 
        b = (i+j)//2 if (i+j)%2 == 0 else 0
        c = 2*i - j
        if m <= a <= M:
            if S[a-1] == "B":
                ans -= 1
        if b != 0 and S[b-1] == "B":
            ans -= 1
        if m <= c <= M:
            if S[c-1] == "B":
                ans -= 1
            
print(ans)
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for i in range(H)]

white = 0

for i in range(H):
    white += s[i].count(".")


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

g = [[10**9]*W for i in range(H)]
g[0][0] = 0
for i in range(H*W):
    x, y = q.popleft()
    if (x, y) == (H-1, W-1):
        break
    else:
        if x < H-1 and s[x+1][y] == ".":
            if g[x+1][y] == 10**9:
                q.append((x+1, y))
            g[x+1][y] = min(g[x+1][y], g[x][y]+1)
        if y < W-1 and s[x][y+1] == ".":
            if g[x][y+1] == 10**9:
                q.append((x, y+1))
            g[x][y+1] = min(g[x][y+1], g[x][y]+1)
        if x > 0 and s[x-1][y] == ".":
            if g[x-1][y] == 10**9:
                q.append((x-1, y))
            g[x-1][y] = min(g[x-1][y], g[x][y]+1)
        if y > 0 and s[x][y-1] == ".":
            if g[x][y-1] == 10**9:
                q.append((x, y-1))
            g[x][y-1] = min(g[x][y-1], g[x][y]+1)
if g[H-1][W-1] == 10**9:
    print(-1)
else:
    print(white - (g[H-1][W-1]+1))


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
s = [list(input()) for i in range(H)]

white = 0

for i in range(H):
    white += s[i].count(".")

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

g = [[10**9]*W for i in range(H)]
g[0][0] = 0
for i in range(H*W):
    if len(q) == 0:
        break
    x, y = q.popleft()
    if (x, y) == (H-1, W-1):
        break
    else:
        if x < H-1 and s[x+1][y] == ".":
            if g[x+1][y] == 10**9:
                q.append((x+1, y))
            g[x+1][y] = min(g[x+1][y], g[x][y]+1)
        if y < W-1 and s[x][y+1] == ".":
            if g[x][y+1] == 10**9:
                q.append((x, y+1))
            g[x][y+1] = min(g[x][y+1], g[x][y]+1)
        if x > 0 and s[x-1][y] == ".":
            if g[x-1][y] == 10**9:
                q.append((x-1, y))
            g[x-1][y] = min(g[x-1][y], g[x][y]+1)
        if y > 0 and s[x][y-1] == ".":
            if g[x][y-1] == 10**9:
                q.append((x, y-1))
            g[x][y-1] = min(g[x][y-1], g[x][y]+1)
if g[H-1][W-1] == 10**9:
    print(-1)
else:
    print(white - (g[H-1][W-1]+1))
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
for i in range(N):#最大公倍数
    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//gcd(x,y)*y, A)
 
for i in range(N):
    ans+=lcm//A[i]


print(ans%mod)
    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)
from collections import deque

H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
S = ["##"+input()+"##" for _ in range(H)]
for i in range(2):
    S.insert(0, "#"*(W+4))
    S.append("#"*(W+4))

inf = int(1e9)
cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
cost0 = deque()
ans = -1

cost0.append((C[0]+1, C[1]+1, 0))
cost[C[0]+1][C[1]+1] = 0

move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

cost1 = deque()

while cost0:
    h, w, c = cost0.popleft()
    cost1.append((h, w, c))

    for i, j in move:
        dh = h+i
        dw = w+j
        if S[dh][dw] == "." and c < cost[dh][dw]:
            cost[dh][dw] = c
            cost0.appendleft((dh, dw, cost[dh][dw]))

    if len(cost0) == 0:
        while cost1:
            h, w, c = cost1.popleft()
            for i, j in warp:
                dh = h+i
                dw = h+j
                if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                    cost[dh][dw] = c+1
                    cost0.append((dh, dw, cost[dh][dw]))

    if cost[D[0]+1][D[1]+1] != inf:
        ans = cost[D[0]+1][D[1]+1]

print(ans)


### FIXED CODE ###

from collections import deque


def solve():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    S = ["##"+input()+"##" for _ in range(H)]
    for i in range(2):
        S.insert(0, "#"*(W+4))
        S.append("#"*(W+4))

    inf = int(1e9)
    cost = [[inf for _ in range(W+4)] for _ in range(H+4)]
    cost0 = deque()
    ans = -1

    cost0.append((CH+1, CW+1, 0))
    cost[CH+1][CW+1] = 0

    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]

    cost1 = deque()

    while cost0:
        h, w, c = cost0.popleft()
        cost1.append((h, w, c))

        for i, j in move:
            dh = h+i
            dw = w+j
            if S[dh][dw] == "." and c < cost[dh][dw]:
                cost[dh][dw] = c
                cost0.appendleft((dh, dw, cost[dh][dw]))

        if len(cost0) == 0:
            while cost1:
                h, w, c = cost1.popleft()
                for i, j in warp:
                    dh = h+i
                    dw = w+j
                    if S[dh][dw] == "." and c+1 < cost[dh][dw]:
                        cost[dh][dw] = c+1
                        cost0.append((dh, dw, cost[dh][dw]))

        if cost[DH+1][DW+1] != inf:
            ans = cost[DH+1][DW+1]

    print(ans)


if __name__ == "__main__":
    solve()
N,K = list(map(int,input().split()))

tree = [[] for _ in range(N+10)]

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

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(N):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
 

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

tree = [[] for _ in range(N+10)]

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

ans = []
def wfs(now,back):
    if now != 0:
        cnt = K - 2 #まず一個上のを引く。
    else:
        cnt = K - 1
    for nxt in tree[now]:
        if nxt != back:
            ans.append(cnt)
            cnt = cnt - 1
            wfs(nxt,now)

ans.append(K)
wfs(0,-1)

ans2 = 1
for j in range(len(ans)):
    ans2 = (ans2 * ans[j]) % (10**9+7)
print(ans2)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

dxy=[(-1,0),(0,1),(0,-1),(1,0)]
for i in range(h):
  for j in range(w):
    if s[i][j]=="#":
      f=False
      for x,y in dxy:
        
        if 0<=i+x<=h-1 and 0<=j+y<=w-1 and s[i+x][j+y]=="#":
          f=True
      
      if not f:
        print("No")
        exit()
        
        
if f:
  print("Yes")






### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

dxy=[(-1,0),(0,1),(0,-1),(1,0)]
for i in range(h):
  for j in range(w):
    if s[i][j]=="#":
      f=False
      for x,y in dxy:
        
        if 0<=i+x<=h-1 and 0<=j+y<=w-1 and s[i+x][j+y]=="#":
          f=True
      
      if not f:
        print("No")
        exit()
        
        

print("Yes")
n, k = [int(i) for i in input().split()]
if k > (n - 1)*(n - 2) // 2:
    print(-1)
else:
    ed = []
    for i in range(1, n):
        ed.append(" ".join(map(str, [1, i + 1])))
    kk = (n - 1)*(n - 2) - k
    if not kk:
        print(len(ed))
        print("\n".join(ed))
        exit()
    for i in range(1, n):
        for j in range(1, n):
            ed.append(" ".join(map(str, [i + 1, j + 1])))
            kk -= 1
            if not kk:
                print(len(ed))
                print("\n".join(ed))
                exit()


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
if k > (n - 1)*(n - 2) // 2:
    print(-1)
else:
    ed = []
    for i in range(1, n):
        ed.append(" ".join(map(str, [1, i + 1])))
    kk = (n - 1)*(n - 2)//2 - k
    if not kk:
        print(len(ed))
        print("\n".join(ed))
        exit()
    for i in range(1, n):
        for j in range(i+1, n):
            ed.append(" ".join(map(str, [i + 1, j + 1])))
            kk -= 1
            if not kk:
                print(len(ed))
                print("\n".join(ed))
                exit()
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200001)
N,Q = map(int,input().split())
ab = [ tuple(map(int,input().split())) for i in range(N-1) ]
px = [ tuple(map(int,input().split())) for i in range(Q) ]
dic = {}
dic2=[0]*(N+1)
dic3=[0]*N

for i in range(N):
    dic[i+1] = []
for i in range(N-1):
    dic[ab[i][0]].append(ab[i][1])
ab=0
for i in range(Q):
    dic2[px[i][0]] += px[i][1]
px=0
def rec(now_node,prevval):
    nowval = prevval + dic2[now_node]
    dic3[now_node-1] = nowval
    for elem in dic[now_node]:
        rec(elem,nowval)
rec(1,0)
res = [str(dic3[i-1]) for i in range(1,N+1)]
print(' '.join(res))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
ab = [ tuple(map(int,input().split())) for i in range(N-1) ]
px = [ tuple(map(int,input().split())) for i in range(Q) ]
dic = {}
dic2=[0]*(N+1)
dic3=[0]*N

for i in range(N):
    dic[i+1] = []
for i in range(N-1):
    tmp1 = ab[i][0]
    tmp2 = ab[i][1]
    dic[tmp1].append(tmp2)
    dic[tmp2].append(tmp1)
ab=0
for i in range(Q):
    dic2[px[i][0]] += px[i][1]
px=0
def rec(now_node,prevval):
    nowval = prevval + dic2[now_node]
    dic3[now_node-1] = nowval
    tg_list = dic[now_node][:]
    for elem in tg_list:
        dic[elem].remove(now_node)
        rec(elem,nowval)
rec(1,0)
res = [str(dic3[i-1]) for i in range(1,N+1)]
print(' '.join(res))