Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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]*(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])
  for i in range(1,N+1):
    if len(G[i])==1:break
  first = i
  #first = deg2[1][0]
  second = G[first][0]
  color = [1]*(N+1)
  color[first],color[second]=K,K-1

  def bfs(s):
      todo = deque([])
      todo.append(s)
      while 1:
        if len(todo)==0:break
        a = todo.popleft()
        if a != first: 
          acolor=K-1
        for b in G[a]:
          if G[b]==a:continue
          todo.append(b)
          if b != second:
            acolor -= 1
            color[b] = acolor

  bfs(first)
  total=1
  for i in range(1,N+1):
    total *= color[i]
  total %= mod
  print(total)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from math import prod

N,K=map(int,input().split())
if N==1:print(K)
else:
  G=[[] for i in range(N+1)]
  #deg=[0]*(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])
  for i in range(1,N+1):
    if len(G[i])==1:break
  first = i
  #first = deg2[1][0]
  second = G[first][0]
  color = [1]*(N+1)
  color[first],color[second]=K,K-1

  def bfs(s):
      seen = [0]*(N+1)
      todo = deque([])
      seen[s]=1
      todo.append(s)
      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)
  total = prod(color)%mod
  print(total)

Fixed submission:
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)

Buggy python submission (verdict: Runtime Error):
from collections import deque
from math import prod

N,K=map(int,input().split())
if N==1:print(K)
else:
  G=[[] for i in range(N+1)]
  #deg=[0]*(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])
  for i in range(1,N+1):
    if len(G[i])==1:break
  first = i
  #first = deg2[1][0]
  second = G[first][0]
  color = [1]*(N+1)
  color[first],color[second]=K,K-1

  def bfs(s):
      seen = [0]*(N+1)
      todo = deque([])
      seen[s]=1
      todo.append(s)
      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)
  total = prod(color)%mod
  print(total)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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]*(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])
  for i in range(1,N+1):
    if len(G[i])==1:break
  first = i
  #first = deg2[1][0]
  second = G[first][0]
  color = [1]*(N+1)
  color[first],color[second]=K,K-1

  def bfs(s):
      seen = [0]*(N+1)
      todo = deque([])
      seen[s]=1
      todo.append(s)
      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)
  total=1
  for i in range(1,N+1):
    total *= color[i]
  total %= mod
  print(total)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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

  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)
  total=1
  for i in range(1,N+1):
    total *= color[i]
  total %= mod
  print(total)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
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 = list(enumerate(deg))
  deg2 = sorted(deg2,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

  def bfs(s):
      seen = [0 for i in range(N+1)]
      prev = [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)
            prev[b] = a
            if b != second:
              acolor -= 1
              color[b] = acolor
      return prev

  prev = bfs(first)
  total=1
  for i in range(1,N+1):
    total *= color[i] % mod
  total %= mod
  print(total)

Fixed submission:
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)