Harryxun/stf_run huggingface dataset:
# coding: utf-8
# Your code here!

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

ab_list.sort()

graph = [[] for i in range(N)]
for i in range(N-1):
    graph[ab_list[i][0]-1].append((ab_list[i][1],i))
    graph[ab_list[i][1]-1].append((ab_list[i][0],i))
    
ans = [0 for i in range(N-1)]
ten_col = [[] for i in range(N)]
def dfs(start,now,color):
    ten_col[now-1].append(color)
    for (future,i) in graph[now-1]:
        if future == start:
            pass
        else:
            new_col = 1
            while True:
                if new_col not in ten_col[now-1]:
                    ten_col[now-1].append(new_col)
                    ten_col[future-1].append(new_col)
                    ans[i] = new_col
                    break
                else:
                    new_col += 1
            dfs(now,future,new_col)
            
dfs(-1,1,0)
print(max(ans))
for i in ans:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b,i))
    graph[b-1].append((a,i))
    
ans = [0]*(N-1)

def dfs(past,now,edge_col):
    new_col = 1
    for (future,i) in graph[now-1]:
        if future == past:
            pass
        else:
            if new_col == edge_col:
                new_col += 1
            ans[i] = new_col
            dfs(now,future,new_col)
            new_col += 1
            
dfs(-1,1,-1)

print(max(ans))
for i in ans:
    print(i)
a=input()
s=input()
print(s if a>=3200 else "red")

### FIXED CODE ###

a=int(input())
s=input()
if a >= 3200:
  print(s)
else:
  print("red")
N = int(input())
H = list(map(int,input().split()))
a = "Yes"

for i in range(N-1):
  if H[i]<H[i+1]:
    pass
  else:
    H[i]-=1

for i in range(N-1):
  if H[i]>H[i+1]:
    a = "No"

print(a)


### FIXED CODE ###

A,B,C = list(map(int,input().split()))
print(max(C-A+B,0))
A_1=int(input())
A_2=int(input())
A_3=int(input())
if A_1+A_2+A_3>=22:
    print("bust")
if A_1+A_2+A_3<=21:
    print("bust")

### FIXED CODE ###

A_1,A_2,A_3=map(int,input().split())
if A_1+A_2+A_3>=22:
    print("bust")
if A_1+A_2+A_3<=21:
    print("win")
import math 
a,b=map(int,input().split()) 
print(a*b/math.gcd(a,b))  

### FIXED CODE ###

import fractions  
a,b=map(int,input().split())  
print(a*b//fractions.gcd(a,b))
a=imput()
a[3]='8'
print(a)

### FIXED CODE ###

a=input()
print(a.replace('2017/','2018/'))
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcm(a, b):
  if a > b:
    a, b = b, a
  while True:
    a, b = b%a, a
    if a == 0:
      return b

def gcm(a, b):
  return int(a * b / lcm(a, b))


def main():
  n, m = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  x = 1
  for i in range(len(As)):
    x = gcm(x, As[i])
  if sum([(x//A)%2 == 1 for A in As]) == len(As):
    print(int(m/x-0.5)+1)
  else:
    print(0)

if __name__=='__main__':
  main()

### FIXED CODE ###

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

def gcd(a, b):
  if a > b:
    a, b = b, a
  while True:
    a, b = b%a, a
    if a == 0:
      return b

def lcm(a, b):
  return int(a * b // gcd(a, b))


def main():
  n, m = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  x = 1
  for i in range(len(As)):
    x = lcm(x, As[i])
    if m/x < 0.5:
      print(0)
      return
  if sum([(x//A)%2 == 1 for A in As]) == len(As):
    print(int(m/x-0.5+1))
  else:
    print(0)

if __name__=='__main__':
  main()
N = int(input())
li = list(map(int, input().split()))
ans = dict()
for i in range(len(li)):
    ans[li[i]] = i + 1
ali = []
for j in sorted(ans.keys()):
    ali.append(ans[j])
print(*join(ali))

### FIXED CODE ###

N = int(input())
S = list(input())
li = list()
for i in range(N):
    if i < N-1:
        if S[i] != S[i+1]:
            li.append(S[i])
    else:
        li.append(S[i])
print(len(li))
a = map(int,raw_input().split())
a.sort()
print a[0] a[1] a[3]

### FIXED CODE ###

a, b, c = map(int,raw_input().split())
str = [a, b, c]
str.sort()
print str[0], str[1] , str[2]
import itertools as itl

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

for mi in M:
    flg = False
    for i in range(len(A)):
        C = itl.combinations_with_replacemant(A, i)
        for j in C:
            if sum(j) == mi:
                flg = True
                break
    if flg: print("yes")
    else: print("no")


### FIXED CODE ###

import itertools as itl

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
S = []

for i in range(n):
    cmb = list(itl.combinations(A, i+1))
    for j in cmb:
        S.append(sum(j))

for m in M:
    flg = False
    for s in S:
        if s == m:
            flg = True
            break
    if flg:
        print("yes")
    else:
        print("no")
r = int(input())
import math
S = "%.6f"%(r ** 2 * math.pi)
L = "%.6f"%(2 * r * math.pi)
print(str(S) + " " + str(L))



### FIXED CODE ###

r = float(input())
import math
S = "%.6f"%(r ** 2 * math.pi)
L = "%.6f"%(2 * r * math.pi)
print(str(S) + " " + str(L))
a = input()
a[5] = " "
a[13] = " "
print(a[0]+a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10]+a[11]+a[12]+a[13]+a[14]+a[15]+a[16]+a[17]+a[18])

### FIXED CODE ###

a = input()
A =a[0]+a[1]+a[2]+a[3]+a[4]
B =a[6]+a[7]+a[8]+a[9]+a[10]+a[11]+a[12]
C =a[14]+a[15]+a[16]+a[17]+a[18]
print(A,B,C)
n = input()
nStr = input().split()
number = list(map(int,nStr))
 
frby = 1
twby = -1
 
for i in number:
    if i % 4 == 0:
        frby += 2
    elif i % 2 == 0:
        twby += 1
        
if int(n) == 1 and frby == 3:
    print("Yes")
elif int(n) == (twby + 1):
    print("Yes")
elif int(n) <= (frby):
    print("Yes")
elif int(n) <= (frby + twby):
    print("Yes")
else :
    print("No")


### FIXED CODE ###

n = input().split()
print((int(n[0])-1 )* ( int(n[1])-1))
import itertools
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in itertools.combinations(arr, 3):
  if i[0]+i[1] > i[3] and i[0]+i[3] > i[1] and i[3]+i[1] > i[0]:
    count += 1
print(count)
    
  


### FIXED CODE ###

import itertools

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in itertools.combinations(arr, 3):
    if i[0] + i[1] > i[2] and i[0] + i[2] > i[1] and i[2] + i[1] > i[0] and i[0] != i[1] != i[2]:
        count += 1
print(count)
n = int(input())
a = list(map(int, input().split()))
result = 1
checker =False
for j in a:
  if j > 1000000000000000000:
    result = -1
    checker =True
if 0 in a:
  result = 0
  checker=True
import numpy as np
while checker==False:
  #import numpy as np
  a = np.array(a)
  result = int(a.prod())
  checker = True
    

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)


### FIXED CODE ###

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

print(a*b)
n,m=map(int,input().split())
print("Yes" if n=m else "No")


### FIXED CODE ###

n,m=map(int,input().split())
print("Yes" if n==m else "No")
import copy
N = int(input())
word = [input() for i in range(N)]
sorted_word = [sorted(list(word[i])) for i in range(N)]
copy_word = copy.copy(sorted_word)
count = 0
for i in range(N-1):
  copy_word.remove(sorted_word[i])
  if sorted_word[i] in copy_word
    count += 1
print(count)



### FIXED CODE ###

N = int(input())
ans = 0
dict_word = {}
for i in range(N):
  sorted_word = str(''.join(sorted(list(input()))))
  try:
    ans += dict_word[sorted_word]
    dict_word[sorted_word] += 1
  except:
    dict_word[sorted_word] = 1
print(ans)
X,Y,A,B,C=list(map(int,input().split()))
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
eat=[]
eat.extend(p[:X])
eat.extend(q[:Y])
eat.sort(reverse=True)
i=0
result=0
for v in eat:
  if v<r[i]:
    result+=r[i]
    i+=1
  else:
    result+=v
print(result)

### FIXED CODE ###

X,Y,A,B,C=list(map(int,input().split()))
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
eat=[]
eat.extend(p[:X])
eat.extend(q[:Y])
eat.sort(reverse=True)
i=0
j=0
result=0
for v in eat:
  if i<C and eat[j]<r[i]:
    result+=r[i]
    i+=1
  else:
    result+=eat[j]
    j+=1
  if i+j==X+Y:
    break
print(result)
# -*- coding: utf-8 -*-

N,W = map(int, input().split())
wN = []
vN = []
for i in range(N):
    w,v = map(int, input().split())
    wN.append(w)
    vN.append(v)

dp = [[0] * (3*(N-1)+1)+100 for i in range(N+1)]

# 答えが明らかな範囲はDPに含めない
if W < wN[0]:
    print(0)
    exit()
elif W >= sum(wN):
    print(sum(vN))
    exit()

# wNの範囲はかなり限定されているので、オフセットを用意
# (-1するのは0地点を残すため)
offset = wN[0]-1
W -= offset

for i in range(N):
    for j in range(offset, (3*(N-1)+1)+100 + offset):

        if wN[i] <= j:
            # max(0,～)で0未満を探しに行くのを避ける
            dp[i+1][j-offset] = max(dp[i][max(0,j-wN[i]-offset)] + vN[i], dp[i][j-offset])
        else:
            dp[i+1][j-offset] = dp[i][j-offset]

print(dp[N][W])

### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
・メモ化再帰
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = map(int, input().split())
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = map(int, input().split())

# memo[i][j]: i番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値
memo = [defaultdict(lambda: -1) for i in range(N+1)]

def dfs(cur, wei):
    # 既に調べた場所はそのまま返却
    if memo[cur][wei] != -1:
        return memo[cur][wei]
    # 品物を最後まで見た
    if cur == N:
        res = 0
    # まだ余力があるから両方試す
    elif wei >= wN[cur]:
        res = max(dfs(cur+1, wei-wN[cur]) + vN[cur], dfs(cur+1, wei))
    # もうこの回の荷物は入らない
    else:
        res = dfs(cur+1, wei)
    # ここまでのベストな値をメモに記録してから返却
    memo[cur][wei] = res
    return res
# 0番目以降で容量W以下の場合の結果を表示
print(dfs(0, W))
import bisect

f_inf = float('inf')


def cal(syurui, d, index):
    if d == 'e':
        return syurui[index]
    elif d == 'w':
        return syurui[index - 1]


A, B, Q = map(int, input().split())
s = [int(input()) for i in range(A)]
s.sort()
t = [int(input()) for i in range(B)]
t.sort()

for i in range(Q):
    x = int(input())
    s_index = bisect.bisect_left(s, x)
    t_index = bisect.bisect_left(t, x)
    if s_index == len(s) and t_index == len(t):
        print(max(abs(x-s[s_index-1]), abs(x-t[t_index-1])))
    elif s_index == len(s):
        ｓ.insert(0, -f_inf)
        t.insert(0, -f_inf)
        print(min(max(abs(x-s[s_index]), abs(x-t[t_index])),
                  2*abs(x-s[s_index])+abs(x-t[t_index+1]), abs(x-s[s_index])+2*abs(x-t[t_index+1])))
    elif t_index == len(t):
        ｓ.insert(0, -f_inf)
        t.insert(0, -f_inf)
        print(min(max(abs(x-s[s_index]), abs(x-t[t_index])), 2*abs(x-s[s_index+1])+abs(x-t[t_index]),
                  abs(x-s[s_index+1])+2*abs(x-t[t_index])))
    else:
        ｓ.insert(0, -f_inf)
        t.insert(0, -f_inf)
        print(min(max(abs(x-s[s_index]), abs(x-t[t_index])), max(
            abs(x-s[s_index+1]), abs(x-t[t_index+1])), 2*abs(x-s[s_index+1])+abs(x-t[t_index]), 2*abs(x-s[s_index])+abs(x-t[t_index+1]), abs(x-s[s_index+1])+2*abs(x-t[t_index]), abs(x-s[s_index])+2*abs(x-t[t_index+1])))


### FIXED CODE ###

A,B = map(int,input().split())
# N = int(input())
if B%A == 0:
    print(A+B)
else:
    print(B-A)
s=list(input())
ans=0
for i in s:
  if i="-":
    ans=ans-1
  else:
    ans=ans+1
print(ans)

### FIXED CODE ###

s=list(input())
ans=0
for i in s:
  if i=="-":
    ans=ans-1
  else:
    ans=ans+1
print(ans)
n = int(input())n = int(input())
n = n + n**2 + n**3
print(n)

### FIXED CODE ###

n = int(input())
n = n + n**2 + n**3
print(int(n))
n = int(input())
x_s = input()
x = int(x_s, 2)

def popcount(n):
    return bin(n).count("1")

pops = popcount(x)
x_pop_p = x%(pops + 1)
try:
    x_pop_m = x%(pops - 1)
except:
    x_pop_m = 0
for i in reversed(range(0,n)):
    if x_s[i] == '1':
        tmp = (x_pop_m - pow(2,i,(pops - 1)))%(pops - 1)
    else:
        tmp = (x_pop_p + pow(2,i,(pops + 1))) % (pops + 1)
    if tmp == 0:
        print(1)
        continue
    cnt = 2
    tmp %= popcount(tmp)
    while tmp > 0:
        cnt += 1
        if tmp == 0:
            print(cnt-1)
            continue
        tmp %= popcount(tmp)
    print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
from collections import deque
n=int(raw_input())
que = deque()
for i in xrange(n):
    o = raw_input()
    if o == 'deleteFirst':
        del que[0]
    elif o == 'deleteLast':
        del que[-1]
    else:
        c,p = o.split()
        p = int(p)
        if c == 'insert':
            que.appendleft(p)
        elif c == 'delete':
            que.remove(p)
print ' '.join(map(str,que))

### FIXED CODE ###

from collections import deque
n=int(raw_input())
q = deque()
for i in xrange(n):
    o = raw_input()
    if o == 'deleteFirst':  q.popleft()
    elif o == 'deleteLast': q.pop()
    else:
        c,p = o.split(); p = int(p)
        if c == 'insert': q.appendleft(p)
        elif c == 'delete':
            try: q.remove(p)
            except: pass
print ' '.join(map(str,q))
A = int(input())
B = int(input())
C = int(input())
D = int(input())
while (A>0 and C>0):
    C = C - B
    if C <= 0:
        break
    A = A - D
print("Yes" if C<=0 else "NO")

### FIXED CODE ###

A, B, C, D = map(int, input().split())
while (A>0 and C > 0):
    C = C - B
    if C <= 0:
        break
    A = A - D
print("Yes" if C<=0 else "No")
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])


# 経路復元
p = {}
for i in range(N):
    for j in range(i+1, N):
        c = i
        while c != j:
            for k in range(N):
                if k != c and (g[c][k]+dp[k][j]) == dp[c][j]:
                    p[(c, k) if c < k else (k, c)] = 1
                    c = k
                    break
print(max([0, M-len(p)))


### FIXED CODE ###

import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]
ms = []
for i in range(N):
    dp[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
    ms.append([a-1, b-1, c])

g = copy.deepcopy(dp)

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])

# 全頂点でmが使われたかどうか
ans = M
for m in ms:
    a, b, c = m
    for n in range(N):
        if dp[n][b] == (dp[n][a]+c):
            ans -= 1
            break
print(ans)
s = input()
k = int(input())

for i in range(k + 1):
    if s[i] == '1':
        continue
    else:
        print(s[i])
        break
else:
    print(1)


### FIXED CODE ###

s = input()
k = int(input())

for i in range(k):
    if s[i] == '1':
        continue
    else:
        print(s[i])
        break
else:
    print(1)
N = input()
str = input()
new_str = ""

for x in str:
  temp = ord(x)+N
  if temp>90:
    str += chr((ord(x)+N) - 26)
  else:
    str += chr(ord(x)+N)

print(new_str)

### FIXED CODE ###

N = int(input())
str = input()
new_str = ''
 
for x in str:
  temp = ord(x)+N
  if temp>90:
    new_str += chr(temp - 26)
  else:
    new_str += chr(temp)
 
print(new_str)
#!/usr/bin/env python

s = input().strip()
k = input().strip()

if s[0] == '1':
    print(s[1])
else:
    print(s[0])


### FIXED CODE ###

#!/usr/bin/env python


def main():
    s = input().strip()
    k = int(input().strip())

    # 1桁目が、1以外のときは、1桁目を表示
    if s[0] != '1':
        print(s[0])
        return

    count_one = 0
    for c in s:
        if c == '1':
            count_one += 1
        else:
            break

    if k <= count_one:
        print(1)
    else:
        print(s[count_one])


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

li = []
temp = 10 ** 5
for i in range(N):
    t = int(T - (H[i] * 0.006))
    li.append(t)
    if abs(A - t) < temp:
        temp = abs(A-t)

if A < 0:
    idx = li.index(-(temp-A))
else:
    idx = li.index(temp+A)

print(idx+1)


### FIXED CODE ###

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

ans = []
for i in range(N):
    ans.append(abs(A - (T - H[i] * 0.006)))

print(ans.index(min(ans))+1)
from collections import Counter
n=int(input())
s=[input() for i in range(n)]
c=Counter(s)
t=[]
v=c.most_common()[0][1]
t.append(c.most_common()[0][0])
for i in range(1,n):
  a=c.most_common()[i][1]
  if v>a:
    break
  else:
    t.append(c.most_common()[i][0])
t.sort()
for i in t:
  print(i)

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[input() for i in range(n)]
c=Counter(s)
t=[]
u=c.most_common()
v=u[0][1]
t.append(u[0][0])
for i in range(1,len(c)):
  a=u[i][1]
  if v>a:
    break
  else:
    t.append(u[i][0])
t.sort()
for i in t:
  print(i)
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["#"] * (W+2)]
for _ in range(H):
    grid.append(["#"] + list(sys.stdin.readline().strip()) + ["#"])
grid.append(["#"] * (W+2))
# print(grid)

q = deque()
for j in range(1, H+1):
    for i in range(1, W+1):
        if grid[i][j] == "#":
            q.append((i, j, 0))

ans = 0
while q:
    x, y, count = q.popleft()
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[x+dx][y+dy] != ".":
            continue
        grid[x+dx][y+dy] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))

# print(grid)
print(ans)

### FIXED CODE ###

import sys
from pprint import pprint

from collections import deque

h, w = map(int, sys.stdin.readline().strip().split(" "))
field = []
for _ in range(h):
    field.append(list(sys.stdin.readline().strip()))

# pprint(field)

q = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            q.append((0, i, j))

while q:
    count, y, x = q.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if 0 <= y+dy < h and 0 <= x+dx < w:
            # print(y+dy, x+dx, field[y+dy][x+dx])
            if field[y+dy][x+dx] == "#":
                continue
            else:
                field[y+dy][x+dx] = "#"
                q.append((count+1, y+dy, x+dx))

# pprint(field)
print(count)
n=int(input())
s=input().split(' ')

flag=1
m=0

while flag:
　　　　flag=0
　　　　for j in range(1,n):
　　　　　　　　j=n-j
　　　　　　　　if s[j]<s[j-1]:
　　　　　　　　　　　　a=s[j]
　　　　　　　　　　　　s[j]=s[j-1]
　　　　　　　　　　　　s[j-1]=a
　　　　　　　　　　　　m+=1
　　　　　　　　　　　　flag=1
　　　　　　　　　　　　print(j)

print(' '.join(s))
print(m)


### FIXED CODE ###

n=int(input())
s=input().split(' ')

flag=1
m=0

while flag:
    flag=0
    for j in range(1,n):
        j=n-j
        if int(s[j])<int(s[j-1]):
            a=s[j]
            s[j]=s[j-1]
            s[j-1]=a
            m+=1
            flag=1

print(' '.join(s))
print(m)
from queue import Queue
INF = 20000000
q = Queue()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
smp = [[INF for i in range(1002)] for j in range(1002)]
mp = [['X' for i in range(1002)] for j in range(1002)]
ipt = input().split('\n')
H, W, n = map(int,ipt[0].split())
for i in range(1, H+1):
    for j in range(1, W+1):
        mp[i][j] = ipt[i][j-1];
x = y = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if mp[i][j]=='S':
            x = j; y = i;
c = 0; ans = 0;
q.put([x,y]); smp[y][x] = 0;
while c<n:
    p = q.get()
    x = p[0]; y = p[1];
    if mp[y][x]==chr(ord('1')+c):
        ans += smp[y][x]; c+=1;
        if c==n: break;
        while q.empty()==False: q.get()
        for i in range(1, H+1):
            for j in range(1, W+1):
                smp[i][j] = INF
        smp[y][x] = 0
    for i in range(4):
        if mp[y+dy[i]][x+dx[i]]!='X' and smp[y+dy[i]][x+dx[i]]==INF:
            q.put([x+dx[i], y+dy[i]]);
            smp[y+dy[i]][x+dx[i]] = smp[y][x]+1;
print(ans)

### FIXED CODE ###

from Queue import Queue
INF = 20000000
q = Queue()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
smp = [[INF for i in range(1002)] for j in range(1002)]
mp = [['X' for i in range(1002)] for j in range(1002)]
H, W, n = map(int,raw_input().split())
for i in range(1, H+1):
    ipt = raw_input()
    for j in range(1, W+1):
        mp[i][j] = ipt[j-1];
x = y = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if mp[i][j]=='S':
            x = j; y = i;
c = 0; ans = 0;
q.put([x,y]); smp[y][x] = 0;
while c<n:
    p = q.get()
    x = p[0]; y = p[1];
    if mp[y][x]==chr(ord('1')+c):
        ans += smp[y][x]; c+=1;
        if c==n: break;
        while q.empty()==False: q.get()
        for i in range(1, H+1):
            for j in range(1, W+1):
                smp[i][j] = INF
        smp[y][x] = 0
    for i in range(4):
        if mp[y+dy[i]][x+dx[i]]!='X' and smp[y+dy[i]][x+dx[i]]==INF:
            q.put([x+dx[i], y+dy[i]]);
            smp[y+dy[i]][x+dx[i]] = smp[y][x]+1;
print(ans)
H, W = map(int, input().split())

S = [input() for _ in range(H)]
p = [[0, 0, 0, 0]]
if S[0][0] == '#':
  p[3] = 1
for m in range(H+W-2):
  n = len(p)
  for i in range(n):
    x = p[i]
    if x[0] < H - 1:
      if x[3] == 1 and S[x[0]+1][x[1]] == '.':
        p.append([x[0]+1, x[1], x[2], 0])
      elif x[3] == 0 and S[x[0]+1][x[1]] == '#':
        p.append([x[0]+1, x[1], x[2]+1, 1])
      else:
        p.append([x[0]+1, x[1], x[2], x[3]])
    if x[1] < W - 1:
      if x[3] == 1 and S[x[0]][x[1]+1] == '.':
        p.append([x[0], x[1]+1, x[2], 0])
      elif x[3] == 0 and S[x[0]][x[1]+1] == '#':
        p.append([x[0], x[1]+1, x[2]+1, 1])
      else:
        p.append([x[0], x[1]+1, x[2], x[3]])
  p = p[n:]
print(min(p[i][2] for i in range(len(p))))

### FIXED CODE ###

H, W = map(int, input().split())

S = [input() for _ in range(H)]
X = [[[int(1e9), 0] for i in range(W)] for j in range(H)]
p = [[0, 0]]
if S[0][0] == '#':
  X[0][0][0], X[0][0][1] = 1, 1
else:
  X[0][0][0], X[0][0][1] = 0, 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      X[i][j][1] = 1
for m in range(H+W-2):
  n = len(p)
  for i in range(n):
    x = p[i][:]
    if x[0] < H - 1:
      p.append([x[0]+1, x[1]])
    if x[0] == 0 and x[1] < W - 1:
      p.append([x[0], x[1]+1])
  p = p[n:]
  n = len(p)
  for i in range(n):
    x = p[i][:]
    if x[0] > 0 and x[1] > 0:
      X[x[0]][x[1]][0] = min(X[x[0]-1][x[1]][0] + (1-X[x[0]-1][x[1]][1])*X[x[0]][x[1]][1], X[x[0]][x[1]-1][0] + (1-X[x[0]][x[1]-1][1])*X[x[0]][x[1]][1])
    elif x[0] == 0 and x[1] > 0:
      X[x[0]][x[1]][0] = X[x[0]][x[1]-1][0] + (1-X[x[0]][x[1]-1][1])*X[x[0]][x[1]][1]
    elif x[0] > 0 and x[1] == 0:
      X[x[0]][x[1]][0] = X[x[0]-1][x[1]][0] + (1-X[x[0]-1][x[1]][1])*X[x[0]][x[1]][1]
print(X[H-1][W-1][0])