Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

INF = 10**18
N, M = map(int, input().split())
g = [[] for _ in range(N)]
lst = [INF] * N

def dfs(v):
    for n, d in g[v]:
        if lst[n] == INF:
            lst[n] = lst[v] + d
            if not dfs(n):
                return False
        else:
            if lst[n] != lst[v] + d:
                return False
    return True

for i in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))

for i in range(N):
    if lst[i] == INF:
        lst[i] = 0
        if not dfs(i):
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

INF = 10**18
N, M = map(int, input().split())
g = [[] for _ in range(N)]
lst = [INF] * N

def dfs(v):
    for n, d in g[v]:
        if lst[n] == INF:
            lst[n] = lst[v] + d
            if not dfs(n):
                return False
        else:
            if lst[n] != lst[v] + d:
                return False
    return True

for i in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))

for i in range(N):
    if lst[i] == INF:
        lst[i] = 0
        if not dfs(i):
            print('No')
            exit()

print('Yes')
### BUGGY CODE ###

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

ans=0
for a in set(A):
  if A.count(a)==a:
    continue
  elif A.count(a)<a:
    ans+=A.count(a)
  else:
    cnt=0
    while True:
      if A.count(a)==a or A.count(a)==0:
        break
      else:
        A.remove(a)
        cnt+=1
    ans+=cnt
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))

c=Counter(A)
ans=0
for key, value in c.items():
  if key!=value:
    if key>value:
      ans+=value
    else:
      ans+=value-key
print(ans)
### BUGGY CODE ###

S = list(input())
k = int(input())
S_sorted = "".join(sorted(list(set(S))))
#print(S_sorted[:5])
Ans = []
counter = 0
for counter in range(0, 10000000):
  Ans_temp = []
  moji = S_sorted[counter]
  Index = [i for i, chr in enumerate(S) if moji == chr]
  for index in Index:
    for j in range(0, len(S) + 1):
      if len(S[index : index+j]) != 0:
        Ans_temp.append("".join(S[index : index+j]))
#  print(Ans_temp)
  Ans = Ans + sorted(list(set(Ans_temp)))
  if len(Ans) >= k:
    break
print(Ans[k-1])

### FIXED CODE ###

S = list(input())
k = int(input())
S_sorted = "".join(sorted(list(set(S))))
#print(S_sorted[:5])
Ans = []
counter = 0
for counter in range(0, 10000000):
  Ans_temp = []
  moji = S_sorted[counter]
  Index = [i for i, chr in enumerate(S) if moji == chr]
  for j in range(0, k + 1):
    for index in Index:
      if len(S[index : index+j]) != 0:
        Ans_temp.append("".join(S[index : index+j]))
#  print(Ans_temp)
  Ans = Ans + sorted(list(set(Ans_temp)))
  if len(Ans) >= k:
    break
print(Ans[k-1])
### BUGGY CODE ###

import numpy as np
N, K = map(int,input().split())
A = np.sort(list(map(int,input().split())))
F = np.sort(list(map(int,input().split())))[::-1]
mul = A*F
if K >= sum(A)*N:
    print(0)
    exit()

ma = 2**40
mi = 0
while 1:
    tgt = (ma + mi)//2
    num = 0
    for m,f in zip(mul,F):
        tmp = np.ceil((m-tgt)/f)
        if tmp < 0:
            continue
        num += tmp
    if ma == mi:
        print(ma)
        exit()
    if num <= K:
        ma = mi + (ma - mi)//2
    else:
        mi = mi + (ma - mi)//2+1


### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A = sorted(A)
F = sorted(F, reverse=True)
mul = [A[i]*F[i] for i in range(N)]

if K >= sum(A):
    print(0)
    exit()

ma = 2**40
mi = 0
while 1:
    tgt = mi + (ma - mi)//2
    num = 0
    for i in range(N):
        tmp = (mul[i] - tgt + F[i] - 1) // F[i]
        if tmp <= 0:
            continue
        num += tmp
    if ma == mi:
        print(ma)
        exit()
    if num <= K:
        ma = mi + (ma - mi)//2
    else:
        mi = mi + (ma - mi)//2+1
### BUGGY CODE ###

NKQ= input().split(" ")
N = int(NKQ[0])
K = int(NKQ[1])
Q = int(NKQ[2])
LIST = []

for i in range(0, N):
    LIST.append(K)

for i in range(0, Q):
    offset = int(input()) - 1
    for o in range(0, N):
        if o != offset:
            LIST[o] -= 1
        else:
            pass
        
for i in LIST:
    if i >= 1:
        print("Yes")
    else:
        print("No")
    

### FIXED CODE ###

NKQ= input().split(" ")
N = int(NKQ[0])
K = int(NKQ[1])
Q = int(NKQ[2])
LIST = []

for i in range(0, N):
    LIST.append(K)

for i in range(0, Q):
    offset = int(input()) - 1
    LIST[offset] += 1
        
for i in LIST:
    if i - Q >= 1:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
sl = []
ans = 0
for i in  range (n):
  s = input()
  if s not in sl:
    sl.append(s)
    ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
sl = set()
for i in  range (n):
  s = input()
  sl.add(s)
print(len(sl))
### BUGGY CODE ###

n=int(input())
H=[int(i) for i in input().split()]
for i in range(n):
    if i!=0:
        H=H[:-1]
    if max(H)-H[-1]>1:
        print("No")
        exit(0)
print("Yes")

### FIXED CODE ###

n=int(input())
H=[int(i) for i in input().split()]
for i in range(n-1,0,-1):
    if H[i]<H[i-1]:
        H[i-1]-=1
        if H[i]<H[i-1]:
            print("No")
            exit()
print("Yes")
### BUGGY CODE ###

N, M = map(int, input().split())
adjL = [set() for _ in range(N)]
outdegs = [0] * N
edges = []
for _ in range(M):
    s, t = map(int, input().split())
    s, t = s-1, t-1
    adjL[s].add(t)
    outdegs[s] += 1
    edges.append((s, t))

def func():
    ps = [0] * N
    ps[0] = 1
    ns = [0] * N
    es = [0] * N
    for v in range(N-1):
        p, e = ps[v], es[v]
        outdeg = outdegs[v]
        if p != 0:
            n = ns[v] = e / p
            if len(adjL[v]) == 0:
                return N

        for v2 in adjL[v]:
            ps[v2] += p / outdeg
            es[v2] += p * (n+1) / outdeg

    if ps[-1] != 0:
        return es[-1] / ps[-1]
    else:
        return N

ans = func()
for vFr, vTo in edges:
    adjL[vFr].remove(vTo)
    outdegs[vFr] -= 1

    num = func()

    adjL[vFr].add(vTo)
    outdegs[vFr] += 1

    ans = min(ans, num)

print(ans)


### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    outdegs = [0] * N
    for _ in range(M):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        adjL[s].append(t)
        outdegs[s] += 1

    dp = [0] * N
    for v in reversed(range(N-1)):
        dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1

    ans = dp[0]
    for vRem in range(N-1):
        if outdegs[vRem] == 1: continue
        sumDP, maxDP = 0, -1
        for v2 in adjL[vRem]:
            sumDP += dp[v2]
            if dp[v2] > maxDP:
                maxDP = dp[v2]
        dp[vRem] = (sumDP-maxDP) / (outdegs[vRem]-1) + 1
        for v in reversed(range(vRem)):
            dp[v] = sum([dp[v2] for v2 in adjL[v]]) / outdegs[v] + 1
        ans = min(ans, dp[0])

    print(ans)


solve()
### BUGGY CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort()
c = []

for i in range(M):
    if ab[i][0] == 1:
        c.append(ab[i][1])
    if ab[i][0] in c:
        if ab[i][1] == N:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
A = set()
B = set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
p = [((i-1)%n, (i-1)//n) for i in p]
ans = 0
dp = [[min(i, j, n - (i + 1), n - (j + 1)) for j in range(n)] for i in range(n)]
dp2 = [[False]*n for _ in range(n)]
for (q, r) in p:
    ans += dp[r][q]
    dp2[r][q] = True
    h = [(dp[r][q], r, q)]
    while h:
        d, y, x = heappop(h)
        if not dp2[y][x]:
            d += 1
        if x != 0:
            if dp[y][x-1] > d:
                dp[y][x-1] = d
                heappush(h, (d, y, x-1))
        if x != n-1:
            if dp[y][x+1] > d:
                dp[y][x+1] = d
                heappush(h, (d, y, x+1))
        if y != 0:
            if dp[y-1][x] > d:
                dp[y-1][x] = d
                heappush(h, (d, y-1, x))
        if y != n-1:
            if dp[y+1][x] > d:
                dp[y+1][x] = d
                heappush(h, (d, y+1, x))
print(ans)
    
    

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
p = [((i-1)%n, (i-1)//n) for i in p]
ans = 0
dp = [[min(i, j, n - (i + 1), n - (j + 1)) for j in range(n)] for i in range(n)]
dp2 = [[False]*n for _ in range(n)]
for (q, r) in p:
    ans += dp[r][q]
    dp2[r][q] = True
    h = [(dp[r][q], r, q)]
    while h:
        d, y, x = h.pop()
        if not dp2[y][x]:
            d += 1
        if x != 0:
            if dp[y][x-1] > d:
                dp[y][x-1] = d
                h.append((d, y, x-1))
        if x != n-1:
            if dp[y][x+1] > d:
                dp[y][x+1] = d
                h.append((d, y, x+1))
        if y != 0:
            if dp[y-1][x] > d:
                dp[y-1][x] = d
                h.append((d, y-1, x))
        if y != n-1:
            if dp[y+1][x] > d:
                dp[y+1][x] = d
                h.append((d, y+1, x))
print(ans)
### BUGGY CODE ###

n = int(input())
red_point_list = [[int(j) for j in input().split()] for i in range(n)]
blue_point_list = [[int(j) for j in input().split()] for i in range(n)]

count = 0
memo = []

def func(red_points, blue_points, count):
    
    if len(red_points) == 0:
        memo.append(count)
    else:
        a = red_points[0][0]
        b = red_points[0][1]
        x = 0
        for i, p in enumerate(blue_points):
            if a < p[0] and b < p[1]:
                new_red_points = red_points[1:]
                new_blue_points = blue_points.copy()
                new_blue_points.pop(i)
                new_count = count + 1
                x += 1
                func(new_red_points, new_blue_points, new_count)
        if x == 0:
            new_red_points = red_points[1:]
            new_blue_points = blue_points.copy()
            func(new_red_points, new_blue_points, count)


func(red_point_list, blue_point_list, count)
print(max(memo))


### FIXED CODE ###

n = int(input())
red_point_list = [[int(j) for j in input().split()] for i in range(n)]
blue_point_list = [[int(j) for j in input().split()] for i in range(n)]

count = 0
for c, d in sorted(blue_point_list, key=lambda x: x[0]):
    tmp_index = 0
    tmp_y = -1
    for i, p in enumerate(red_point_list):
        if c > p[0] and d > p[1]:
            if p[1] >= tmp_y:
                tmp_index = i
                tmp_y = p[1]

    if tmp_y > -1:
        count += 1
        red_point_list.pop(tmp_index)

print(count)
### BUGGY CODE ###

def main():
    from itertools import zip_longest
    from bisect import bisect_left
    n, k, *a = map(int, open(0).read().split())
    a.append(k)
    *b, = map(lambda x: bin(x)[2:].zfill(len(bin(max(a))) - 2), a)

    f = False
    m = ''
    for t in zip_longest(*b):
        g = t[-1]
        i = bisect_left(sorted(list(t[:-1])), '1')
        h = '1' if i > n / 2 else '0'
        if (f, g, h) == (False, '1', '0'):
            f = True
        if f:
            m += h
        else:
            m += g

    x = int(m, 2)
    ans = sum(x ^ i for i in a[:-1])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k, *a = map(int, open(0).read().split())

    cnt = [sum((x >> i) & 1 for x in a) for i in range(40)]
    bits = [0 if i > n - i else 1 for i in cnt]

    base = format(k, 'b')
    l = len(base)
    tmp = []

    if sum(2 ** i for i, b in enumerate(bits[:l]) if b == 1) > k:
        for i in range(l - 1, -1, -1):
            if int(base[-i - 1]) < bits[i]:
                bits[i] = 0
                tmp.append(sum(2 ** j for j, b in enumerate(bits[:l]) if b == 1))
    else:
        tmp.append(sum(2 ** j for j, b in enumerate(bits[:l]) if b == 1))

    ans = max(sum(i ^ x for x in a) for i in tmp if i <= k)
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, *a = map(int, open(0).read().split())
b = []
for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b = [a[i]] + b

if n % 2 == 0:       
    print(' '.join(map(str, b)))
else:
    print(' '.join(map(str, b[::-1])))

### FIXED CODE ###

n, *a_l = map(int, open(0).read().split())
b = []

for a in a_l[::-2]:
        b.append(a)
for a in a_l[n%2::2]:
        b.append(a)

print(' '.join(map(str, b)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
a = []

for i in range(1,n+1):
    if n%i == 0:
        a.append(i+n//i-2)

print(min(a))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import sqrt

n = int(input())
a = []

for i in range(1,int(sqrt(n))//1+1):
    if n%i == 0:
        a.append(i+n//i-2)

print(min(a))
### BUGGY CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, M = LI()
A = LI()
BandC = []
for i in range(M):
    BandC.append(LI())

A = sorted(A)
BandC = sorted(BandC, key=lambda x: x[1], reverse=True)

BandC_list = []
for i in BandC:
    BandC_list += [i[1]]*i[0]

ans = 0
for i, a in enumerate(A):
    if i < len(BandC_list):
        ans += max(a, BandC_list[i])
    else:
        ans += a

print(ans)

### FIXED CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    A = LI()
    BandC = []
    for i in range(M):
        BandC.append(LI())
 
    A = sorted(A)
    BandC = sorted(BandC, key=lambda x: x[1], reverse=True)
 
    BandC_counter = 0
    BandC_position = 0
    BandC_sum = 0
    for A_position in range(N):
        if A[A_position] > BandC[BandC_position][1]:
            break
        BandC_sum += BandC[BandC_position][1]
        BandC_counter += 1
        if BandC_counter >= BandC[BandC_position][0]:
            BandC_position += 1
            BandC_counter = 0
            if BandC_position >= len(BandC):
                A_position += 1
                break
    else:
        A_position += 1
 
    print(BandC_sum + sum(A[A_position:]))

main()
### BUGGY CODE ###

import math
K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(i,math.gcd(j,k))
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)

K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=gcd(i,gcd(j,k))
print(ans)
### BUGGY CODE ###

def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

dp = makelist(n+1,n+1,n*a+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*a+1):
            if j*k > 0 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
ans = 0
for k in range(1,n+1):
    ans += dp[n][k][k*a]
print(ans)

### FIXED CODE ###

def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

dp = makelist(n+1,n+1,n*a+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*a+1):
            if j*k > 0 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
ans = 0
for k in range(1,n+1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
ans=[0]*(10**5+1)
for i in a:
  ans[i]+=1
for _ in range(q):
  b,c=map(int,input().split())
  ans[c]+=ans[b]
  ans[b]=0
  s=0
  for i,x in enumerate(ans):
    s+=i*x
  print(s)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
ans=[0]*(10**5+1)
for i in a:
  ans[i]+=1
res=sum(a)
for _ in range(q):
  b,c=map(int,input().split())
  ans[c]+=ans[b]
  res-=ans[b]*b
  res+=ans[b]*c
  ans[b]=0
  print(res)
### BUGGY CODE ###

a=int(input())
c=0
for i in range(a):
  c = c+i
  
print(c)

### FIXED CODE ###

N = int(input())
print((N-1)*N//2)
### BUGGY CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n = int(input())
    As = [int(input()) for i in range(n)]

    for i in range(n):
        print(max(As[:i] + As[i+1:]))

    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def main():
    n = int(input())
    As = [int(input()) for i in range(n)]
    sAs = sorted(As)
    mn1 = sAs[-1]
    mn2 = sAs[-2]
    for i in range(n):
        if As[i] == mn1:
            print(mn2)
        else:
            print(mn1)
    return 

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(raw_input())
S = map(int, raw_input().split())
S = sorted(S)

q = int(raw_input())
T = map(int, raw_input().split())
T = sorted(T)

count = 0
j = 0

for i in range(q):
    while j < n:
        if T[i] == S[j]:
            count += 1
            j += 1
            break
    j += 1

print count

### FIXED CODE ###

n = int(raw_input())
S = map(int, raw_input().split())
S = sorted(S)

q = int(raw_input())
T = map(int, raw_input().split())
T = sorted(T)

count = 0
j = 0

for i in range(q):
    for j in range(n):
        if T[i] == S[j]:
            count += 1
            break

print count
### BUGGY CODE ###

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


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0
aa=sum(a)
for i in range(n):
    aa-=a[i]
    ans += a[i]*aa
ans %= mod
print(ans)
### BUGGY CODE ###

s = input().replace("BC", "X")
cnt = 0
while True:
  pos = s.find("AX")
  if pos == -1:
    break
  s = s[:pos] + "XA" + s[pos + 2:]
  cnt += 1
print(cnt)

### FIXED CODE ###

cnt, tmp = 0, 0
for c in input().replace("BC", "X"):
  if c == "A":
    tmp += 1
  elif c == "X":
    cnt += tmp
  else:
    tmp = 0
print(cnt)
### BUGGY CODE ###

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

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

for d in list_d:
    retn = -1
    for x,s,t in list_xst:
        if ( (s <= d) and (t > d) ):
            retn = x
            break
    print(retn)

### FIXED CODE ###

import bisect

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

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

retn = [-1] * q
jmp = [-1] * q

for x,s,t in list_xst:
    i = bisect.bisect_left(list_d, s)
    tt = bisect.bisect_left(list_d, t)
    while i < tt:
        if (jmp[i] != -1):
            i = jmp[i]
        else:
            retn[i] = x
            jmp[i] = tt
            i += 1

print(*retn, sep="\n")
### BUGGY CODE ###

from collections import deque

N,K=map(int,input().split())
if N==1:print(K)
else:
  G=[[] for i in range(N+1)]
  deg=[0 for i in range(N+1)]
  mod=10**9+7

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

  deg2 = sorted(enumerate(deg),key=lambda x:x[1])
  first = deg2[1][0]
  second = G[first][0]
  color = [1 for i in range(N+1)]
  color[first],color[second]=K,K-1

  total=1
  def calc():
    global total
    for i in range(1,N+1):
      total *= color[i]
    total %= mod

  def bfs(s):
      seen = [0 for i in range(N+1)]
      todo = deque([])
      now = s
      seen[now]=1
      todo.append(now)
      while 1:
        if len(todo)==0:break
        a = todo.popleft()
        if a != first: 
          acolor=K-1
        for b in G[a]:
          if seen[b] == 0:
            seen[b] = 1
            todo.append(b)
            if b != second:
              acolor -= 1
              color[b] = acolor
  bfs(first)
  calc()
  print(total)


### FIXED CODE ###

from collections import deque

N,K=map(int,input().split())
mod = 10**9+7
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

def bfs(s):
    seen = [0]*N
    prev = [0]*N
    color = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    color[s]=K
    while todo:
      a = todo.popleft()
      if a == start: count = K-1
      else: count = K-2
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          color[b] = count %mod
          count -= 1
    return color
  
MAX,start = 0,-1
for i in range(N):
  if len(G[i])>MAX:
    MAX=len(G[i])
    start = i
    
color = bfs(start)
ans = 1
for i in range(N):
  ans *= color[i]
  ans %= mod
  
print(ans)