Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


from collections import defaultdict


def main():
    n, m, k = map(int, input().split())
    fr_ed_c = defaultdict(int)  # node -> count

    parents = {}  # node -> parent_node
    root_2_nc = {}  # node -> count

    for i in range(m):
        a, b = map(int, input().split())
        fr_ed_c[a] += 1
        fr_ed_c[b] += 1

        p_a = get_root(parents, a)
        p_b = get_root(parents, b)

        if p_a == p_b:
            # already same cluster. do nothing.
            pass
        else:
            # cluster integration
            p_a_c = root_2_nc.get(p_a, 1)
            p_b_c = root_2_nc.get(p_b, 1)
            p_a, p_b = (p_a, p_b) if p_a_c < p_b_c else (p_b, p_a)
            parents[p_a] = p_b
            if p_b not in root_2_nc:
                root_2_nc[p_b] = 1
            root_2_nc[p_b] += root_2_nc.pop(p_a, 1)

    br_ed = defaultdict(set)  # node -> set()
    for i in range(k):
        c, d = map(int, input().split())
        br_ed[c].add(d)
        br_ed[d].add(c)

    ans_list = []
    for i_m in range(n):
        i = i_m + 1
        root = get_root(parents, i)
        block_count = 0
        for b in br_ed[i]:
            b_root = get_root(parents, b)
            block_count += 1 if root == b_root else 0
        ans = root_2_nc[root] - 1 - fr_ed_c[i] - block_count
        ans_list.append(str(ans))
    print(" ".join(ans_list))


def get_root(parents, i):
    if i not in parents:
        return i
    return get_root(parents, parents[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


from collections import defaultdict


def main():
    n, m, k = map(int, input().split())
    fr_ed_c = defaultdict(int)  # node -> count

    parents = {}  # node -> parent_node
    root_2_nc = {}  # node -> count

    for i in range(m):
        a, b = map(int, input().split())
        fr_ed_c[a] += 1
        fr_ed_c[b] += 1

        p_a = get_root(parents, a)
        p_b = get_root(parents, b)

        if p_a == p_b:
            # already same cluster. do nothing.
            pass
        else:
            # cluster integration
            p_a_c = root_2_nc.get(p_a, 1)
            p_b_c = root_2_nc.get(p_b, 1)
            p_a, p_b = (p_a, p_b) if p_a_c < p_b_c else (p_b, p_a)
            parents[p_a] = p_b
            if p_b not in root_2_nc:
                root_2_nc[p_b] = 1
            root_2_nc[p_b] += root_2_nc.pop(p_a, 1)

    br_ed = defaultdict(set)  # node -> set()
    for i in range(k):
        c, d = map(int, input().split())
        br_ed[c].add(d)
        br_ed[d].add(c)

    ans_list = []
    for i_m in range(n):
        i = i_m + 1
        root = get_root(parents, i)
        block_count = 0
        for b in br_ed[i]:
            b_root = get_root(parents, b)
            block_count += 1 if root == b_root else 0
        ans = root_2_nc.get(root, 1) - 1 - fr_ed_c.get(i, 0) - block_count
        ans_list.append(str(ans))
    print(" ".join(ans_list))


def get_root(parents, i):
    if i not in parents:
        return i
    return get_root(parents, parents[i])


if __name__ == '__main__':
    main()
a,b,x=map(int,input().split())
import math

if x == a**2*b/2:
  print(math.atan(a/b))
elif x < a**2*b/2:
  print(math.atan(2*x/a/b/b))
else:
  print(math.atan((a*a*b-x)**(-1)*a**3/2)


### FIXED CODE ###

a,b,x=map(int,input().split())
import math
 
if x == a**2*b/2:
  print(float(90)-math.degrees(math.atan(a/b)))
elif x == a*a*b:
  print(0)
elif x < a**2*b/2:
  print(float(90)-math.degrees(math.atan(2*x/a/b/b)))
else:
  print(float(90)-math.degrees(math.atan((a*a*b-x)**(-1)*a**3/2)))
A,B,C,K = map(int,input().split())
result = 0
if K > 0 :
    result = result + A
    K = K - A
for i in range (K):
    if B > 0 :
        B = B-1
    else:
        result = result-1
print(result)

### FIXED CODE ###

S = str(input())
T = str(input())
if T[:-1] == S :
    print("Yes")
else:
    print("No")
import bisect
N = int(input())
An = list(map(int,input().split(' '))) 

bit_list = [1]
for i in range(100000):
    bit_list.append(bit_list[i]*2)
    if bit_list[i+1] > 10**12:
        break
start_point = bisect.bisect_left(bit_list,max(An))
keta_list = [0] * start_point

for A in An:
    abin = format(A, 'b')
    for i in range(len(abin)):
        if abin[i] == '1':
            keta_list[len(abin)-1-i] += 1
count = 0
for idx,keta_count in enumerate(keta_list):
    count += (N-keta_count) * bit_list[idx] * keta_count % (1000000000+7)
print(count)

### FIXED CODE ###

import bisect
N = int(input())
An = list(map(int,input().split(' '))) 

bit_list = [1]
for i in range(100000):
    bit_list.append(bit_list[i]*2)
    if bit_list[i+1] > 2**60:
        break
start_point = bisect.bisect_right(bit_list,max(An))
keta_list = [0] *  start_point

for A in An:
    abin = format(A, 'b')
    for i in range(len(abin)):
        if abin[i] == '1':
            keta_list[len(abin)-1-i] += 1
count = 0
for idx,keta_count in enumerate(keta_list):
    count += (N-keta_count) * bit_list[idx] * keta_count
    count = count % (1000000000+7)
print(count)
N = int(input())
d = [int(input()) for i in range(N)]count = 1
d.sort(reverse=True)
for j in range(N-1):
    if (d[j] != d[j+1]):
        count += 1
print(count)


### FIXED CODE ###

N = int(input())
d = [int(input()) for i in range(N)]
print(len(set(d)))
a,b,c,d,e = map(int,input.split())
print((c*60+d)-(a*60+b)-e)

### FIXED CODE ###

a,b,c,d,e = map(int,input().split())
print((c*60+d)-(a*60+b)-e)
a.b = map(int,input().split)
if a >=13:
  print(b)
else if 6<=a and a<=13:
  print(b//2)
else:
  print(0)

### FIXED CODE ###

a,b = map(int,input().split())
if a >=13:
  print(b)
elif 6<=a and a<=13:
  print(b//2)
else:
  print(0)
N = int(input())
T = [0]*N
for i in range(N):
    T[i] = int(input())

# N < 100
# gcd(a,b) lcd(a,b) = ab

from math import gcd
def lcd(a, b):
    return a*b//gcd(a,b)

l = 1
g = 0
for t in T:
    l = lcd(l, t)
    g = gcd(g, t)
print(l)


### FIXED CODE ###

N = int(input())
T = [0]*N
for i in range(N):
    T[i] = int(input())

# N < 100
# gcd(a,b) lcd(a,b) = ab

from fractions import gcd
def lcd(a, b):
    return a*b//gcd(a,b)

l = 1
g = 0
for t in T:
    l = lcd(l, t)
    g = gcd(g, t)
print(l)
import itertools


def main():
    length = {}
    v = set()
    d = {}

    N, M, R = list(map(int, input().split(' ')))

    r = [int(a) for a in input().split()]

    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        length[(a, b)] = c
        length[(b, a)] = c
        v.add(a)
        v.add(b)
    for a in v:
        length[(a, a)] = 0

    res = float('inf')

    v = list(v)

    for a in v:
        for b in v:
            for c in v:
                length[(b, c)] = min([length[(b, c)], length[(b, a)]+length[(a, c)]])

    # print(length)

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += length[(perm[i], perm[i+1])]
        if a < res:
            # print(perm, a)
            res = a

    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    min_cost = inf
    for p in itertools.permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)


if __name__ == '__main__':
    main()
n=int(input()def givel(): 
     n=int(input()) 
     l=[int(i) for i in input().split()] 
     curr = 0 
     i = 0 
     while i<len(l): 
         temp = i+1 
         ans = 0 
         while temp<len(l) and l[temp]<=l[temp-1]: 
             temp+=1 
             ans+=1 
         i=temp 
         curr = max(curr,ans) 
     return curr

### FIXED CODE ###

def givel(): 
    n=int(input()) 
    l=[int(i) for i in input().split()] 
    curr = 0 
    i = 0 
    while i<len(l): 
        temp = i+1 
        ans = 0 
        while temp<len(l) and l[temp]<=l[temp-1]: 
            temp+=1 
            ans+=1 
        i=temp 
        curr = max(curr,ans) 
    return curr
print(givel())
import math

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//math.gcd(A, D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(t2 - t1)


### FIXED CODE ###

import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))
input = input()
if 0 <= input < 86400:
    hour = input / 3600
    minute = (input / 60) % 60
    second = input % 60
    print("%d:%d:%d" % (hour,minute,second))

### FIXED CODE ###

input = int(input())
if 0 <= input < 86400:
    hour = input / 3600
    minute = (input / 60) % 60
    second = input % 60
    print("%d:%d:%d" % (hour,minute,second))
N=int(input())

for i in reversed(range(1,10)):
    if N%i==0:
        if N/i > 9:
            print('No')
            exit(0)
    print('Yes')
    exit(1)  


### FIXED CODE ###

N=int(input())

for i in reversed(range(1,10)):
    if N%i==0:
        if N/i > 9:
            print('No')
            exit(0)
        else:
            print('Yes')
            exit(0)
# https://atcoder.jp/contests/abc131/tasks/abc131_c


import math


A, B, C, D = map(int, input().split())

C_ = (B // C) - ((A - 1) // C)

D_ = (B // D) - ((A - 1) // D)

# 最大公約数
CD = math.gcd(C, D)

# 最小公倍数
CD = (C * D) / CD

CD_ = (B // CD) - ((A - 1) // CD)

total_num = B - (A - 1)

ans = total_num - C_ - D_ + CD_

print(int(ans))

### FIXED CODE ###

# https://atcoder.jp/contests/abc131/tasks/abc131_c

from fractions import gcd


A, B, C, D = map(int, input().split())

C_ = B // C
D_ = B // D

C_a = (A-1) // C
D_a = (A-1) // D

# 最小公倍数
CD = (C * D) // gcd(C, D)    # C*D / (最大公約数)

CD_ = (B // CD)
CD_a = ((A-1) // CD)

ans = B - (A-1) - (C_ - C_a) - (D_ - D_a) + (CD_ - CD_a)

print(int(ans))
# 入力
s = input()

# 処理
leftLen :int = len(s) // 2 # 文字列の長さの半分
left :str = s[:leftLen] # sの左半分

# leftの回文チェック
leftLenHalf :int = leftLen // 2
isPalindromeLeft :bool = True
for i in range(0, leftLenHalf - 1):
	if left[i] != left[leftLenHalf - i]:
		isPalindromeLeft = False

# 全体の回文チェック
right :str = s[leftLen * -1:] # sの右半分
isPalindrome :bool = isPalindromeLeft and left == right

# 結果
result :str = "Yes" if isPalindrome else "No"

# 出力
print(result)


### FIXED CODE ###

# 入力
s = input()

# 処理
leftLen = len(s) // 2 # 文字列の長さの半分
left = s[:leftLen] # sの左半分

# leftの回文チェック
leftLenHalf = leftLen // 2
isPalindromeLeft = True
for i in range(0, leftLenHalf):
	if left[i] != left[leftLen - i - 1]:
		isPalindromeLeft = False

# 全体の回文チェック
right = s[leftLen * -1:] # sの右半分
isPalindrome = isPalindromeLeft and left == right

# 結果
result = "Yes" if isPalindrome else "No"

# 出力
print(result)
n=int(input())
x=list(map(int,input().split()))
ans=1
for i in x:
    ans=ans*i
    if ans>10**18:
     ans=-1
     break
    elif ans=0:
     break
print(ans)

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
ans=1
for i in x:
  if i==0:
    print(0)
    exit()

for i in x:
    ans=ans*i
    if ans>10**18:
      ans=-1
      break
print(ans)
A = int(input())
B = int(input())

print(A*B)

### FIXED CODE ###

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

print(A*B)
print('ACL' * int(input())
      

### FIXED CODE ###

print('ACL' * int(input()))
from math import ceil
N,M = map(int,input().split())
list = [list(map(int,input().split())) for i in range(N)]
list.sort(key=lambda x:x[0])

def dfs(m,cnt):
    if m <= 0 or cnt == len(list):
        return 0
    b = list[cnt][1] if list[cnt][1] < m else m
    a = b*list[cnt][0]

    return a + dfs(m-b,cnt+1)

print(dfs(M,0))

### FIXED CODE ###

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

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

list.sort()
sum = 0
cnt = 0

for A,B in list:
    if cnt + B >= M:
        sum += A*(M - cnt)
        cnt += M - cnt
        break
    sum += A*B
    cnt += B

print(sum)
def foo (s):
	ans = 0
	count = 0
	for i in s:
		if   (not count) and (i == 'E'):pass
		elif not count: count += 1
		elif i == 'E': count -= 1; ans += 1
		else: count += 1
	return ans
  
  n = int(input())
  s = input()
  print(foo(s))

### FIXED CODE ###

def foo (s):
	ans = 0
	count = 0
	for i in s:
		if   (not count) and (i == 'E'):pass
		elif not count: count += 1
		elif i == 'E': count -= 1; ans += 1
		else: count += 1
	return ans

n = input()
s = input()

print(foo(s))
n,x = map(int, input().split())
l = list(map(int, input().split()))

s = 0
d = 0
for i in range(n):
  d += l[i]
  s += 1
  if d >= x:
    break
print(s)

### FIXED CODE ###

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

if a <= x: print(10)
else: print(0)
n = int(input())

a = [2**i for i in range(1, 7)]

print(max([x for x in a if x <= n]))

### FIXED CODE ###

n = int(input())
 
a = [2**i for i in range(7)]

print(max([x for x in a if x <= n]))
a = int(input())
Lists = list(map(int, input().split()))

ma = []

for j in range(a):
    test = Lists.pop(0)
    for i in Lists:
        ma.append((i+test)/2)

ma2 = []
for j in ma:
    test = ma.pop(0)
    for i in ma:
        ma2.append((i+test)/2)

print (max(ma2))


### FIXED CODE ###

a = int(input())
Lists = sorted(list(map(int, input().split())))

ans = Lists[0]

for i in range(1,a):
    ans += Lists[i]
    ans /= 2

print(ans)
# coding UTF-8
# 
# problem C
# 

import pandas as pd

t = []
N, M = map(int, input().split())
for i in range(M):
    t.append(tuple(input().split(' ')))

df = pd.DataFrame(t, columns=['p', 'S'])
alist = df.groupby('p')['S'].apply(list)

#print(df)
#print(alist)

#print(alist[0])

#print(alist.apply(lambda d: d[:d.index('AC')))


c = 0
NG = 0
for i in range(len(alist)):
    #print(alist[i])
    try:
        k = alist[i].index('AC')
    except ValueError:
        NGtmp = alist[i].count('WA')
        NG = NG + NGtmp
    else:
        #print(k)
        #print(alist[:k])
        NGtmp = alist[i][:k].count('WA')
        c = c + 1
        NG = NG + NGtmp

#print(c)
#print(NG)

print('{} {}'.format(c, NG))
 

### FIXED CODE ###

import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    aclist = [0] * N
    wrongcount = [0] * N
    for _ in range(M):
        p, S = readline().split()
        q = int(p)-1
        if aclist[q] == 0 and S == 'WA':
            wrongcount[q] += 1
        if S == 'AC':
            aclist[q] = 1

    pena = 0
    for i in range(N):
        if aclist[i] == 1:
            pena += wrongcount[i]
    ac = sum(aclist)

    print(ac, pena)


if __name__ == "__main__":
    main()
N = int(input())

units = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

dp = [100000]*100000
dp[0] = 0
dp[1] = 1

for i in range(2, N+1):
    for unit in units:
        if i - unit >= 0:
            dp[i] = min(dp[i-unit]+1, dp[i])

print(dp[N])


### FIXED CODE ###

N = int(input())

units = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]

dp = [100000]*(N+1)
dp[0] = 0
dp[1] = 1

for i in range(2, N+1):
    for u in units:
        p = i-u
        if p >= 0:
            dp[i] = min(dp[p]+1, dp[i])

print(dp[N])
import sys,math

def solve():
    while True:
        s = input()
        if s == "0 ? 0":
            break
        else:
            print(int(eval(s)//1))
    
solve()


### FIXED CODE ###

import sys,math

def solve():
    while True:
        s = input()
        if "?" in s:
            break
        else:
            print(int(eval(s)//1))
    
solve()
from collections import defaultdict
from math import gcd

N, P = map(int, input().split())
S = input().strip()

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    h = defaultdict(int)
    ans = 0
    for i in range(len(S)-1, -1, -1):
        s = int(S[i:])
        m = s % P
        if m == 0:
            h[m] += 1
            ans += h[m]
        else:
            ans += h[m]
            h[m] += 1

    print(ans)


### FIXED CODE ###

from fractions import gcd

N, P = map(int, input().split())
S = input().strip()

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    s = 0
    for i in range(len(S)-1, -1, -1):
        s = (s + int(S[i])*pow(10, N-1-i, P)) % P
        m = s % P
        if m == 0:
            p[m] += 1
            ans += p[m]
        else:
            ans += p[m]
            p[m] += 1

    print(ans)
#abc176-e
import sys,math,collections,itertools
import numpy as np


input = sys.stdin.readline
H,W,M=list(map(int,input().split()))

point_bom = np.array([[0]*(W+1) for _ in range(H+1)])
for _ in range(M):
    h,w = map(int,input().split())
    point_bom[h][w]=1
#point_bom = np.array(point_bom)
#row_bom = point_bom.sum(axis=0)
#col_bom = point_bom.sum(axis=1)
row_bom = []
for rb in point_bom:
    row_bom.append(sum(rb))
col_bom = [sum(x) for x in zip(*point_bom)]
    
max_row = max(row_bom)
max_col = max(col_bom)

ind_max_row =[]
ind_max_col = []

for i in range(len(row_bom)):
    if row_bom[i] == max_row:
         ind_max_row.append(i)
for i in range(len(col_bom)):
    if col_bom[i] == max_col:
        ind_max_col.append(i)

flag = 1#爆破対象が置かれる　おかれている＝１　いない＝０
for mr in ind_max_row:
    for mc in ind_max_col:
        if point_bom[mc][mr] == 0:
            flag = 0
            break
    if flag == 0:
        break
print(max_row+max_col - flag)
        
        


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W,M=map(int,input().split())
bom = [] #ボムの場所
bomH =[0]*(H+1) 
bomW=[0]*(W+1)

for _ in range(M):
    h,w=map(int,input().split())
    bom.append((h,w))
    bomH[h]+=1
    bomW[w]+=1

#縦の爆弾と横の爆弾は独立。爆弾を置く場所に爆弾があると-1
max_bomH = max(bomH)
max_bomW = max(bomW)

cnt = 0#爆弾が置かれた場所のbomH,bomWがともにMaxの場所の数
for h,w in bom:
    if bomH[h]==max_bomH and bomW[w] == max_bomW:
        cnt += 1

print(max_bomH +max_bomW -(cnt == bomH.count(max_bomH) * bomW.count(max_bomW)))
import math
import functools
import fractions
from functools import reduce
import itertools

gcd1 = 0
gcd2 = 0
ans = 0

N = int(input())
values = ([int(x) for x in input().split()])
for i in list(itertools.combinations(values,2)):
  gcd1 = functools.reduce(fractions.gcd,i)
  if gcd1>gcd2:
    gcd2 = gcd1
    ans = gcd1
    
print(ans)

### FIXED CODE ###

#スペース区切りの整数の入力
A, B, T= map(int, input().split())
ans = (int(T/A))*B
print("{}".format(ans))
a,b=map(int,input().split.(""))
print(a-b+1)

### FIXED CODE ###

a, b = map(int, input().split())
print(a-b+1)
flg=False


for i in range(10**6):
    
    temp = A*i
    
    if temp%B==C:
        flg=True
        break
        
        
if flg==True:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

flg=False


for i in range(10**6):
    
    temp = A*i
    
    if temp%B==C:
        flg=True
        break
        
        
if flg==True:
    print("YES")
else:
    print("NO")
import math

N = int(input())

n = int(math.sqrt(N))
lens = []
for a in range(1, n):
  if N % a == 0:
    lens.append(a+N//a-2)

print(min(lens))


### FIXED CODE ###

import math

N = int(input())

n = int(math.sqrt(N)) + 1
lens = [N-1]
for a in range(2, n):
  if N % a == 0:
    lens.append(a+N//a-2)

print(min(lens))
n, x = map(int,input().split())
l = list(map(int,input().split()))
d = 0
i = 0
while(d <= x):
    d = d + l[i]
    i += 1

print(i)


### FIXED CODE ###

n, x = map(int,input().split())
l = list(map(int,input().split()))
d = 0 #1回目の座標
#2回目以降
count = 1
for i in range (0,n):
    d = d + l[i]
    if(d > x):
        break
    count += 1

print(count)
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K - 1 < d[1]:
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
import re

input()
print(len(re.findall(input(), 'ABC'))

### FIXED CODE ###

import re

input()
print(len(re.findall('ABC', input())))
x, a = map(int, input().split())
    r = 0 if x < a else 10
    print(r)

### FIXED CODE ###

x, a = map(int, input().split())
r = 0 if x < a else 10
print(r)
# 73

MOD = 10**9 + 7
x, y = map(int, input().split())

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = (finv_l[i-1] * inv_l[i]) % MOD

def ncr(n, r):
    return (fac_l[n] * (finv_l[r] * finv_l[n-r]) % MOD) % MOD


if a % 3 != 0 or b % 3 != 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))


### FIXED CODE ###

# 73

MOD = 10**9 + 7
x, y = map(int, input().split())

a = 2*y - x
b = 2*x - y

fac_l = [0] * (int((a + b) / 3) + 1)
inv_l = [0] * (int((a + b) / 3) + 1)
finv_l = [0] * (int((a + b) / 3) + 1)


def com_init():
    fac_l[1] = 1
    inv_l[0] = 1
    inv_l[1] = 1
    finv_l[0] = 1
    finv_l[1] = 1
    for i in range(2, a+b+1):
        fac_l[i] = (fac_l[i-1] * i) % MOD
        inv_l[i] = MOD - (inv_l[MOD % i] * int(MOD / i)) % MOD
        finv_l[i] = (finv_l[i-1] * inv_l[i]) % MOD

def ncr(n, r):
    return (fac_l[n] * (finv_l[r] * finv_l[n-r]) % MOD) % MOD


if a % 3 != 0 or b % 3 != 0 or a < 0 or b < 0:
    print("0")
else:
    a = int(a/3)
    b = int(b/3)

    com_init()
    print(ncr(a+b, a))
n = int(input())
a = input()
b = input()

import itertools
l = list(itertools.permutations(range(1,n+1))
print(abs(l.index(a)-l.index(b)))

### FIXED CODE ###

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

import itertools
l = list(itertools.permutations(range(1, n+1)))
#permutations:順列 combinations:組み合わせ (list, 数字)rCnのnが「数字」で決まる
print(abs(l.index(p) - l.index(q)))