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

import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
S = np.array([['' for i in range(w)] for j in range(h)])
for i in range(h):
  line = input()
  for j in range(w):
    S[i][j] = line[j]
#print(S)
  
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

q = deque()

def update(vs, i, j, x, q):
  if vs[i, j] != np.inf or S[i, j] == '#':
    return
  vs[i, j] = x
  q.append((i,j))

mx = 0
for i, j in product(range(h), range(w)):
  if S[i, j] == '#':
    continue
  vs = np.array([[np.inf for i in range(w)] for j in range(h)])
  x = 0
  update(vs, i, j, x , q)
  while len(q) > 0:
    #print(q)
    #print(vs)
    # x += 1
    current_q = q.popleft()
    qi, qj = current_q[0], current_q[1]
    for k in range(4):
      ni, nj = qi + di[k], qj + dj[k]
      if not(0 <= ni < h) or not(0 <= nj < w):
        continue
      update(vs, ni, nj, vs[qi][qj]+1, q)
  for i, j in product(range(h), range(w)):
    if vs[i,j] == np.inf: continue
    mx = max(mx, vs[i,j])
print(int(mx))
      

### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
#print(S)
  
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

def update(vs, i, j, x, q):
  if vs[i][j] != -1 or S[i][j] == '#':
    return
  vs[i][j] = x
  q.append((i,j))

mx = 0
for i, j in product(range(h), range(w)):
  if S[i][j] == '#':
    continue
  q = deque([])
  vs = [[-1 for i in range(w)] for j in range(h)]
  update(vs, i, j, 0, q)
  while len(q) > 0:
    #print(q)
    #print(vs)
    # x += 1
    current_q = q.popleft()
    qi, qj = current_q[0], current_q[1]
    for k in range(4):
      ni, nj = qi + di[k], qj + dj[k]
      if not(0 <= ni < h) or not(0 <= nj < w):
        continue
      update(vs, ni, nj, vs[qi][qj]+1, q)
  for i, j in product(range(h),range(w)):
    if vs[i][j] == -1:
      continue
    mx = max(mx, vs[i][j])
print(int(mx))
### BUGGY CODE ###

class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l] % self.MOD) % self.MOD
        return res

n = int(input())
s = input()

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set([])
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)

### FIXED CODE ###

def LRS(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = ""
    res_length = 0
  
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
n = int(input())
s = input()

print(len(LRS(s)))
### BUGGY CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
result = []

for i in range(2**n):
    list_v = []
    list_c = []
    for j in range(n):
        if (i >> j) &1 ==1:
            list_v.append(v[j])
            list_c.append(c[j])
    result.append(sum(list_v)-sum(list_c))

print(max(result))

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
result = 0

for i in range(2**n):
    list_v = []
    list_c = []
    for j in range(n):
        if (i >> j) &1 ==1:
            list_v.append(v[j])
            list_c.append(c[j])
    if sum(list_v) - sum(list_c) >= result:
        result = sum(list_v) - sum(list_c)

print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
n, k, q =map(int, input().split())
m = [k]*n
for i in range(q):
  a = int(input())-1
  m[a]+=1
  for j in range(n):
    m[j]-=1

for i in range(n):
  if m[i]>0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, k, q =map(int, input().split())
a = [int(input()) for i in range(q)]

p = [0]*(n+1)

for i in range(q):
  p[a[i]] += 1
  

for i in range(1,n+1):
  if p[i]>q-k:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N = int(input())
ARR = list(map(int,input().split()))

# N = 2
# ARR = [1000000000, 1000000000]

def calculate(n,arr):
    res = 1

    for i in range(n):
        res = res * arr[i]

    if res > 1000000000000000000:
        res = -1

    return res

print(calculate(N,ARR))



### FIXED CODE ###

N = int(input())
ARR = list(map(int, input().split()))


# N = 3
# ARR = [1000000000, 0, 9]
#
# N = 31
# ARR =  [4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0]

def calculate(n, arr):
    res = 1
    for i in range(n):
        if arr[i] == 0:
            res = 0
            break

        if res == -1:
            continue

        res = res * arr[i]
        if res > 1000000000000000000:
            res = -1

    return res


print(calculate(N, ARR))
### BUGGY CODE ###

def f(s,K):
 if len(s)==1:
  if ord(s[0])+K<123:
   return chr(ord(s[0])+K)
  else:
   return chr((((ord(s[0])+K)-97)%26)+97)
 res=0
 for i in range(len(s)):
  if s[i]=="a":
   continue
  if K>=123-ord(s[i]):
   res+=1
   K-=123-ord(s[i])
  else:
   break
 str=""
 for i in range(res):
  str+="a"
 if res==0:
  return s[0]+f(s[1:],K)
 return str+f(s[res:],K)
ss=input()
KK=int(input())
print(f(ss,KK))

### FIXED CODE ###

def f(s,K):
 if K==0:
  return s,"",0
 res=0
 str=""
 for i in range(len(s)-1):
  if s[i]=="a":
   str+="a"
   res+=1
   continue
  if K>=123-ord(s[i]):
   str+="a"
   res+=1
   K-=123-ord(s[i])
  else:
   break
 if res==0:
  skip=0
  for skip in range(len(s)):
   if K>=123-ord(s[skip]):
    break
  return s[:skip],s[skip:],K
 return str,s[res:],K

ss=input()
KK=int(input())
sol=""
while len(ss)>1:
 x,ss,KK=f(ss,KK)
 sol+=x
if len(ss)==1:
 KK%=26
 if ord(ss[0])+KK<123:
  sol+=chr(ord(ss[0])+KK)
 else:
  sol+=chr(ord(ss[0])+KK-26)
print(sol)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


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

N = int(input())
A = list(map(int,input().split()))
c = [0]*N

for i in range(N):
    c[i] = A.index(i+1)+1
print(' '.join(map(str, c)))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
c = [0]*N

for i in range(N):
    a = A[i]
    c[a-1] = i+1
print(' '.join(map(str, c)))
### BUGGY CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
D = None
D_dfs_d = None


def dfs_d(v, pre, dist):
    global D_dfs_d

    D_dfs_d[v] = dist

    for i, d in enumerate(D[v]):
        if d != -1 and i != pre:
            dfs_d(i, v, dist + d)

    return


def main():
    global D
    global D_dfs_d

    N = int(input())
    D = [[-1] * (N + 1) for _ in range(N + 1)]
    D_dfs_d = [-1] * (N + 1)

    for i in range(N - 1):
        a, b, c = li_input()
        D[a][b] = c
        D[b][a] = c

    Q, K = li_input()

    # Kから各頂点までの長さをWFSで求める
    dfs_d(K, -1, 0)

    for i in range(Q):
        x, y = li_input()
        print(D_dfs_d[x] + D_dfs_d[y])


main()


### FIXED CODE ###

import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
D = None
D_dfs_d = None


def dfs_d(v, pre, dist):
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def main():
    global D
    global D_dfs_d

    N = int(input())
    D_dfs_d = [-1] * (N + 1)
    D = [[] for _ in range(N + 1)]

    for i in range(N - 1):
        a, b, c = li_input()
        D[a].append((b, c))
        D[b].append((a, c))

    Q, K = li_input()

    # Kから各頂点までの長さをWFSで求める
    dfs_d(K, -1, 0)

    for i in range(Q):
        x, y = li_input()
        print(D_dfs_d[x] + D_dfs_d[y])


main()
### BUGGY CODE ###

a, b, c, d = list(map(int, input().split()))
ad = set()
for i in range(a, b + 1):
    for j in range(c, d + 1):
        ans = i * j
        ad.add(ans)

print(max(ad))

### FIXED CODE ###

a, b, c, d = list(map(int, input().split()))
print(max(a*c, a*d, b*c, b*d))
### BUGGY CODE ###

#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for _ in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
for i in range(len(s))[::-1]:
    cum[i+1]=int(s[i:])%2019
    if cum[i+1] in d:
        ret += d[cum[i+1]]
    d[cum[i+1]] += 1
#print(d,cum,ret)
print(ret)

### FIXED CODE ###

# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig = (dig*10)%2019
    #cum[i+1]=int(s[i:])%2019
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1
#print(d,cum,ret)
print(ret)
### BUGGY CODE ###

N = input()
n = len(N)
Ans = set()
Ans.add(N)

for i in range(n):
    for j in range(i + 1, n):
        Ans.add(N[:i] + N[i:j+1][::-1] + N[j + 1:])

print(len(Ans))

### FIXED CODE ###

from collections import Counter

N = input()
n = len(N)

NC = Counter(N)
ans = n * (n - 1) // 2 + 1

for value in NC.values():
    ans -= value * (value - 1) // 2

print(ans)
### BUGGY CODE ###

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

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)

### FIXED CODE ###

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

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)
### BUGGY CODE ###

n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(sum(v)+1):
    if j - v[i] >= 0:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)


### FIXED CODE ###

n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(sum(v)+1):
    if j - v[i] >= 0:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)
### BUGGY CODE ###

# D - FT Robot
# coding: utf-8

def check(d, to_d):
  meu = [0]
  for i in to_d:
    hoge = []
    for j in meu:
      if not j+i in hoge : hoge.append(j+i) 
      if not j-i in hoge : hoge.append(j-i)
    meu = hoge
  return d in meu

S = map(len, raw_input().split('T'))
x, y = map(int, raw_input().split())
to_x, to_y = S[2::2], S[1::2]

print "Yes" if check(x-S[0],to_x) and check(y,to_y) else "No"

### FIXED CODE ###

# D - FT Robot
# coding: utf-8

def check(d, to_d):
  meu = set([0])
  for i in to_d:
    hoge = set([])
    for j in meu: hoge.add(j+i), hoge.add(j-i)
    meu = hoge
  return d in meu

S = map(len, raw_input().split('T'))
x, y = map(int, raw_input().split())
to_x, to_y = S[2::2], S[1::2]

print "Yes" if check(x-S[0],to_x) and check(y,to_y) else "No"
### BUGGY CODE ###

n=int(input())
ans=0
s=[]
for i in range(n):
  a=sorted(input())
  ans+=s.count(a)
  s.append(a)
print(ans)

### FIXED CODE ###

N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)
### BUGGY CODE ###


K = int(input())
n = 0
cnt = 0
tmp = 0
while cnt < K:

    n = n + 1
    nDigit = []
    nDiv   = []
    flg = True
    digits = len(str(n))
    tmpN = n
    for i in range(0,digits) :
        nDigit.append(tmpN // (10 ** (digits-i-1)))
        tmpN = tmpN % (10 ** (digits-i-1))
    if len(nDigit) == 1 :
        cnt = cnt + 1
        tmp = n
    else :
        tR = 0
        for i in range(0,len(nDigit)-1) :
            if abs(nDigit[i] - nDigit[i+1]) > 1 :
                flg = False
                tR = i
                i = len(nDigit)
        if flg == True :
            cnt = cnt + 1
            tmp = n
        elif nDigit[tR] - nDigit[tR+1] < 0 :
            n = n - (n % (10 ** (digits - tR))) + (nDigit[tR] + 1) * (10 ** (digits-tR-1)) - 1

#for i in range(0,len(LunList)) :
#    print(i,LunList[i])
print(n)


### FIXED CODE ###

k = int(input())

i = 1
q = []
while i <= k :
    if(i < 10) :
        q.append(i)
    else :
        x = q.pop(0)
        tmp = 10 * x + (x % 10)
        if x % 10 != 0 :
            q.append(tmp-1)
            i+=1
        q.append(tmp)
        if x % 10 != 9 :
            q.append(tmp+1)
            i+=1
    i+=1
print(q.pop(k-i))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N, Q = MI()
    #木
    tree = [[]]*N
    visit = [True]*N
    for i in range(N-1):
        a,b = MI()
        if len(tree[a-1]) == 0:
            tree[a-1] = [b-1]
            tree[b-1] = [a-1]
        else:
            tree[a-1].append(b-1)
            tree[b-1].append(a-1)
    #カウンター保存用、初期化
    counter = [0]* N
    score = [0]* N
    dq = deque([0])
    visit[0] = False
    for i in range(Q):
        p, x = MI()
        counter[p-1] += x
    score[0] = counter[0]
    while dq:
        temp = dq.pop()
        for num in tree[temp]:
            if visit[num]:
                score[num] = score[temp]+counter[num]
                dq.append(num)
                visit[num] = False
    score = [str(i) for i in score]
    print(" ".join(score))
    return None

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
 
def main():
    n,q = map(int,ipt().split())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)
    pl = [0]*(n+1)
    for i in range(q):
        p,x = map(int,ipt().split())
        pl[p] += x
    ans = [-1]*(n+1)
    ans[0] = 0
    ans[1] = pl[1]
    q = [(1,0)]
 
    while q:
        qi,qp = q.pop()
        qa = ans[qi]
        for j in way[qi]:
            if j == qp:
                continue
            ans[j] = qa+pl[j]
            q.append((j,qi))
 
    print(" ".join(map(str,ans[1::])))
 
    return None
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = input()
ctr1 = Counter()
ctr2 = Counter()

for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += S[k]
        else:
            red += S[k]
    ctr1[(blue,red)] += 1

T = S[::-1][:N]
for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += T[k]
        else:
            red += T[k]
    ctr2[(blue,red)] += 1

ans = 0
for (b1,r1),v1 in ctr1.items():
    for (b2,r2),v2 in ctr2.items():
        if b1==r2 and b2==r1:
            ans += v1*v2
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
ctr1 = Counter()
ctr2 = Counter()

for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += S[k]
        else:
            red += S[k]
    ctr1[(blue,red)] += 1

T = S[:-N-1:-1]
for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += T[k]
        else:
            red += T[k]
    ctr2[(blue,red)] += 1

ans = 0
for k,v in ctr1.items():
    ans += v * ctr2[k]
print(ans)
### BUGGY CODE ###

N = input()
a = []
for i in range(N):
        a.append(input())
for i in range(N):
        b = a.pop(i)
        print(max(a))
        a.insert(i,b)


### FIXED CODE ###

N = input()
a = []
for i in range(N):
        a.append(input())
b = sorted(a)
b0,b1 = b[-1],b[-2]
for i in range(N):
        if a[i]!=b0 :
                print(b0)
        else:
                print(b1)
### BUGGY CODE ###

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c

from itertools import product, permutations
for i, j, k in product(range(1, 1 + n), repeat=3):
    if dists[j, k] > dists[j, i] + dists[i, k]:
        dists[j, k] = dists[j, i] + dists[i, k]

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

print(ans)

### FIXED CODE ###

n, m, r = list(map(int, input().split()))
rs = list(map(int, input().split()))
# construct map
import numpy as np
dists = np.ones((n + 1, n + 1)) * float('inf')
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
for i in range(1, n + 1):
    dists[i, i] = 0

from itertools import product, permutations
for i, k in product(range(1, 1 + n), repeat=2):
    dists[:, k] = np.minimum(dists[:, k], dists[:, i] + dists[i, k])

ans = float('inf')
for path in permutations(rs):
    val = sum(dists[i, j] for i, j in zip(path, path[1:]))
    val = int(val)
    if val < ans:
        ans = val

print(ans)