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

import sys

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, goal):
    q = [[start]]
    q_d = [0]
    d_set = set()
    while(len(q) > 0):
        path = q.pop(0)
        dist = q_d.pop(0)
        w = path[len(path) - 1]
        if w == goal:
            d_set.add(dist)
        else:
            for x in adj_list[w]:
                if x[0] not in path:
                    new_path = path[:]
                    new_path.append(x[0])
                    q.append(new_path)
                    q_d.append(dist + x[1])
    if len(d_set) <= 1:
        return True
    else:
        return False
for i in range(n):
    for j in range(n):
        if not search(i, j):
            print('No')
            exit(0)
print('Yes')


### FIXED CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')
### BUGGY CODE ###

s = input()
t = input()

alphabet = 'abcdefghijklmnopqrstuvwxyz'
alphaset = set(s)
cache = []

def search(origin, c, offset):
    if c not in alphaset:
        return None
    offset = offset % len(origin)
    o = origin[offset:] + origin
    try:
        return o.index(c)
    except ValueError:
        return None

for i in range(len(s)):
    cache.append({c2: 0 for c2 in alphabet})
    for c2 in alphabet:
        offset2 = search(s, c2, i+1)
        if offset2 is None:
            cache[i][c2] = None
            continue
        cache[i][c2] = offset2 + 1

a = search(s, t[0], 0)
if a is None:
    print(-1)
    exit()

result = a
for i in range(1, len(t)):
    k = cache[result % len(s)][t[i]]
    if k is None:
        print(-1)
        exit()
    result += k

print(result+1)


### FIXED CODE ###

from bisect import bisect
s = input()
t = input()

alphabet = 'abcdefghijklmnopqrstuvwxyz'
char = {c: [] for c in alphabet}
for i, c in enumerate(s):
    char[c].append(i)

if len(char[t[0]]) == 0:
    print(-1)
    exit()

result = char[t[0]][0]

for c in t[1:]:
    if len(char[c]) == 0:
        print(-1)
        exit()
    idx = bisect(char[c], result % len(s))
    result = result - result % len(s)
    try:
        result += char[c][idx]
    except IndexError:
        result += len(s) + char[c][0]

print(result+1)
### BUGGY CODE ###

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

import bisect
import heapq

d = dict()
key_all = []
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    if a not in key_all:
        d[a] = [b]
        heapq.heappush(key_all, a)
    else:
        d[a].append(b)


ans = 0
l = []

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    # print(l)

    if l != []:
        ans += heapq.heappop(l) * -1

    # print(ans)

print(ans)


### FIXED CODE ###

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

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

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

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

ans_g =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        for k in range(10**8):
            if tmp <= l[j][1] + l[j][2] * k:
                tmp = l[j][1] + l[j][2] * k + l[j][0]
                break
            else:
                k += 1
    else:
        ans_g.append(tmp)

for ans in ans_g:
    print(ans)

print(0)

### FIXED CODE ###

n = int(input())

c, s, f = [], [], []
for _ in range(n-1):
    x,y,z = map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

anss =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        k = 0
        while 1:
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
            else:
                k += 1
    else:
        anss.append(tmp)
else:
    anss += [0]

for ans in anss:
    print(ans)
### BUGGY CODE ###

N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    cnt = 0
    while M >= X:
        if M % X == 0:
            M //= X
        elif M % X == 1:
            return True
        else:
            M -= X
        cnt += 1
        if cnt > 10000:
            return False
    return M == 1


A = divisor(N)
B = divisor(N - 1)

# N%K==1となるやつ
ans = len(B) - 1

for a in (A - B):
    if simu(N, a):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())


def divisor(M):
    div = set()
    for i in range(1, int(N ** 0.5 + 0.5) + 1):
        if M % i == 0:
            div.add(i)
            div.add(M // i)
    return div


def simu(M, X):
    cnt = 0
    while M >= X:
        if M % X == 0:
            M //= X
        elif M % X == 1:
            return True
        else:
            M -= X
        cnt += 1
        if cnt > 1000:
            return False
    return M == 1


A = divisor(N)
B = divisor(N - 1)

# N%K==1となるやつ
ans = len(B) - 1

for a in (A - B):
    if simu(N, a):
        ans += 1

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

from numpy import array
from numpy.linalg import solve

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

L=[]
for i in range(N-1):
	L.append ([0]*i+[1,1]+[0]*(N-i-2)) 

L.append([1]+[0]*(N-2)+[1])


a=array(L) 
b=array(A)       
L=solve(a,b) 

for ans in L:
	print (int(ans)*2, end=" ")


### FIXED CODE ###

import sys
from collections import deque

N=input()
A=map(int, sys.stdin.readline().split())
A=map(lambda x: x*2, A)

a=sum(A)/2

for i in range(1,N):
	if i%2==1:
		a-=A[i]

#a
print a,

prev=a
for x in A[:-1]:
	x-=prev
	print x,
	prev=x
### BUGGY CODE ###

H, W = map(int, input().split())
H += 2
W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + input() + '#'
grid += '#' * W

HL = [[0]*W for _ in range(H)]
WL = [[0]*H for _ in range(W)]

for i in range(H):
  temp = grid[W*i:W*(i+1)]
  left = 0
  right = 0
  for j in range(W):
    if temp[j] == "#":
      left = 0
    else:
      left += 1
      HL[i][j] += left
    if temp[-1-j] == "#":
      right = 0
    else:
      right += 1
      HL[i][-1-j] += right - 1

for j in range(W):
  temp = grid[j::W]
  left = 0
  right = 0
  for i in range(H):
    if temp[i] == "#":
      left = 0
    else:
      left += 1
      WL[j][i] += left
    if temp[-1-i] == "#":
      right = 0
    else:
      right += 1
      WL[j][-1-i] += right - 1

ans = 0

for i in range(H):
  for j in range(W):
    ans = max(ans, HL[i][j] + WL[j][i] - 1, 0)

print(ans)


### FIXED CODE ###

import copy

H, W = map(int, input().split())
grid = [[1 if c == "." else 0 for c in input()] for _ in range(H)]

L = copy.deepcopy(grid)
R = copy.deepcopy(grid)
U = copy.deepcopy(grid)
D = copy.deepcopy(grid)

for i in range(H):
  for j in range(1, W):
    L[i][j] = (L[i][j-1] + 1) * L[i][j]
    R[i][-1-j] = (R[i][-j] + 1) * R[i][-1-j]

for j in range(W):
  for i in range(1, H):
    U[i][j] = (U[i-1][j] + 1) * U[i][j]
    D[-1-i][j] = (D[-i][j] + 1) * D[-1-i][j]

ans = 0

for i in range(H):
  for j in range(W):
    ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3, 0)

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

N, K = map(int, input().split())
S = []

for _ in range(K):
  L, R = map(int, input().split())
  S.extend(range(L,R+1))
  
S.sort()

DP =[0]*N
DP[0] = 1

for i in range(N-1):
  if i + S[0] >= N:
    break
  if DP[i] == 0:
    pass
  else:
    for j in S:
      if i+j<N:
        DP[i+j] += DP[i]
      else:
        break

print(DP[-1]%998244353)

### FIXED CODE ###

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

L = []
R = []

for _ in range(K):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)
  
dp = [0]*(N+5)
dp[1] = 1

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    if i-L[j] >= 0:
      dp[i] += dp[i-L[j]]
    if i-R[j]-1 >= 0:
      dp[i] -= dp[i-R[j]-1]
    dp[i] %= 998244353
    
print((dp[N]-dp[N-1])%998244353)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
a.sort()
b = list(set(a))
cnt = 0
for i in range(len(b)):
  c = a.count(b[i])
  if b[i] <= c:
    cnt += c - b[i]
  else:
    cnt += c
print(cnt)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
b = list(set(a))
ans = 0
for i in range(len(b)):
  cnt = 1
  while len(a) > 1 and a[-1] == a[-2]:
    a.pop()
    cnt += 1
  c = a.pop()
  if c <= cnt:
    ans += cnt - c
  else:
    ans += cnt
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent,cnt):
    global MAX
    MAX = max(cnt,MAX)
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur,cnt)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1,cnt)
print(MAX)

            








### FIXED CODE ###

import sys
sys.setrecursionlimit(99999999)


[n,m]=list(map(int,input().split()))
friends=[]
for i in range(m):
    friends.append(list(map(int,input().split())))

tomodachi=[[]for i in range(n)]

for i in range(m):
    tomodachi[friends[i][0]-1].append(friends[i][1]-1)
    tomodachi[friends[i][1]-1].append(friends[i][0]-1)

for i in range(n):
    tomodachi[i]=list(set(tomodachi[i]))

namelist=[1 for i in range(n)]
teams=[]

def haba(x,kari,tomodachi,namelist):
    for i in range(len(tomodachi[x])):
        if namelist[tomodachi[x][i]]==1:#生き残っているなら
            kari.append(tomodachi[x][i])
            namelist[tomodachi[x][i]]=0#殺す
            haba(tomodachi[x][i],kari,tomodachi,namelist)
    return(kari)
            


for i in range(n):
    if namelist[i]==1:
        teams.append(list(set(haba(i,[i],tomodachi,namelist))))

saidai=0

for i in range(len(teams)):
    if saidai<len(teams[i]):
        saidai=len(teams[i])

ans=saidai

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

from collections import Counter
import bisect

def sortedexist(list,x):
    if bisect.bisect_left == bisect.bisect_right:
        return False
    else:
        return True

N = int(input())
A = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
dp = [False] * (max(A) + 1)
S = list(C.keys())
S.sort()
for a in S:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
    if C[a] > 1:
        dp[a] = True
print(sum([dp[a] == False for a in A ]))

### FIXED CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
s = [int(i) for i in input()]
a = {i for i in itertools.combinations(s, 3)}


print(len(a))

### FIXED CODE ###

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

l = [str(i).zfill(3) for i in range(0,1000)]

ct = 0
for i in l:
  n0 = s.find(i[0])
  if n0==-1:
    continue
  n1 = s.find(i[1], n0+1)
  if n1==-1:
    continue
  n2 = s.find(i[2], n1+1)
  if n2!=-1:
    ct += 1
   
print(ct)
### BUGGY CODE ###

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

    fac = [0] * (N + 1)
    fac[0] = 1
    for i in range(N):
        fac[i + 1] = fac[i] * (i + 1) % 998244353

    def mcomb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += M * mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    print(result)


main()


### FIXED CODE ###

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

result = 0
n = 1
k = 1
for i in range(K + 1):
    result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
    n *= N - 1 - i
    n %= 998244353
    k *= i + 1
    k %= 998244353
result *= M
result %= 998244353
print(result)
### BUGGY CODE ###

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

N,Q = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(Q)]

if N == 1:
    answer = [min(v,w) for v,w in VW]
else:
    answer = []
    for v,w in VW:
        while v != w:
            if v > w:
                v,w = w,v
            w = (w+N-2)//N
        answer.append(v)

print('\n'.join(map(str,answer)))

### FIXED CODE ###

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

import numpy as np

N,Q = map(int,input().split())
V,W = np.array([input().split() for _ in range(Q)],dtype=np.int64).T

if N == 1:
    answer = np.minimum(V,W)
else:
    for _ in range(50):
        V[V>W] = (V[V>W]+N-2)//N
        W[W>V] = (W[W>V]+N-2)//N
    answer = V

print('\n'.join(answer.astype(str)))
### BUGGY CODE ###

import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord("a")],A-1)
        #alphabet[o]=alphabet[o][:index]+[A-1]+alphabet[o][index:]
        #bisect.insort(alphabet[o],A-1)
        alphabet[ord(B)-ord("a")].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
s = list(input())
q = int(input())
query = [input() for _ in range(q)]

p = [[] for _ in range(26)]

for i, x in enumerate(s):
    p[ord(x) - ord('a')].append(i)

for x in query:
    a, b, c = x.split()
    #print(c)
    if a == '1':
        b = int(b) - 1
        if s[b] == c:
            continue
        d = ord(s[b]) - ord('a')
        e = ord(c) - ord('a')
        temp = bisect_left(p[d], b)
        p[d].pop(temp)
        temp = bisect_left(p[e], b)
        p[e].insert(temp, b)
        s[b] = c
    else:
        b = int(b) - 1
        c = int(c) - 1
        #print(b, c)
        ans = 0
        for i in range(26):
            L = bisect_left(p[i], b)
            if L >= len(p[i]):
                continue
            if p[i][L] <= c:
                ans += 1
        print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys


def merge(lst, left, mid, right):
    L = lst[left: mid]
    R = lst[mid: right]
    l_len = len(L)
    r_len = len(R)
    cnt = 0
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if l_len > i or r_len > j:
            if l_len <= i:
                lst[k] = R[j]
                j += 1
            elif r_len <= j:
                lst[k] = L[i]
                i += 1
            elif L[i] <= R[j]:
                lst[k] = L[i]
                i += 1
            else:
                lst[k] = R[j]
                j += 1
    return cnt


def mergeSort(lst, left, right):
    if left + 1 < right:
        mid = (left + right) >> 1
        cnt = mergeSort(lst, left, mid)
        cnt += mergeSort(lst, mid, right)
        return merge(lst, left, mid, right) + cnt
    else:
        return 0


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    data = [int(n) for n in lst[1]]
    cnt = mergeSort(data, 0, int(lst[0][0]))
    print(" ".join([str(n) for n in data]))
    print(cnt)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys


def merge(lst, left, mid, right):
    L = lst[left: mid]
    R = lst[mid: right]
    l_len = len(L)
    r_len = len(R)
    cnt = 0
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if l_len <= i:
            lst[k] = R[j]
            j += 1
        elif r_len <= j:
            lst[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            lst[k] = L[i]
            i += 1
        else:
            lst[k] = R[j]
            j += 1
    return cnt


def mergeSort(lst, left, right):
    if left + 1 < right:
        mid = (left + right) >> 1
        cnt = mergeSort(lst, left, mid)
        cnt += mergeSort(lst, mid, right)
        return merge(lst, left, mid, right) + cnt
    else:
        return 0


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    data = [int(n) for n in lst[1]]
    cnt = mergeSort(data, 0, int(lst[0][0]))
    print(" ".join([str(n) for n in data]))
    print(cnt)
### BUGGY CODE ###

S = input()
N = len(S)

map_ = [-1] * 2019
map_[0] = 0
ans = 0
now = 0
for i in range(0, N + 1):
    now += int(S[N - i - 1]) * (10**i)
    map_[now % 2019] += 1
    ans += map_[now % 2019]

print(ans)


### FIXED CODE ###

S = input()
N = len(S)

map_ = [-1] * 2019
map_[0] = 0
ans = 0
now = 0
for i in range(0, N):
    now = (now + int(S[N - i - 1]) * pow(10, i, 2019)) % 2019
    map_[now] += 1
    ans += map_[now]

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

from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]


# 塗らなければいけないマスの数
target_count = sum(l.count('.') for l in s)

queue = deque()

for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '#':
            queue.append((i, j))

while queue:
    # 先頭の値を取り出す
    h, w = queue.popleft()

    # 上下左右4マスに対し処理
    for i in range(4):

        # 移動距離
        dx, dy = dis_x[i], dis_y[i]

        # もし次のマスが通路かつ黒塗りが終わっていないなら
        if s[h+dy][w+dx] == '.' and target_count != 0:
            s[h+dy][w+dx] = '#'
            dist[h+dy][w+dx] = dist[h][w] + 1
            target_count -= 1

            queue.append((h+dy, w+dx))


print(max(max(l) for l in dist))

### FIXED CODE ###

from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

queue = deque()
for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '#':
            queue.append((i, j))

while queue:
    # 先頭の値を取り出す
    h, w = queue.popleft()

    # 上下左右4マスに対し処理
    for i in range(4):

        # 移動距離
        dx, dy = dis_x[i], dis_y[i]

        # もし次のマスの黒塗りが終わっていないなら
        if s[h+dy][w+dx] == '.':
            s[h+dy][w+dx] = '#'
            dist[h+dy][w+dx] = dist[h][w] + 1

            queue.append((h+dy, w+dx))


print(max(max(l) for l in dist))
### BUGGY CODE ###

from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []
color = [set() for _ in range(n)]
ans = dict()
for i in range(n-1):
    a,b = map(int,input().split())
    edge.append([a,b])
    tree[a-1].append(b)
    tree[b-1].append(a)

work_q = deque([])
visited = set()
work_q.append(1)
visited.add(1)
while work_q:
    here = work_q.popleft()
    for i in tree[here-1]:
        col = 1
        if i not in visited:
            work_q.append(i)
            visited.add(i)
            while col in color[here-1]:
                col += 1
            color[here-1].add(col)
            color[i-1].add(col)
            ans[(here-1,i-1)] = col
            col += 1

print(max(ans.values()))
for i in range(n-1):
    print(ans[edge[i][0]-1,edge[i][1]-1])


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

n = int(input())
edge = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int,input().split())
    edge[a].append((b, i))
    edge[b].append((a, i))
colors = 0
for i, line in enumerate(edge):
    colors = max(colors, len(line))
print(colors)
work_q = deque()
work_q.append((1, -1, -1))
color = [-1] * (n - 1)

while work_q:
    here, prev, col = work_q.popleft()
    cnt = 1
    for to, ind in edge[here]:
        if to == prev:
            continue
        if cnt == col:
            cnt += 1
        color[ind] = cnt
        work_q.append((to, here, cnt))
        cnt += 1
print(*color, sep="\n")
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 21:56:12 2020

@author: riichi
"""
import numpy as np

N = int(input())
A = list(map(int,input().split()))
a = np.array([],dtype = int)
b = np.array([],dtype = int)

A = np.array(A)
ans = 0
for i in range(N-1):
    a = np.append(a,1-A[i])
    a = a + 1
    
a = a-1

for i in range(N):
    b = np.append(b,A[i])
    b = b + 1

b = b - 1
a = np.sort(a)
b = np.sort(b)

for i in b:
    ans += np.count_nonzero(a==i)


print(ans)
    
    
    

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
ans = 0

L = [A[x]+x+1 for x in range(N)]
R = [x+1-A[x] for x in range(N)]

cL = collections.Counter(L)
cR = collections.Counter(R)

cRlist = list(cR.keys())

for i in range(len(cRlist)):
    tmp = cRlist[i]
    ans += cR.get(tmp,0) * cL.get(tmp,0)
    
print(ans)
### BUGGY CODE ###

N=int(input())
S = []
S_append = S.append
for i in range(N):
  data=input()
  if data not in S:
    S_append(data)
print(len(S))

### FIXED CODE ###

N = int(input())
S = list()
for i in range(N):
  x = input()
  S.append(x)
  
A = set(S)
print(len(A))