Harryxun/stf_run huggingface dataset:
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    branch[a]|={b}
    branch[b]|={a}
jisuu=[len(branch[i]) for i in range(N+1)]
def dfs1(check,visited,P):
    while len(check)>0:
        now=check.pop()
        for nex in branch[now]:
            if nex not in visited:
                if jisuu[nex]==1:
                    return P[now]+[nex]
                else:
                    check|={nex}
                    visited|={nex}
                    P[nex]=P[now]+[nex]
def dfs2(check,visited,P,goal):
    while len(check)>0:
        now=check.pop()
        for nex in branch[now]:
            if nex not in visited:
                if nex==goal:
                    return P[now]+[nex]
                else:
                    check|={nex}
                    visited|={nex}
                    P[nex]=P[now]+[nex]
if jisuu.count(1)>=2:
    start=jisuu.index(1)
    visited={start}
    check={start}
    P=[0]*(N+1)
    P[start]=[start]
    path=dfs1(check,visited,P)
else:
    for i in range(1,1+N):
        if jisuu[i]==2:
            a,b=list(branch[i])
            if jisuu[a]==2:
                start=i
                goal=a
                nex=b
                break
            elif jisuu[b]==2:
                start=i
                goal=b
                nex=a
                break
    visited={start,nex}
    check={nex}
    P=[0]*(N+1)
    P[start]=[start]
    P[nex]=[start,nex]
    path=dfs2(cehck,visited,P,goal)
print(len(path))
print(" ".join(map(str,path)))

### FIXED CODE ###

N,M=map(int,input().split())
from collections import deque,defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    branch[a-1]|={b-1}
    branch[b-1]|={a-1}
path=deque([0])
for x in branch[0]:
    path.append(x)
    break
used=set(path)
while True:
    A,B=False,False
    if len(branch[path[0]]-used)==0:
        A=True
    else:
        for x in branch[path[0]]:
            if x in used:
                continue
            path.appendleft(x)
            used|={x}
            break
    if len(branch[path[-1]]-used)==0:
        B=True
    else:
        for x in branch[path[-1]]:
            if x in used:
                continue
            path.append(x)
            used|={x}
            break
    if A and B:
        break
path=[p+1 for p in path]
print(len(path))
print(" ".join(map(str,path)))
n = int(input())
s = input()

alpha = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')

for i in len(s)
  s[i] = alpha[(alpha.index(s[i])+n)%26]

print(''.join(s))


### FIXED CODE ###

n = int(input())
s = list(input())

alpha = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')

for i in range(len(s)):
  s[i] = alpha[(int(alpha.index(s[i]))+n)%26]

print(''.join(s))
s, t = map(str,input.split())
a, b = map(int,input.split())
u = input()
if s == u:
    a -= 1
if t == u:
    b -= 1
print("{0} {1}".format(a,b))

### FIXED CODE ###

S, T = map(str,input().split())
A, B = map(int,input().split())
U = input()
 
if S == U: A -= 1
if T == U: B -= 1
print("{0} {1}".format(A,B))
A,B,T = map(int,input().split())

C = int((T + 1/2)//A)
ans = B*C

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May 30 18:10:37 2019

@author: またの
"""

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = 0

for i in range(N):
    if V[i]-C[i]>0:
        ans += V[i]-C[i]
print(ans)
n=int(input())
dat = list(map(int, input().split()))
dan = []
for e in dat:
    e = str(bin(e))
    e=e[2:]
       
for i in range(n):
      j = -1
     while j > -len(dat[i]):
          if dat[i][j]=='1':
               dan.append(-j-1)
               break
          else:
               j = j - 1
           
print(min(dan))



### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
x = input()
if x >= 30:
  print("Yes")
else:
  print("No)

### FIXED CODE ###

x = int(input())
if x>= 30:
  print("Yes")
else:
  print("No")
N = int(input())
T,A = int(i) for i in input().split()
Hi = [int(i) for i in input().split()]
Ave = T - i*0.006 for i in Hi
Result = [abs(i) for i in (Ave - A)]
print(index(min(Result))+1)


### FIXED CODE ###

N = int(input())
T,A = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
sub = [0 for i in range(N)]
for i in range(N):
    sub[i] = abs(A - (T - 0.006*H[i]))
print(sub.index(min(sub))+1)
rom math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def main():
    N = input()
    K = int(input())

    ans = func(N, K)

    print(ans)

def func(N, K):
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    ret += func('9'* l, K)

    # ret += (n - 1) * nCr(l-1, K - 2) * 9 ** (K - 1)
    # ret += nCr(l-1, K - 1) * 9 ** K 

    return ret
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def main():
    N = input()
    K = int(input())

    ans = func(N, K)

    print(ans)

def func(N, K):
    N = N.lstrip('0')
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    if l >= K:
        ret += func('9'* l, K)

    # ret += (n - 1) * nCr(l-1, K - 2) * 9 ** (K - 1)
    # ret += nCr(l-1, K - 1) * 9 ** K 

    return ret
    

if __name__ == '__main__':
    main()
N, M = map(int, input().split())
ac = 0
is_AC = [False] * (10 ** 5) + 1
WA_cnt = [0] * (10 ** 5) + 1
for i in range(M):
    p, s = input().split()
    p = int(p)
    if s == 'WA':
        if is_AC[p]:
            continue
        else:
            WA_cnt[p] += 1
    else:
        if is_AC[p]:
            continue
        else:
            is_AC[p] = True
            ac += 1

print(ac, sum(WA_cnt))



### FIXED CODE ###

N, M = map(int, input().split())
ac = 0
is_AC = [False] * (N + 1)
WA_cnt = [0] * (N + 1)
for i in range(M):
    p, s = input().split()
    p = int(p)
    if s == 'WA':
        if is_AC[p]:
            continue
        else:
            WA_cnt[p] += 1
    else:
        if is_AC[p]:
            continue
        else:
            is_AC[p] = True
            ac += 1

wa = 0
for i in range(N + 1):
    if is_AC[i]:
        wa += WA_cnt[i]
print(ac, wa)
'''
うまくいかなかったパターン
1 4
1 WA
1 WA
1 WA
1 WA
'''
li = list(map(int,input().split()))
li.append(a+b)
for i in range(3):
    if li[i] % 3 == 0:
        print("Possible")
        exit()
print("Impossible")

### FIXED CODE ###

li = list(map(int,input().split()))
li.append(li[0]+li[1])
for i in range(3):
    if li[i] % 3 == 0:
        print("Possible")
        exit()
print("Impossible")
s = input()
k = 'keyence'
i = 0
flag = 0
ans = 'YES'
for a in s:
    if a == k[i]:
        i += 1
        if flag == 0:
            flag = 1 # reading 1st half
        elif flag == 2:
            flag = 3 # reading 2nd half
    elif flag == 1: # end of 1st half
        flag = 2 # reading middle
    elif flag == 3:
        ans = 'NO'
        break

if flag == 0:
    ans = 'NO'
print(ans)

### FIXED CODE ###

s = input()
k = 'keyence'

for i in range(len(s)):
    for j in range(i,len(s)):
        if s[:(i+1)]+s[j:] == 'keyence':
            print('YES')
            exit()

print('NO')
a = int(input())
b = int(input())
c = int(input())
x = int(input())
 
 result= 0
 
for xx in range(a+1):
    A = 500*xx
    for y in range(b+1) :
        B = 100*y
        for z in range(c+1):
            C = 50*z
            if x == A+B+C:
                result += 1
            else:
                continue
 
 
print(result)

### FIXED CODE ###

#!/usr/bin/env python3
from itertools import product
import sys
 
 
def solve(AA: int, BB: int, CC: int, XX: int):
    print(sum(
        1
        for a, b, c in product(range(AA + 1), range(BB + 1), range(CC + 1))
        if a * 500 + b * 100 + c * 50 == XX
    ))
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(A, B, C, X)
 
 
if __name__ == '__main__':
    main()
a = input()
num=0
b=[]
for i in range(len(a)):
  if a[i] in 'ATGC':
    num+=1
  else:
    b.append(num)
    num=0
print(max(b))
    

### FIXED CODE ###

a = input()+"a"
num=0
b=[]
for i in a:
  if i in 'ATGC':
    num+=1
  else:
    b.append(num)
    num=0
print(max(b))
a,b = map(int,input(),split())
print(a * b,(a + b) * 2)


### FIXED CODE ###


a,b =(int(x) for x in input().split())
print(a * b, (a+b) * 2)
p,q,r = map(int, input().split())
print(min(p+q,q+r,r+s))

### FIXED CODE ###

p,q,r = map(int, input().split())
ans = min(p+q, q+r, r+p)
print(ans)
#! /usr/bin/env python3

# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
from collections import Counter, deque, defaultdict

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

mi = 10000000

c = Counter(S)
A = N - c["#"]
B = N - c["."]

for i in range(1, N):
    l = S[:i]
    r = S[i:]
    a = l.count("#") + r.count(".")
    if mi > a:
        mi = a

print(min(mi, A, B))


### FIXED CODE ###

from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
from collections import Counter, deque, defaultdict

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

mi = 10000000

c = Counter(S)
A = N - c["#"]
B = N - c["."]

l = 0
r = c["."]

for i in range(0, N):

    if S[i] == "#":
        l += 1
    else:
        r -= 1
    a = l + r
    if mi > a:
        mi = a

print(min(mi, A, B))
import pandas as pd

### FIXED CODE ###

import itertools
N, M, X = map(int, input().split())
C = []
A = dict()
for i in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    for j in range(1, M+1):
        if j in A:
            A[j].append(CA[j])
        else:
            A[j] = [CA[j]]

cost = float("inf")

for i in range(1, N+1):
    for pm in itertools.combinations(list(range(1, N+1)), r=i):
        c = 0
        k = dict()
        for p in pm:
            c += C[p-1]

            for m in range(1, M+1):
                if m in k:
                    k[m] += A[m][p - 1]
                else:
                    k[m] = A[m][p - 1]

        if min(k.values()) >= X:
            cost = min(cost, c)


if cost == float("inf"):
    print(-1)
else:
    print(cost)
x = list(map(int, input().split()))
x_l = [1,2,3,4,5]

for i in range(ren(x_l)):
    if x_l[i] != x[i]:
        print(i+1)

### FIXED CODE ###

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

for i in range(len(x)):
    if x[i] == 0:
        print(i+1)
N, K = map(int, input().split())
x = list(map(int, input().split()))
ans = 3*10**8

for i in range(N-K+1):
    ans1 = abs(x[i])+abs(x[i]-x[i+N-K])
    ans2 = abs(x[i+N-K])+abs(x[i]-x[i+N-K])
    ans = min(ans, ans1, ans2)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
x = list(map(int, input().split()))
ans = 3*10**8

for i in range(N-K+1):
    ans1 = abs(x[i])+abs(x[i]-x[i+K-1])
    ans2 = abs(x[i+K-1])+abs(x[i]-x[i+K-1])
    ans = min(ans, ans1, ans2)
print(ans)
S = str(input())

S_list =list(S)


A = 0
for i in range(0,len(S_list)-1):
    for j in range(i+3,len(S_list)+1):
        P = 0
        S_list_P = S_list[i:j]
        for k in range(0,j-i):
            P += int(S_list_P[k])* 10 ** (j-i-k-1)

        if P % 2019== 0:
            A += 1



print(A)


### FIXED CODE ###

S,W = map(int,input().split())

if S <= W:
    print("unsafe")

else :
    print("safe")
N, M = [int(i) for i in input().split()]

dp = [-1] * 10100
dp[0] = 1
dp[1] = 1

for i in range(M):
    a = int(input())
    dp[a] = 0

for i in range(N):
    if dp[i+2] == 0: continue
    dp[i+2] = dp[i]+dp[i+1]

print(dp[N] % 1000000007)

### FIXED CODE ###

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

dp = [0, 1]
for i in range(N):
    if i+1 in A: dp.append(0)
    else: dp.append(dp[i]+dp[i+1])
print(dp[N+1]%1000000007)
print(input.count('1'))

### FIXED CODE ###

print(input().count('1'))
s = input()
b = [0]*25
for c in s:
  b[ord(c)-ord("a")]+=1
for i,c in enumerate(b):
  if c == 0:
    print(chr(i+ord("a")))
    exit()
print("None")

### FIXED CODE ###

s = input()
b = [0]*26
for c in s:
  b[ord(c)-ord("a")]+=1
for i,c in enumerate(b):
  if c == 0:
    print(chr(i+ord("a")))
    exit()
print("None")
a,b,k = map(int,input().split())
if a-k >= 0;
  print(a)
elif  a+b-k=< 0;
	print(0)
else;
	print(0)

### FIXED CODE ###

a,b,k = map(int,input().split())
if a+b-k <= 0:
  print(0,0)
elif a-k <= 0:
  print(0,b+a-k)
else:
  print(a-k,b)
X,Y = input().split()

if X > Y:
    print(">")
elif X==Y:
    priint("=")
else:
    print("<")

### FIXED CODE ###

X,Y = input().split()
 
if X > Y:
    print(">")
elif X==Y:
    print("=")
else:
    print("<")
a,b,c =input().split(",")
mylist = [int(a),int(b),int(c)]
mylist.sort()
print(sum(mylist[0:2]))

### FIXED CODE ###

a,b,c =input().split(" ")
mylist = [int(a),int(b),int(c)]
mylist.sort()
print(sum(mylist[0:2]))
h , w = (int(i) for i in input().split())
a =[]
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]


for i in range(h):
    a.append(input())
    
f = True
def check(x,y):
    if a[x][y] =='.':
        return True
    for n in range(4):
        i = dx[n]
        j = dy[n]
#        print(a[x+i][y+j])
        if 0 <= x+i < h and 0 <= y + j < w and a[x+i][y+j]=='#':
            #print(x+i,y+j)
            return True
    return False
#print(check(0,3))
f = True
for i in range(w):
    for j in range(h):
        l = check(i,j)
        if not(l) and f:
            print ("No")
            f = False
if(f):
    print("Yes")


### FIXED CODE ###

H ,W = [int(i) for i in input().split(' ')]
s = []
#print(s)
for i in range(H):
    line = input()
    lis = []
    for str in line:
        lis.append(str)
    s.append(lis)


def drawable(h,w):
    for i in [-1,1]:
        if 0 <= w+i < W:
#            print(h,w+i)
            if s[h][w+i] =='#':
                return True
    for i in [-1,1]:
        if 0 <= h+i < H:
            if s[h+i][w] =='#':
                return True

    return False

flag = True
for i in range(H):
    for j in range(W):
#        print(i,j)
        if s[i][j]=='#' and not(drawable(i,j)):
           flag = False 

if flag:
    print("Yes")
else:
    print("No")
s = str(input())
t = str(input())
ans = 10000
for i in range(len(s)-len(t)+1):
  num = 0
  for j in range(len(t)):
    if s[i+j] != t[i]:
      num += 1
  ans = min(ans,num)
print(ans)

### FIXED CODE ###

s = str(input())
t = str(input())
ans = 10000
for i in range(len(s)-len(t)+1):
  num = 0
  for j in range(len(t)):

    if s[i+j] != t[j]:
      num += 1
  ans = min(ans,num)
print(ans)
from collections import Counter

num=Counter(input())
 ans="YES"  
for X in num.values():
    if X%2!=0:
        ans="NO"
   
print(ans)

### FIXED CODE ###

from collections import Counter
w = Counter(input())
ans = "Yes"
for i in w.values():
    if i % 2 != 0:
        ans = "No"
print(ans)
import math

n, k = [int(x) for x in input().split()]

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

if n <= k:
    print("0")

s_n = sorted(h_n)

log_sum = math.log(sum(s_n[:n - k]))

print(round(math.exp(log_sum)))

### FIXED CODE ###

import math

n, k = [int(x) for x in input().split()]

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

if n <= k:
    print("0")
else:
    s_n = sorted(h_n)

    print(sum(s_n[:n-k]))
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            idx = bisect_right(dp, A[v])
            old = dp[idx]
            dp[idx] = A[v]
            length[v] = length[p]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
                dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(2*10**5)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            length[v] = length[p]
            idx = bisect_left(dp, A[v]) # bisect_rightだとdpに重複する値を書き込んでしまうのでダメ
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)
    


if __name__ == "__main__":
    main()
print('second' if all(a[i] % 2 == 0 for i in range(N)) else 'first')

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
print("second" if all(i % 2 == 0 for i in a) else "first")
from functools import reduce
import math

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

gcd = []

for i in range(len(A)):
    B = A[i]
    A.pop(i)
    gcd.extend([reduce(math.gcd,A)])
    A.insert(i,B)

print(max(gcd))


### FIXED CODE ###

A,B,T = map(int,input().split())

print(T//A * B)
import math
N = int(inport())

print(factrial(N)%(10**9+7))

### FIXED CODE ###

import math
N = int(input())
 
print(math.factorial(N)%(10**9+7))
a,b=int(split(input()))
x=a:b
y=2*a+2*b
print(x,y)

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
print(a*b,2*a+2*b)
from bisect import bisect_left
N = int(input())
L = list(map(int, input().split())).sort()
res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx
print(res)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
res = 0
for i in range(N):
    for j in range(i+1, N):
        idx = bisect_left(L, L[i]+L[j])
        res += max(0,idx-(j+1))
print(res)
N, M = map(int, input().split())
A = list(map(int, input().split()))
b = []
for i in range(M):
    b.append(list(map(int, input().split())))
ans = 0
A.sort()
b.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(len(b)):
    while A[j] < b[i][1] and b[i][0]:
        A.pop(0)
        ans += b[i][1]
        b[i][0] -= 1
print(ans + sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
b = []
for i in range(M):
    b.append(list(map(int, input().split())))
ans = 0
A.sort()
b.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(M):
    if j >= N or b[i][1] <= A[j]:
        break
    while j < N and b[i][0] and b[i][1] > A[j]:
        ans += b[i][1]
        b[i][0] -= 1
        j += 1
if j >= N:
    print(ans)
else:
    print(ans + sum(A[j:]))
from collections import deque

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
colored = [False]*n
# 根を決める
for i in range(n):
    if len(e[i]) == 1:
        s = i
colored[s] = True
ans = k
num = len(e[s])
ans *= fact[k-1] * fact_inv[k-1-num] % MOD
ans %= MOD
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= fact[k-2] * fact_inv[k-2-num] % MOD
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 25 08:44:21 2020

@author: teppe
"""

from collections import deque

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

MOD = 10**9+7
fact, fact_inv = prepare(10+10**5, MOD)

def perm(n,k):
  if k > n or k < 0:
    return 0
  return fact[n] * fact_inv[n-k] % MOD


n, k = map(int,input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
 
colored = [False]*n
colored[0] = True
num = len(e[0])
ans = perm(k, 1+num)
d = deque()
for i in e[0]:
    colored[i] = True
    d.append(i)
while d:
    f = d.pop()
    num = len(e[f]) - 1
    if num == 0:
        continue
    ans *= perm(k-2, num)
    ans %= MOD
    for i in e[f]:
        if not colored[i]:
            colored[i] = True
            d.appendleft(i)
print(ans % MOD)
n = int(input())
ns = list(map(int, input().split()))

print(min(ns), max(ns), sum(ns)


### FIXED CODE ###

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

print(min(ns), max(ns), sum(ns))