Harryxun/stf_run huggingface dataset:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        par[nowNode] = parentNode
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    order = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        order[(min(a-1, b-1), max(a-1, b-1))] = i
    K = 0
    for i in range(N): K = max(K, len(edge[i]))
    
    q = deque()
    col = [-1] * N
    col[0] = 0
    colE = [-1] * (N - 1)
    colPointer = 1
    for next in edge[0]: 
        q.append((0, next))
        col[next] = colPointer
        colE[order[(0, next)]] = colPointer
        colPointer += 1
    while q:
        parentNode, nowNode = q.popleft()
        colPointer = 1
        for nextNode in edge[nowNode]:
            if nextNode != parentNode:
                q.append((nowNode, nextNode))
                if colPointer == col[nowNode]: colPointer += 1
                col[nextNode] = colPointer
                colE[order[(min(nowNode, nextNode), max(nowNode, nextNode))]] = colPointer
                colPointer += 1

    print(K)
    for c in colE: print(c)

    return 0

if __name__ == "__main__":
    solve()
k = list(map(int, input().split()))
h = list(map(int, input().split()))
m = [list(map(int, input().split())) for i in range(k[1])]

import networkx as nx

G = nx.Graph()
for i in range(len(k)):
  G.add_node(i +1)
for i in m:
  G.add_edge(i[0],i[1])

#print(k[0] - len(G.nodes()))
re = 0

for i in list(G.nodes):
  max_height = max([h[x - 1] for x in list(nx.all_neighbors(G, i))])
  if h[i-1] > max_height:
    re +=1
print(re + k[0] - len(G.nodes()))

### FIXED CODE ###

k = list(map(int, input().split()))
h = list(map(int, input().split()))
m = [list(map(int, input().split())) for i in range(k[1])]

import networkx as nx
G = nx.Graph()
for i in range(k[0]):
  G.add_node(i +1)
for i in m:
  G.add_edge(i[0],i[1])
re = 0
for i in list(G.nodes):
  if len(list(nx.all_neighbors(G, i))) != 0:
    max_height = max([h[x - 1] for x in list(nx.all_neighbors(G, i))])
    if h[i-1] > max_height:
      re +=1
  else:
    re +=1
print(re)
n = int(input())
ans = 0
cnt = 0

for i in range(1,n+1):
  for j in range(1,n+1):
    if i%j = 0:
      ans += 1
  if ans = 8:
    cnt += 1

print(cnt)
      


### FIXED CODE ###

N=int(input())

result=0
for i in range(1,N+1):
    if i%2!=0:
        divisor=0
        for j in range(1,i+1):
            if i%j==0:
                divisor+=1
        if divisor==8:
            result+=1
print(result)
s=input()
if s=='AAA' or s=='BBB':
  print ('No')
else ('Yes')  


### FIXED CODE ###

s=input()
if s=='AAA' or s=='BBB':
  print ('No')
else:
  print('Yes')
a=list(map,input().split())
k=int(input())
while a[0]>=a[1]:
  k--
  a[1]*=2
while a[1]>=a[2]:
  k--
  a[2]*=2
if k>=0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a=list(map(int,input().split()))
k=int(input())
while a[0]>=a[1]:
  k-=1
  a[1]*=2
while a[1]>=a[2]:
  k-=1
  a[2]*=2
if k>=0:
  print("Yes")
else:
  print("No")
a,b = map(int,input().split)
if a//2==0 or b//2==0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b=map(int,input().split())
if a%2==0 or b%2==0:
  print("Even")
else:
  print("Odd")
N = int(input())
list = list(map(int, input().split()))
ans = 1

dict = {}
for i in range(N):
    if list[i] in dict.keys():
        dict[list[i]] += 1
    else:
        dict.setdefault(list[i], 1)

max = max(dict)

try:
    for i in range(1,max+1):
        ans = (ans * (dict[i-1] ** dict[i])) % 998244353
except KeyError:
    ans = 0

if dict[0] != 1:
    ans = 0

print(ans)


### FIXED CODE ###

N = int(input())
list = list(map(int, input().split()))
ans = 1

dict = {}
for i in range(N):
    if list[i] in dict.keys():
        dict[list[i]] += 1
    else:
        dict.setdefault(list[i], 1)

max = max(dict)

try:
    for i in range(1,max+1):
        ans = (ans * (dict[i-1] ** dict[i])) % 998244353
    if dict[0] != 1:
        ans = 0
    if list[0] != 0:
        ans = 0
except KeyError:
    ans = 0

print(ans)
m,n,*aa = open(0).read().split()
ans = m-sum(aa)
if ans<0:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

m,n,*aa = map(int, open(0).read().split())
ans = m-sum(aa)
if ans<0:
  print(-1)
else:
  print(ans)
import sys
input = sys.stdin.readline

def ceil(a, b):
    if a%b == 0:
        return a//b
    else:
        return a//b + 1

def main():
    D, G = map(int, input().split())
    pc = [list(map(int, input().split())) for i in range(D)]

    ans = int(1e9)
    for i in range(2**D):
        tmp = 0
        rest = []
        count = 0
        for j in range(D):
            if i&1:# コンプリートする問題
                tmp += (j+1)*100 * pc[j][0] + pc[j][1]
                count += pc[j][0]
            else:
                rest.append(((j+1)*100, pc[j][0]))
            i >>= 1
        rest = sorted(rest, reverse=True)
        rest_point = G - tmp
        if rest_point < 0:
            continue
        tmp = ceil(rest_point, rest[0][0])
        if tmp <= rest[0][1]:
            ans = min(ans, count + tmp)
            # print(rest_point, count, tmp)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def ceil(a, b):
    if a%b == 0:
        return a//b
    else:
        return a//b + 1

def main():
    D, G = map(int, input().split())
    G //= 100
    pc = [list(map(int, input().split())) for i in range(D)]

    ans = int(1e9)
    for i in range(2**D):
        tmp = 0
        rest = []
        count = 0
        for j in range(D):
            if i&1:# コンプリートする問題
                tmp += (j+1) * pc[j][0] + pc[j][1]//100
                count += pc[j][0]
            else:
                rest.append((j+1, pc[j][0]))
            i >>= 1
        rest = sorted(rest, reverse=True)
        rest_point = G - tmp
        if rest_point <= 0:# すでに足りている
            ans = min(ans, count)
        elif len(rest) > 0:# 不足分を補う必要がある
            plus = ceil(rest_point, rest[0][0])
            if plus < rest[0][1]:# p-1問以内ですむ
                ans = min(ans, count + plus)
        else:# すべて使っても足りない
            pass
    print(ans)

if __name__ == "__main__":
    main()
*a, = map(int, input().split())
a = [bin(abs(a[i+1]-a[i]))[::-1].find('1') for i in range(2)].sort()
print(a[1] if a[0]*a[1]<0 else a[0])

### FIXED CODE ###

# my solution
*a, = map(int,input().split())
if any(map(lambda x: bin(x)[-1]== "1", a)):
    print("0")
    exit()
a = [bin(abs(a[i+1]-a[i]))[::-1].find('1') for i in range(2)]
print(max(a) if a[0]*a[1]<0 else min(a))
import math
n=int(input())
ans=0
if n%2==1:
    print(ans)
else:
    m=math.ceil(math.log(n, 5))
    for i in range(1, m):
        ans +=(n//2)//(5**i)
    print(ans)

### FIXED CODE ###

import math
n=int(input())
ans=0
if n==0 or n%2==1:
    print(ans)
else:
    m=math.ceil(math.log(n, 5))
    for i in range(1, m):
        ans +=(n//2)//(5**i)
    print(ans)
n=int(input())
print((a)+(a*a)+(a**3))

### FIXED CODE ###

a=int(input())
print((a)+(a*a)+(a**3))
n=int(input())
a=list(map(int,input().split()))

nn=1000//100*2**(n//2+1)
dp=[[0]*nn for i in range(n)]

ni=1000//a[0]
for i in range(ni+1):    
    dp[0][i]=1000-a[0]*i

for k in range(1,n):
    for i in range(nn):
        xmax=0
        for ii in range(nn):
            x=dp[k-1][ii]+(ii-i)*a[k]
            if x<0:continue
            if dp[k-1][i]//a[k-1]<ii:break
            xmax=max(xmax,x) 
        dp[k][i]=xmax

print(dp[n-1][0])


### FIXED CODE ###

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

dp=[[0]*2 for i in range(n)]
dk=[[0]*2 for i in range(n)]

#--------------- kabu=0
dp[0][0]=1000
dk[0][0]=0
#--------------- all kabu
dp[0][1]=1000%a[0]
dk[0][1]=1000//a[0]

for k in range(1,n):
    dp[k][0]=max(dp[k-1][0],dp[k-1][1]+dk[k-1][1]*a[k])
    dk[k][0]=0

    dpk1=dp[k-1][0]%a[k]
    dkk1=dp[k-1][0]//a[k]
    v1=dk[k-1][1]*a[k]+dp[k-1][1]
    v2=dkk1*a[k]+dpk1
#    if dkk1>dk[k-1][1]:
    if v2>v1:
        dk[k][1]=dkk1
        dp[k][1]=dpk1
    else:
        dp[k][1]=dp[k-1][1]
        dk[k][1]=dk[k-1][1]

print(dp[n-1][0])
n, k = map(int, input().split())
h = list(int(input()).split())
tmp = 0

for i in range(n):

    if h[i] >= k:
        tmp += 1

print(tmp)

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
tmp = 0

for i in range(n):

    if h[i] >= k:
        tmp += 1

print(tmp)
a,b=map(int, input().split())
if a = 1 or b = 1:
  print(1)
else:
print(-(-1 * a * b // 2))

### FIXED CODE ###

a,b=map(int, input().split())
if a == 1 or b == 1:
	print(1)
else:
	print(-(-1 * a * b // 2))
red blue
3 4
red


### FIXED CODE ###

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

ans = a-(s == u)

print("{} {}\n".format(a-(s == u), b-(t == u)))
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if(V <= W):
	print("NO")
elif(abs(B - A) >= V * T):
	print("NO")
elif((B - A) % 2 == 1) and ((W - V) % 2 =! 1):
	print("NO")
else:
	print("YES")

### FIXED CODE ###

S= input()
print(S[:3])
import sys
import numpy as np

n, k = map(int, input().split())
a = list(map(int, input().split()))
cs_a = list(np.cumsum(a)) #累積和

dp = [[0] * (n + 1) for i in range(k + 1)]

for i in range(k + 1):
    for j in range(1, n + 1):
        if i > cs_a[j - 1]:
            dp[i][j] = 0
        elif i == 0:
            dp[i][j] = 1
        elif i == 1:
            dp[i][j] = dp[i][j - 1] + min(1, a[j - 1])
        else:
            dp[i][j] = sum(dp[i - x][j - 1] for x in range(a[j - 1] + 1))
            
print(dp[k][n] % (10 ** 9 + 7))



### FIXED CODE ###

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

cs_a, cnt = [0] * n, 0
for i in range(n):
    cnt += a[i]
    cs_a[i] = cnt
dp = [[0] * (k + 1) for i in range(n + 1)]

for i in range(n + 1):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        elif (i == 0) or (j > cs_a[i - 1]):
            dp[i][j] = 0
        elif j == 1:
            dp[i][j] = dp[i - 1][j] + min(a[i - 1], 1)
        elif j - a[i - 1] - 1 < 0:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - a[i - 1] - 1]
        dp[i][j] %= 10 ** 9 + 7

print(dp[n][k])
T = list(str(input()))

for i in range(len(T)):
    if T[i] == '?' and T[i - 1] == 'P':
        T[i] = 'D'
    elif T[i] == '?' and T[i + 1] == 'D':
        T[i] = 'P'
    elif T[i] == '?' and T[i + 1] == '?':
        T[i] = 'P'
        T[i + 1] = 'D'
        i += 1
    elif T[i] == '?':
        T[i] = 'D'        

TL=''.join(T)
print(TL)


### FIXED CODE ###

T = list(str(input()))

for i in range(len(T)):
    if T[i] == '?':
        T[i] = 'D'
    print(T[i],end='')
#!/usr/bin/env python
# -*- coding:utf-8 -*-

#import sys # モジュール属性 argv を取得するため
 
argvs = sys.argv  # コマンドライン引数を格納したリストの取得
argc = len(argvs) # 引数の個数
# デバッグプリント
print argvs
print argc

### FIXED CODE ###

# -*- coding: utf-8 -*-
# get a integer
num = int(raw_input())
# get two integers separated with half-width break
array = map(int, raw_input().split())
# get a string
#s = raw_input()

state = 0
way_total = 0
for j in range(0,num):
    way_total += abs(array[j] - state)
    state = array[j]
way_total += abs(state)

for i in range(0,num):
    if i != num - 1 and i != 0:
        way = way_total - abs(array[i-1] - array[i]) - abs(array[i+1] - array[i]) + abs(array[i-1] - array[i+1])
    elif i == 0:
        way = way_total - abs(array[i])- abs(array[i+1] - array[i]) + abs(array[i+1])
    elif i == num - 1:
        way = way_total - abs(array[i-1] - array[i]) - abs(array[i]) + abs(array[i-1] - 0)
    print(way)
h, w = map(int, input().split())
cells = []
cells.append(['.']*(w+2))
for i in range(h):
    l = ['.']
    s = input().split()
    l+=list(s[0])
    l+=['.']
    cells.append(l)
cells.append(['.']*(w+2))

ans = True
for i in range(1,len(cells)-1):
    for j in range(1,len(cells)-1):
        if cells[i][j] == '#':
            if cells[i-1][j] != '#' and cells[i+1][j] != '#' and cells[i][j-1] != '#' and cells[i][j+1] != '#':
                ans = False

if ans: print("Yes")
else: print("No")

### FIXED CODE ###

h, w = map(int, input().split())
cells = []
for i in range(h):
    s = input().split()
    cells.append(s[0])
ans = True
for i in range(1,h-1):
    for j in range(1,w-1):
        if cells[i][j] == '#':
            if cells[i-1][j] != '#' and cells[i+1][j] != '#' and cells[i][j-1] != '#' and cells[i][j+1] != '#':
                ans = False
                break
 
if ans: print("Yes")
else: print("No")
S = raw_input()
T = "CODEFESTIVAL2016"
ans = 0
for i in xrange(S):
    if S[i] != T[i]: ans += 1
print ans

### FIXED CODE ###

S = raw_input()
T = "CODEFESTIVAL2016"
ans = 0
for i in xrange(len(S)):
    if S[i] != T[i]: ans += 1
print ans
N,M = map(int, input().split())
ans = 0
while not (N == 0 and M == 0):
 for i in range(N):
  for j in range(N):
   for k in range(N):
    if ( i==j or i==k or j==k):
    elif(i + j + k == M): ans += 1
print(ans)

### FIXED CODE ###

N,M = map(int, input().split())
ans = 0
while not (N == 0 and M == 0):
 for i in range(1, N+1):
  for j in range(i+1, N+1):
   k = M - i - j
   if ( k > N): pass
   elif  k <= j : break
   else: ans += 1
 print(ans)
 ans = 0
 N,M = map(int, input().split())
s = input()
print('{}{}{}'.format(s[0], len(s)-2, s[-1])

### FIXED CODE ###

s = input()
print('{}{}{}'.format(s[0], len(s)-2, s[-1]))
n,x,t=map(int,input().split())

if n%x=0:
   a=n//x
else:
   a=n//x+1

b=a*t

print(b)


### FIXED CODE ###

n,x,t=map(int,input().split())

if n%x==0:
   a=int(n//x)
else:
   a=int(n//x+1)

b=int(a*t)

print(b)
s=input()
k=int(input())
d = dict()
for i in range(len(alphabet)):
    d[alphabet[i]]=i
    
def f(s,k):
    s = [s[i] for i in range(len(s))]
    res = s
    L = 0
    for i in range(len(s)):
        l = max(26 - d[s[i]],0)
        if L + l < k:
            res[i] = "a"
            L += l
        else:
            if i==len(s)-1:
                res[i] = alphabet[(d[s[i]] + (k-L)) % 26]
            continue
    return(''.join(res))
print(f(s,k))

### FIXED CODE ###

s=input()
k=int(input())
d = dict()
alphabet = "abcdefghijklmnopqrstuvwxyz"
for i in range(len(alphabet)):
    d[alphabet[i]]=i
    
def f(s,k):
    s = [s[i] for i in range(len(s))]
    res = s
    L = 0
    for i in range(len(s)):
        l = max((26 - d[s[i]]) % 26, 0)
        if i==len(s)-1:
            res[i] = alphabet[(d[s[i]] + (k-L)) % 26]
        else:
            if L + l <= k:
                res[i] = "a"
                L += l
            else:
                continue
    return(''.join(res))
print(f(s,k))
from sys import stdin
N = int(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())
X = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 0
for i in x:
    if i < K - i:
        ans += 2 * i
    else:
        ans += 2 * (K - i)
print(ans)

### FIXED CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())
X = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 0
for i in X:
    if i < K - i:
        ans += 2 * i
    else:
        ans += 2 * (K - i)
print(ans)
for i in range(len(S)-lenT+1):
  compareS = S[i:i+lenT]
  match_len = 0
  for j in range(lenT):
    if compareS[j] == T[j]:
      match_len += 1
  else:
    if max_match_len < match_len:
      max_match_len = match_len
print(lenT - max_match_len)


### FIXED CODE ###

S, T = [input() for x in range(2)]
max_match_len = 0

for i in range(len(S)):
  if len(S) - len(T) < i:
    break
  compare_s = S[i:i+len(T)]
  match_len = 0
  for j in range(len(T)):
    if compare_s[j] == T[j]:
      match_len += 1
  else:
    if max_match_len < match_len:
      max_match_len = match_len
print(len(T) - max_match_len)
a,b= int(input())
c= a*b
print(c)

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b)
N,M = map(int,input().split())
a = list(int(input())for i in range(M))
mod = 10**9+7
b = [0] * (n-1)
b[0] = 1
b[1] = 1
for i in a:
    b[i] = -1

for i in range(2,n+1):
    if b[i] == -1:
        continue
    if b[i-1] != -1:
        b[i] += b[i-1]
    if b[i-2] != -1:
        b[i] += b[i-2]

print(b[-1]%mod)

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
b=[0]*(n+1)
b[0]=1
b[1]=1

for i in a:
    b[i]=-1

for i in range(2,n+1):
    if b[i]==-1:
        continue
    if b[i-1]!=-1:
        b[i]+=b[i-1]
    if b[i-2]!=-1:
        b[i]+=b[i-2]
        
print(b[-1]%mod)
#coding:utf-8

N = input()

p = []
max_val = -1
for i in range(N):
    p_i = input()
    p.append(p_i)
    max_val = max(max_val, p_i)

sum = 0
flag = 0
for p_i in p:
    if p_i == max_val and flag==0:
        sum += p_i * 0.5
        flag = 1
    else:
        sum += p_i
print(int(sum))
        


### FIXED CODE ###

#coding:utf-8

N = int(input())
p = []
max_val = -1
for i in range(N):
    p_i = int(input())
    p.append(p_i)
    max_val = max(max_val, p_i)

s = 0
flag = 0
for p_i in p:
    if p_i == max_val and flag==0:
        s += p_i * 0.5
        flag = 1
    else:
        s += p_i
print(int(s))
n=int(input())
x=input()
memo={}
import sys
sys.setrecursionlimit(10**7)

def func(m,i):
  if m in memo:
    return memo[m]
  elif m%i==0:
    memo[m]=1
    return 1
  else:
    ret=0
    mm=m%i
    ii=bin(mm).count('1')
    ret+=func(mm,ii)+1
    memo[m]=ret
    return ret

c=x.count('1')
xx=0
for i in range(n):
  xx+=pow(2,i)*int(x[-1-i])
for i in range(n):
  if x[i]=='0':
    xxx=xx+pow(2,n-1-i)
    cc=c+1
  else:
    xxx=xx-pow(2,n-1-i)
    cc=c-1
  print(func(xxx,cc))
#print(memo)


### FIXED CODE ###

n=int(input())
x=input()
import sys
sys.setrecursionlimit(10**7)
if n==1:
  print(0 if x=='1' else 1)
  exit()
def pc(x):
  a=bin(x)[2:]
  return a.count('1')
def func(x):
  if x==0:
    return 0
  else:
    return func(x%pc(x))+1
pcx=x.count('1')
if pcx==0:
  for _ in range(n):
    print(1)
else:
  x0,x1=0,0
  for i in range(n):
    if x[i]=='1':
      if pcx!=1:
        x0+=pow(2,n-1-i,pcx-1)
        x0%=pcx-1
      x1+=pow(2,n-1-i,pcx+1)
      x1%=pcx+1
  for i in range(n):
    ans=0
    if x[i]=='1':
      if pcx==1:
        print(0)
      else:
        xx=x0-pow(2,n-1-i,pcx-1)
        xx%=pcx-1
        print(func(xx)+1)
    else:
      xx=x1+pow(2,n-1-i,pcx+1)
      xx%=pcx+1
      print(func(xx)+1)
a, b, c = map(int, input().splis())
dai = max(a,b,c)
shou = min(a,b,c)
mid = a + b + c - dai - shou

print(shou * mid / 2)

### FIXED CODE ###

a, b, c = map(int, input().split())
dai = max(a,b,c)
shou = min(a,b,c)
mid = a + b + c - dai - shou

print(shou * mid // 2)
print(eval(open(0).read().replace(' ','**2-')))

### FIXED CODE ###

print(eval(input()+'**2-'+input()))
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    table = [True for _ in range(n)]
    perm = [1]
    for i in range(k - 2, -1, -1):
        perm.append(perm[-1] * i % MOD)

    table[0] = False
    que = collections.deque(e[0])
    ans = k
    for i in range(len(e[0])):
        table[e[0][i]] = False
        ans *= k - i - 1
        ans %= MOD

    while len(que) > 0:
        for _ in range(len(que)):
            q = que.popleft()
            cnt = 0
            for i in range(len(e[q])):
                tmp = e[q][i]
                if table[tmp]:
                    table[tmp] = False
                    cnt += 1
                    que.appendleft(tmp)
            ans *= perm[cnt]
            ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    table = [True for _ in range(n)]
    perm = [1]
    for i in range(k - 2, -1, -1):
        perm.append(perm[-1] * i % MOD)

    table[0] = False
    que = collections.deque(e[0])
    ans = k
    for i in range(len(e[0])):
        table[e[0][i]] = False
        ans *= k - i - 1
        ans %= MOD

    while len(que) > 0:
        for _ in range(len(que)):
            q = que.popleft()
            cnt = 0
            for i in range(len(e[q])):
                tmp = e[q][i]
                if table[tmp]:
                    table[tmp] = False
                    cnt += 1
                    que.appendleft(tmp)
            ans *= perm[min(len(perm) - 1, cnt)]
            ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
s = input()

h = s/3600
m = s%3600/60
s = s%3600%60

print h + ":" + m + ":" + s

### FIXED CODE ###

s = input()

h = s/3600
m = s%3600/60
s = s%3600%60

print '{0}:{1}:{2}'.format(h, m, s)