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

from itertools import permutations
import sys

N, M, R = map(int, sys.stdin.readline().split())
r = [i - 1 for i in map(int, sys.stdin.readline().split())]

d = [[float('inf') for i in range(N)] for j in range(N)]

for i in range(N):
    d[i][i] = 0
    
for i in range(M):
    a, b, c = map(int,sys.stdin.readline().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

ans = 10**12

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += d[each[i]][each[i+1]]  
    
    ans = min(ans, t_dis)

print(ans)

### FIXED CODE ###

from collections import defaultdict
from itertools import permutations
import heapq

INF = float('inf')
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
memo = [[INF for _ in range(N)] for _ in range(N)]

Adj_list = defaultdict(set)

for i in range(M):
    a, b, c = map(int, input().split())
    if memo[a-1][b-1]:
        memo[a-1][b-1] = min(memo[a-1][b-1], c)
        
    Adj_list[a-1].add((b-1, memo[a-1][b-1]))
    Adj_list[b-1].add((a-1, memo[a-1][b-1]))


def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d

ans = INF
t_dis = 0

table = {}
for i in r:
    table[i-1] = dijkstra(N, i-1)

for each in permutations(r):
    t_dis = 0
    for i in range(R-1):
        t_dis += table[each[i]-1][each[i+1]-1]
    #print(each, t_dis)
    ans = min(ans, t_dis)

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

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
k = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
d = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if i in a:
      continue
    elif i==1:
      dp[i] = d
    elif i==2:
      d += dp[1]
      dp[i] = d
    else:
      d = d-dp[i-3]+dp[i-1]
      dp[i] = dp[i-1]+dp[i-2]
  print(dp[N]%k)

### FIXED CODE ###

N,M = map(int,input().split())
a = set([int(input()) for _ in range(M)])
k = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if i in a:
      continue
    elif i==1:
      dp[1] = 1
    elif i==2:
      dp[i] = 1+dp[1]
    else:
      dp[i] = dp[i-1]+dp[i-2]
  print(dp[N]%k)
### BUGGY CODE ###

N,X,Y = map(int, input().split())
Dis = [[0 for i in range(N)] for j in range(N)]
count = [0]*(N-1)
c=0
for i in range(N):
    for j in range(i+1,N):
        if abs(i-j) >= abs(X-i-1)+1+abs(Y-j-1):
            Dis[i][j] = abs(X-i-1)+1+abs(Y-j-1)
        else:
            Dis[i][j] = abs(i-j)
for k in range(1,N):
    for i in range(N):
        for j in range(i+1,N):
            if Dis[i][j] == k:
                c+=1
    count[k-1]=c
    c=0
for i in range(N-1):
    print(count[i])

### FIXED CODE ###

N,X,Y = map(int, input().split())
count = [0]*(N-1)
c=0
for i in range(0,N):
    for j in range(i+1,N):
        if abs(i-j) >= abs(X-i-1)+1+abs(Y-j-1):
            count[abs(X-i-1)+1+abs(Y-j-1)-1] +=1
        else:
            count[abs(i-j)-1] += 1
for i in range(N-1):
    print(count[i])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(1000)]
memo[0][Ch-1][Cw-1] = True

ans = -1

while d:
    h, w, c = d.popleft()

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[c][h+i][w+j]:
                    memo[c][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[c][h+i][w+j] and not memo[c+1][h+i][w+j]:
                        memo[c+1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(2)]
memo[0][Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

while d:
    h, w, c = d.popleft()

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[0][h+i][w+j] and not searched[h+i][w+j]:
                    memo[0][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[0][h+i][w+j] and not memo[1][h+i][w+j] and not searched[h+i][w+j]:
                        memo[1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

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

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        if s == '1':
            if a not in dp:
                dp = set()
                break
        else:
            for b in dp.copy():
                dp.add(b ^ a)
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')


### FIXED CODE ###

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        for b in dp:
            a = min(a, a ^ b)
        if s == '1':
            if a:
                dp = set()
                break
        else:
            dp2 = set([a])
            for b in dp:
                dp2.add(min(b, a ^ b))
            dp = dp2
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))


ab_sum = [0] * (X * Y)
i = 0
for a in a_list:
    for b in b_list:
        ab_sum[i] = a + b
        i += 1
ab_sum.sort(reverse = True)

answer_sums = [0] * (K * Z)
i = 0
for e in ab_sum[:K]:
    for c in c_list:
        answer_sums[i] = e + c
        i += 1
answer_sums.sort(reverse = True)
[print(num) for num in answer_sums[:K]]


### FIXED CODE ###

import heapq

X, Y, Z, K = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

heap = []
heapq.heappush(heap, (-(a_list[0] + b_list[0] + c_list[0]), 0, 0, 0))
searched = []
result = [0] * K

for k in range(K):
    elem = heapq.heappop(heap)
    result[k] = - elem[0]

    if elem[1] + 1 <= X - 1:
        a_next = (-(a_list[elem[1] + 1] + b_list[elem[2]] + c_list[elem[3]]), elem[1] + 1, elem[2], elem[3])
        if not a_next in searched:
            heapq.heappush(heap, a_next)
            searched.append(a_next)

    if elem[2] + 1 <= Y - 1:
        b_next = (-(a_list[elem[1]] + b_list[elem[2] + 1] + c_list[elem[3]]), elem[1], elem[2] + 1, elem[3])
        if not b_next in searched:
            heapq.heappush(heap, b_next)
            searched.append(b_next)

    if elem[3] + 1 <= Z - 1:
        c_next = (-(a_list[elem[1]] + b_list[elem[2]] + c_list[elem[3] + 1]), elem[1], elem[2], elem[3] + 1)
        if not c_next in searched:
            heapq.heappush(heap, c_next)
            searched.append(c_next)

[print(k) for k in result]
### BUGGY CODE ###

s = input()
l = len(s)
mod = (10**9)+7

dp = [[0 for j in range(13)] for i in range(l)]

if s[0] == '?':
    dp[0][0:9] = [1 for x in range(10)]
else:
    dp[0][int(s[0])] = 1

for i in range(l-1):
    a = i+1
    if s[a] == '?':
        for j in range(10):
            for k in range(13):
                dp[a][(k*10+j)%13] += dp[a-1][k]%mod
    else:
        for k in range(13):
            dp[a][(k*10+int(s[a]))%13] += dp[a-1][k]%mod

print(dp[l-1][5]%mod)

### FIXED CODE ###

s = input()
l = len(s)
mod = (10**9)+7

dp = [[0 for j in range(13)] for i in range(l)]

if s[0] == '?':
    dp[0][0:9] = [1 for x in range(10)]
else:
    dp[0][int(s[0])] = 1

for i in range(l-1):
    a = i+1
    x = s[a]
    if x == '?':
        for j in range(10):
            for k in range(13):
                dp[a][(k*10+j)%13] += dp[a-1][k]%mod
    else:
        for k in range(13):
            dp[a][(k*10+int(x))%13] += dp[a-1][k]%mod

print(dp[-1][5]%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
N = int(input())
a = list(map(int,input().split()))

cum = [0]*(N+1)
for i in range(N):
    cum[i] = cum[i-1]+a[i]

dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = a[i]

def cal(i,j):
    if dp[i][j] == -1:
        dp[i][j] = cum[j]-cum[i-1]-min(cal(i+1,j),cal(i,j-1))
    return dp[i][j]

print(2*cal(0,N-1)-cum[N-1])

### FIXED CODE ###

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

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N-1, -1, -1):
    for j in range(i, N):
        dp[i][j] = max(a[i]-dp[i+1][j],a[j]-dp[i][j-1])

print(dp[0][N-1])
### BUGGY CODE ###

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]

xl.sort(key=lambda x:x[1])

cnt = [0 for _ in range(10**8)]
ans = [0 for _ in range(n)]

for i in range(n):
    for j in range(xl[i][0] - xl[i][1] + 1, xl[i][0] + xl[i][1]):
        if cnt[j] == 0:
            cnt[j] = 1
        else:
            break
        if j == xl[i][0] + xl[i][1]-1:
            ans[i] = 1

print(sum(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x + l, x - l] for x, l in xl])

ans = 0
mr = xl2[0][1]
for r, l in xl2:
    if l >= mr:
        ans += 1
        mr = r
print(ans)
### BUGGY CODE ###

from collections import defaultdict


def get_data(data_dic, num, check_data):
    for i in range(len(data_dic))[::-1]:
        if data_dic[i][0] == num:
            check_data.add(data_dic[i])
            data_dic.pop(i)
        elif data_dic[i][1] == num:
            data_add = (data_dic[i][1], data_dic[i][0], data_dic[i][2])
            check_data.add(data_add)
            data_dic.pop(i)
    return check_data, data_dic


def main():
    num = int(input())


    data_dic = [tuple(map(int, input().split())) for i in range(num - 1)]
    parent_data = [-1 for i in range(num + 1)]
    dist_data = [0 for i in range(num + 1)]

    check_data_now, data_dic = get_data(data_dic, 1, set())
    check_data_next = set()

    while len(check_data_now) > 0:
        parent_list = set()
        for u, v, w in check_data_now:
            parent_data[v] = u
            dist_data[v] = w % 2
            parent_list.add(v)


        for ele in parent_list:
            check_data_next, data_dic = get_data(data_dic, ele, check_data_next)
        check_data_now = check_data_next
        check_data_next = set()

    dist_ori_data = [-1 for i in range(num + 1)]
    dist_ori_data[1] = 0

    for i in range(1, num + 1):
        if dist_ori_data[i] != -1:
            continue
        dist = 0
        now_data = i
        while parent_data[now_data] != -1:
            if dist_ori_data[now_data] != -1:
                dist += dist_ori_data[now_data]
                break
            else:
                dist += dist_data[now_data]
                now_data = parent_data[now_data]
        dist_ori_data[i] = dist % 2

    for i in range(1, num + 1):
        dist = dist_ori_data[i]
        if dist % 2 == 0:
            print(0)
        else:
            print(1)








if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys


def visit(current, v, dist, color):
    for ele in v[current]:
        if color[ele] != -1:
            continue
        if dist[(ele, current)] % 2 == 0:
            color[ele] = color[current]
        else:
            if color[current] == 0:
                color[ele] = 1
            else:
                color[ele] = 0
        visit(ele, v, dist, color)

def main():
    sys.setrecursionlimit(100100)
    num = int(input())

    v = [[] for i in range(num + 1)]

    dist = {}

    for i in range(1, num):
        a, b, d = map(int, input().split())
        v[a].append(b)
        v[b].append(a)
        dist[(a, b)] = d
        dist[(b, a)] = d

    color = [-1 for i in range(num + 1)]
    color[1] = 0
    visit(1, v, dist, color)

    for i in range(1, num + 1):
        print(color[i])

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

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def nasu(n, m):
  ans = (com.com(n + 2, m + 1) - 1)
  return ans
N = r2 + c2
com = comb(N + 3, MOD)

ans = nasu(N, r2)
ans = (ans + nasu(c1 + r1 - 2, min(c1, r1) - 1)) % MOD
ans = (ans - nasu(r2 + c1 - 1, c1 - 1))
ans = (ans - nasu(c2 + r1 - 1, r1 - 1))
while ans < 0: ans += MOD

print(ans)

### FIXED CODE ###

class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


r1, c1, r2, c2 = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def nasu(n, m):
  if n < 0 or m < 0: return 0
  ans = (com.com(n + 2, m + 1) - 1)
  return ans
N = r2 + c2
com = comb(N + 3, MOD)

ans = nasu(N, r2)
ans = (ans + nasu(c1 + r1 - 2, min(c1, r1) - 1)) % MOD
ans = (ans - nasu(r2 + c1 - 1, c1 - 1))
ans = (ans - nasu(c2 + r1 - 1, r1 - 1))
while ans < 0: ans += MOD

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

import heapq
n,a,b = map(int,input().split())
q = [-int(input()) for i in range(n)]
heapq.heapify(q)


ans = 0
count = 0
while q[0]+b*count<0:
  num = heapq.heappop(q)
  num=num+(a-b)
  heapq.heappush(q,num)
  ans += 1
  count += 1
print(ans)

### FIXED CODE ###

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

h = [int(input()) for i in range(n)]
diff = a-b
def solve(num):
  kaisu = 0
  for i in range(n):
    if -((-(h[i]-num*b))//diff) > 0:
      kaisu += -((-(h[i]-num*b))//diff)
  if kaisu <= num:
    return True
  else:
    return False
    
ng = 0
ok = 1000000001

while abs(ok-ng)>1:
  mid = (ok+ng)//2
  if solve(mid):
    ok = mid
  else:
    ng = mid
#  print(ng,ok)
print(ok)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

# 距離が3のノード間にだけ辺を張り直す
row = []
col = []
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  _g = list(set(d))
  row.extend([i] * len(_g))
  col.extend(_g)

d = [1] * len(row)
graph = csr_matrix((d, (row, col)), shape=(N, N))
S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=S).astype(int)
if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(3*N)]
for i in range(M):
  u, v = map(int, input().split())
  u, v = 3*(u - 1), 3*(v - 1)
  graph[u].append(v+1)
  graph[u+1].append(v+2)
  graph[u+2].append(v)

s, t = map(int, input().split())
s, t = 3*(s - 1), 3*(t - 1)


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)
### BUGGY CODE ###

def main():
    n, k, q = map(int, input().split())
    
    ls = [k] * n

    for i in range(q):
        maru = int(input())
        for j in range(n):
            if j != maru - 1:
                ls[j] -= 1

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

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

def main():
    n, k, q = map(int, input().split())
    
    ls = [q] * n

    rls = [k] * n

    maru_list = [0] * n

    ls = np.array(ls)
    rls = np.array(rls)
    maru_list = np.array(maru_list)

    for i in range(q):
        maru = int(input())
        maru_list[maru-1] += 1

    ls = ls - maru_list

    rls = rls - ls

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

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

m = 10**9+7
n = int(input())
a = list(map(int, input().split()))
check = 0
for i in set(a):
  if n%2 == 1:
    if i == 0 and a.count(i) == 1:
      pass
    elif i%2 == 0 and a.count(i) == 2:
      pass
    else:
      print(0)
      exit()
  else:
    if i%2 == 1 and a.count(i) == 2:
      pass
    else:
      print(0)
      exit()

print(2**(n//2)%m)

### FIXED CODE ###

m = 10**9+7
n = int(input())
a = list(map(int, input().split()))
check = True
if n%2 == 0:
    if 0 in a or len(set(a)) != n//2:
      check = False
else:
    if len([0 for i in a if i==0]) != 1 or len(set(a)) != n//2+1:
      check = False
      
if check:
  print(2**(n//2)%m)
else:
  print(0)
### BUGGY CODE ###

n,x,y = map(int,input().split())

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [sorted(dijkstra(i)[i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)

### FIXED CODE ###

n,x,y = map(int,input().split())

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [sorted(dijkstra(i)[i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)
### BUGGY CODE ###

import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        for v in edges[u]:
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

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

ans = [0] * (n - 1)


def col(now, color):
    c = 1
    for (b, j) in A[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b, c)
        c += 1


col(0, 0)
print(max(ans))
for a in ans:
    print(a)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**10
for i in range(n):
	loop=[0]
	now=i
	while True:
		now=p[now]-1
		loop.append(loop[-1]+c[now])
		if now==i:
			break
	L=len(loop)-1
	if k<=L:
		score=max(loop[1:k+1])
		ans=max(score,ans)
	else:
		score=max(loop[-1],0)*(k//L-1)
		ans=max(ans,score)
		for j in range(k%L+L):
			score+=loop[j%L+1]-loop[j%L]
			ans=max(score,ans)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**10
for i in range(n):
	loop=[0]
	now=i
	while True:
		now=p[now]-1
		loop.append(loop[-1]+c[now])
		if now==i:
			break
	L=len(loop)-1
	if k<=L:
		score=max(loop[1:k+1])
		ans=max(score,ans)
	else:
		score=max(loop[-1],0)*(k//L-1)
		ans=max(ans,score)
		for j in range(k%L+L):
			score+=loop[j%L+1]-loop[j%L]
			ans=max(score,ans)
print(ans)
### BUGGY CODE ###

S = list(input())
Q = int(input())

for i in range(Q):
  list_ = list(input().split())
  T = int(list_[0])
  if T == 1:
    S.reverse()
  else:
    F, C = int(list_[1]), list_[2]
    if F == 1:
      S.insert(0, C)
    else:
      S.append(C)
ans = ''.join(S)
print(ans)

### FIXED CODE ###

S = list(input())
Q = int(input())
t_count = 0
before = []
after = []

for i in range(Q):
  list_ = list(input().split())
  T = int(list_[0])
  if T == 1:
    t_count += 1
  else:
    F, C = int(list_[1]), list_[2]
    if F == 1:
      if t_count%2 == 0:
        before.append(C)
      else:
        after.append(C)
    else:
      if t_count%2 == 0:
        after.append(C)
      else:
        before.append(C)
before.reverse()
S.extend(after)
before.extend(S)
if t_count%2 == 1:
  before.reverse() 
ans = ''.join(before)
print(ans)
### BUGGY CODE ###

kind = int(input())
top = input().split()
top = [int(x) for x in top]
top.sort()
middle = input().split()
middle = [int(x) for x in middle]
middle.sort()
down = input().split()
down = [int(x) for x in down]
down.sort()

res = 0
for i in range(0, len(down)):
    for j in range(0, len(middle)):
        if middle[j] >= down[i]:
            break
        for k in range(0, len(top)):
            if top[k] >= middle[j]:
                break
            elif top[k] < middle[j] < down[i]:
                res += 1
print(res)


### FIXED CODE ###

import bisect

num = int(input())
top = sorted([int(x) for x in input().split()])
middle = sorted([int(x) for x in input().split()])
bottom = sorted([int(x) for x in input().split()])


# middleの配列でループを回したほうが早い(topとbottomを同時に処理できるため)
res = 0
for i in middle:
    index = bisect.bisect_left(top, i)
    index2 = len(bottom)-bisect.bisect_right(bottom, i)
    res += index*index2

print(res)