Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0:
            if g2:
                i = g2.pop()
            else:
                i = g1.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1):
        if n%3==1:
            i = g1.pop()
        elif n%3==2:
            i = g2.pop()
        else:
            if g1:
                i = g1.pop()
            else:
                i = g2.pop()
        ans[i] = n
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0:
            if g2:
                i = g2.pop()
            else:
                i = g1.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1,3):
        i = g1.pop()
        ans[i] = n
    for n in range(2,N+1,3):
        i = g2.pop()
        ans[i] = n
    for n in range(3,N+1,3):
        if g1:
            i = g1.pop()
        else:
            i = g2.pop()
        ans[i] = n
print(*ans)
N,K = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = 0
A = []
B = 0
C = [-1]*10000
for i in range(len(p)-K+1):
    P = p[i:i+K]
    if ans < sum(P):
        ans2 = P
    ans = max(ans,sum(ans2)) 
for j in range(len(ans2)):
  if C[ans2[j]] == -1:
      for k in range(1,ans2[j]+1):
          A.append(k)
      B += sum(A)/ans2[j]
      C[ans2[j]] = sum(A)/ans2[j]
      A.clear()
  else:
      B += C[ans2[j]]
print(B)

### FIXED CODE ###

from itertools import accumulate
N,K = list(map(int,input().split()))
P = list(map(int,input().split()))
for i in range(N):
    P[i] = 1+(P[i]-1)/2
ruiseki = list(accumulate([0]+P))
ans = 0
for i in range(N-K+1):
    ans = max(ans,ruiseki[i+K]-ruiseki[i])
print(ans)
a, b = map(int,input().split())
if a == 1:
    if b==1:
        print(b)
    else:
        print(b-2)
else:
    print((a-2) * (b-2))

### FIXED CODE ###

a = input()
b = input()
c = input()

print(a[0]+b[1]+c[2])
while True:
    H,W = map(int,input().split())
    
    if H == W == 0:
        break
    for i in range(H):
        if i % 2 == 0:
            print("#."*(W/2),sep="")
        else:
            print(".#"*(W/2),sep="")
    print("")


### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    if H == W == 0:
        break
    for i in range(H):
        print(('#.'*W)[i%2:][:W])
    print()
n = int(input())
ni = n%100
da = n//100

for a in range(ni):
    for b in range(ni):
        for c in range(ni):
            for d in range(ni):
                for e in range(ni):
                    if a + b*2 + c*3 + d*4 + e*5 == ni :
                        break
                else:
                    continue
                break
            else:
                continue
            break
        else:
            continue
        break
    else:
        continue
    break
if a+b+c+d+e <=da:
    print("1")
else:
    print("0")

### FIXED CODE ###

n = int(input())
ni = n%100
da = n//100

if n < 100:
    print("0")
elif ni == 0:
    print("1")
else:
    for a in range(ni):
        for b in range(ni):
            for c in range(ni):
                for d in range(ni):
                    for e in range(ni):
                        if a + b*2 + c*3 + d*4 + e*5 == ni :
                            break
                    else:
                        continue
                    break
                else:
                    continue
                break
            else:
                continue
            break
        else:
            continue
        break
    if a+b+c+d+e <=da:
        print("1")
    else:
        print("0")
import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in a:
    b_ = i//2
    b.append(b_)
count = 0
flag = True

while res % 2 != 0:
    res = a[0]/2
    count += 1
for i in a:
    if i % 2**count != 0:
        flag = False
        break
if flag:    
    lcm = b[0]
    for i in range(1, len(b)):
        lcm = lcm*b[i]//fractions.gcd(lcm,b[i])
    ans = m // lcm - (m//(lcm*2))
    print(ans)
else:
    print(0)

### FIXED CODE ###

import fractions
import sys
n, m = map(int, input().split())
a = list(map(int, input().split()))
lcm = a[0]
for i in range(1, len(a)):
    lcm = lcm*a[i]//fractions.gcd(lcm,a[i])
for i in a:
    if(lcm//i)%2 == 0:
        print(0)
        sys.exit()
lcm //= 2
print(m//lcm-(m//(lcm*2)))
i = list()
for x in range(2):
  i.append(map(int,input().split()))
return (i[0][0]-i[1][0])*(i[0][1]-i[1][1])

### FIXED CODE ###

i = list()
for x in range(2):
  i.append([int(x) for x in input().split()])
print((i[0][0]-i[1][0])*(i[0][1]-i[1][1]))
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0

for i in range(coin,N+1):
	for coin in coin_list:
    	if i-coin >= 0: dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

### FIXED CODE ###

INF = 10 ** 20

N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])
import sys
sys.setrecursionlimit(5000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [0] * (N+1)
def search(num, root, dis):
    for node in nodes[num]:
        if node[0] != root:
            idx = node[0]
            dis += node[1]%2
            if dis%2 != 0:
                ans[idx] = 1
            search(idx, num, dis)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
W = [list(map(int, input().split())) for _ in range(N-1)]
nodes = [[] for _ in range(N+1)]
for w in W:
    nodes[w[0]].append((w[1], w[2]))
    nodes[w[1]].append((w[0], w[2]))
ans = [-1] * (N+1)
ans[1] = 0
def search(num, root, dis):
    for node in nodes[num]:
        sum_d = dis
        if node[0] != root:
            idx = node[0]
            sum_d += node[1]%2
            if sum_d%2 != 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
            search(idx, num, sum_d)

search(1, 0, 0)
for answer in ans[1:]:
    print(answer)
def main()
	N = int(input())
  	if N%2 == 1:
      print((N+1)/2)
    else:
      print(N/2)
main()

### FIXED CODE ###

def main():
    N = int(input())
    if N%2 == 1:
      print(int((N+1)/2))
    else:
      print(int(N/2))
main()
a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)/gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm))

### FIXED CODE ###

a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))
import math
import random


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


def is_prime3(q, k=50):
    q = abs(q)
    # 計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False

    # n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    # 判定をk回繰り返す
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        # [0,s-1]の範囲すべてをチェック
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True


a, b = map(int, input().split())
gcd = math.gcd(a, b)
divisors = make_divisors(gcd)

ans = 1
for divisor in divisors:
    if is_prime3(divisor):
        ans += 1

print(str(ans))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)


# https://en.wikipedia.org/wiki/Trial_division
def f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
    # Only odd number is possible
    return a


c = gcd(A, B)

print(len(set(f(c))) + 1)
h, w = map(int, input().split())

s = [[i for i in list(str(input()))] for i in range(h)]

board_w = [[0 for i in range(w)] for i in range(h)]
board_h = [[0 for i in range(h)] for i in range(w)]

# 横、縦の順に走査
for i in range(h):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_w[i][j-k] = cnt_continue
            cnt_continue = 0
    for k in range(cnt_continue):
        board_w[i][w-1-k] = cnt_continue
    cnt_continue = 0

s = list(map(list, zip(*s)))

for i in range(w):
    cnt_continue = 0
    for j, c in enumerate(s[i]):
        if c == ".":
            cnt_continue += 1
        elif cnt_continue > 0:
            for k in range(1, cnt_continue+1):
                board_h[i][j-k] = cnt_continue
            cnt_continue = 0
    for k in range(cnt_continue):
        board_h[i][w-1-k] = cnt_continue
    cnt_continue = 0

board_h = list(map(list, zip(*board_h)))
ans = 0

for i in range(h):
    for j in range(w):
        v = int(board_w[i][j]) + int(board_h[i][j])
        ans = max(ans, v)

print(ans-1)


### FIXED CODE ###

h, w = map(int, input().split())

s = [input() for i in range(h)]

board_w = [[0 for _ in range(w)] for _ in range(h)]
board_h = [[0 for _ in range(w)] for _ in range(h)]

# 右、左、上、下の順に走査
for i in range(h):
    cnt_continue = 0
    for j in range(w):
        if s[i][j] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_w[i][j] = cnt_continue

    for j in reversed(range(w-1)):
        if board_w[i][j] == 0:
            continue
        board_w[i][j] = max(board_w[i][j], board_w[i][j+1])

for i in range(w):
    cnt_continue = 0
    for j in range(h):
        if s[j][i] == "#":
            cnt_continue = 0
        else:
            cnt_continue += 1
            board_h[j][i] = cnt_continue

    for j in reversed(range(h-1)):
        if board_h[j][i] == 0:
            continue
        board_h[j][i] = max(board_h[j][i], board_h[j+1][i])


ans = 0

for i in range(h):
    for j in range(w):
        v = board_w[i][j] + board_h[i][j] - 1
        ans = max(ans, v)

print(ans)
A, B = map(int, input().strip())

print(max(A+B,A-B,A*B))

### FIXED CODE ###

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

print(max(A+B,A-B,A*B))
n = int(input())
if n[-1] in [1, 4, 5, 7, 9] :
	print("hon")
elif n[-1] in [0, 1, 6, 8]:
  print("pon")
else:
  print("bon")
  

### FIXED CODE ###

n = input()
if int(n[len(n)-1]) in [2, 4, 5, 7, 9] :
	print("hon")
elif int(n[len(n)-1]) in [0, 1, 6, 8]:
  print("pon")
else:
  print("bon")
211 5
31 41 59 26 53

### FIXED CODE ###

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

if sum(A) >= h:
    print('Yes')
else:
    print('No')
a = input()
b = input()
c = input()
Sa = [a[i] for i in range(a)]
Sb = [b[i] for i in range(b)]
Sc = [c[i] for i in range(c)]
turn = "a"
while True:
  if turn == "a":
    if len(Sa) == 0:
      print("A")
      break
    else:
      turn = Sa.pop(0)
  elif turn == "b":
    if len(Sb) == 0:
      print("B")
      break
    else:
      turn = Sb.pop(0)
  else:
    if len(Sc) == 0:
      print("C")
      break
    else:
      turn = Sc.pop(0)

### FIXED CODE ###

a = input()
b = input()
c = input()
Sa = [a[i] for i in range(len(a))]
Sb = [b[i] for i in range(len(b))]
Sc = [c[i] for i in range(len(c))]
turn = "a"
while True:
  if turn == "a":
    if len(Sa) == 0:
      print("A")
      break
    else:
      turn = Sa.pop(0)
  elif turn == "b":
    if len(Sb) == 0:
      print("B")
      break
    else:
      turn = Sb.pop(0)
  else:
    if len(Sc) == 0:
      print("C")
      break
    else:
      turn = Sc.pop(0)
N = int(input())

score = len(str(N))

i = 2
while i ** 2 < N:
    a, b = divmod(N, i)
    if b == 0:
        score = len(str(a))
	"""
        if score == len(str(i)):
            break
        i = max(N // (10 ** (score - 1)), i+1)
    """
	i += 1
print(score)


### FIXED CODE ###

N = int(input())

score = len(str(N))

i = 2
while i ** 2 <= N:
    a, b = divmod(N, i)
    if b == 0:
        score = min(score, len(str(a)))
    i += 1
print(score)
import numpy as np


def calDistance_dfs(aList, d, node):
    for v in aList[node]:
        if d[v[0]] != -1:
            continue
        else:
            d[v[0]] = d[node] + v[1]
            calDistance_dfs(aList, d, v[0])


n = int(input())
adjacencyList = [[] for i in range(n)]
d = [-1] * n

for i in range(n - 1):
    s = list(map(int, input().split()))
    adjacencyList[s[0] - 1].append((s[1] - 1, s[2]))
    adjacencyList[s[1] - 1].append((s[0] - 1, s[2]))


d[0] = 0
calDistance_dfs(adjacencyList, d, 0)
for i in d:
    print(i % 2)


### FIXED CODE ###

import numpy as np


def calDistance_dfs(aList, d, node):
    stack = [node]
    d[node] = 0
    while len(stack) != 0:
        current = stack.pop()
        for v in aList[current]:
            if d[v[0]] == -1:
                stack.append(v[0])
                d[v[0]] = d[current]+v[1]


n = int(input())
adjacencyList = [[] for i in range(n)]
d = [-1] * n

for i in range(n - 1):
    s = list(map(int, input().split()))
    adjacencyList[s[0] - 1].append((s[1] - 1, s[2]))
    adjacencyList[s[1] - 1].append((s[0] - 1, s[2]))


d[0] = 0
calDistance_dfs(adjacencyList, d, 0)
for i in d:
    print(i % 2)
S=str(input())
print(S[0:3],end='')
print(8,end='')
print(S[4:],end='')

### FIXED CODE ###

S=str(input())
print(S[0:3],end='')
print(8,end='')
print(S[4:],end='')
while True:
    M, N = map(int, raw_input().split())
    if M == N == 0: break
    m = [i for i in range(1, M+1)]
    index = 0
    num = 1
    for i in range(N):
        line = raw_input()
        if num % 15 == 0:
            if line != 'FizzBuzz':
                del m[index]
        elif num % 3 == 0:
            if line != 'Fizz':
                del m[index]
        elif num % 5 == 0:
            if line != 'Buzz':
                del m[index]
        else:
            if not line.isdigit():
                del m[index]
            else:
                if int(line) != num:
                    del m[index]
        if len(m) == 1:
            break
        elif index+1 >= len(m):
            index = 0
        else:
            index += 1
        num += 1
    else:
        print ' '.join(map(str, m))

### FIXED CODE ###

while True:
    M, N = map(int, raw_input().split())
    if M == N == 0: break
    m = [i for i in range(1, M+1)]
    index = 0
    num = 1
    for i in range(N):
        if len(m) != 1:
            line = raw_input()
            flag = False
            if num % 15 == 0:
                if line != 'FizzBuzz':
                    del m[index]
                    flag = True
            elif num % 3 == 0:
                if line != 'Fizz':
                    del m[index]
                    flag = True
            elif num % 5 == 0:
                if line != 'Buzz':
                    del m[index]
                    flag = True
            else:
                if not line.isdigit():
                    del m[index]
                    flag = True
                else:
                    if int(line) != num:
                        del m[index]
                        flag = True
            if not flag:
                index += 1
            if index+1 > len(m):
                index = 0
            num += 1
        else:
            raw_input()
    else:
        print ' '.join(map(str, m))
s=input()
s[0]='2'
s[1]='0'
s[2]='1'
s[3]='8'
print(s)

### FIXED CODE ###

s=input()
r=s[4:]
print("2018%s"%(r))
S, T = list(input().split())
if T[:-1]==S:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()
T = input()

if T[:-1]==S and len(T)==len(S)+1:
	print("Yes")
else:
	print("No")
import sys
import  math
import fractions
from collections import defaultdict
import numpy as np
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()

imos_l=[0]*(N+1)

for i in range(K):    
    imos_l=[0]*(N+1)
    for j in range(len(A)): 
        imos_l[max(j-A[j],0)]+=1
        imos_l[min(j+A[j]+1,N)]-=1
    for j in range(len(imos_l)-1):
        imos_l[j+1]=imos_l[j]+imos_l[j+1]
    for j in range(len(A)):
        A[j]=imos_l[j]
    flag=True
    for j in range(len(A)):
        if(A[j]<N):
            flag=False
    if(flag):
        print(*A)
        sys.exit(0)

print(*A)
            
        



### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()

imos_l=[0]*(N+1)

for i in range(K):    
    imos_l=[0]*(N+1)
    for j in range(len(A)): 
        imos_l[max(j-A[j],0)]+=1
        imos_l[min(j+A[j]+1,N)]-=1
    for j in range(len(imos_l)-1):
        imos_l[j+1]=imos_l[j]+imos_l[j+1]
    for j in range(len(A)):
        A[j]=imos_l[j]
    flag=True
    for j in range(len(A)):
        if(A[j]<N):
            flag=False
    if(flag):
        print(*A)
        sys.exit(0)

print(*A)
lines = map(int, input().split())
lines.sort()

print(lines[0] * lines[1])

### FIXED CODE ###

lines = list(map(int, input().split()))
lines.sort()
 
print((lines[0] * lines[1]) // 2)
S = int(input())
h = int(S / 3600)
m = int((S % 3600) / 60)
s = S-3600*h-60*m
print(str(h)+":"+str(m)+":"str(s))

### FIXED CODE ###

S = int(input())
h = S//3600
m = (S % 3600) // 60
s = S-3600*h-60*m
print(str(h)+":"+str(m)+":"+str(s))
n = int(input())
A = [int(input()) for i in range(n)] 

counter = [0]*1000000000
cnt = 0
for a in A:
    counter[a-1] += 1
for c in counter:
    if c % 2 == 0 & c != 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

b = set()
lenB = 0
for a in A:
    b.add(a)
    lenB += 1
    if len(b) != lenB:
        b.remove(a)
        lenB -= 2
print(len(b))
n=int(input())
h=list(map(int,input().split()))
cnt=0
for i in range(n-1):
    if h[i]>=h[i+1]:
    a+=1
    else:
        a=0
    cnt=max(cnt,a)
print(cnt)

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
cnt=0
a=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        a+=1
    else:
        a=0
    cnt=max(cnt,a)
print(cnt)
from collections import deque

s = list(input())
q = int(input())

count = 0
l = []
for i in range(q):
	tmp = list(map(str,input().split()))
	if len(tmp) == 1:
		count += 1
		for j in range(len(l)):
			l[j][0] += 1
	elif tmp[1] == '1':
		l.append([1, tmp[2]])
	elif tmp[1] == '2':
		l.append([2, tmp[2]])

for i in range(len(l)):
	l[i][0] %= 2

if count % 2 == 1:
	s = s[::-1]
s = deque(s)

for i in range(len(l)):
	if l[i][0] == 0:
		s.append(l[i][1])
	else:
		s.appendleft(l[i][1])
print("".join(s))


### FIXED CODE ###

s = list(input())

if 'A' not in s or 'B' not in s:
    print('No')
else:
    print('Yes')
N, As = int(input()), list(map(int, input().split()))
maxA, ans = max(As), 1
while True:
    if pow(ans, maxA) - 1 > N:
        break
    ans += 1
print(ans)

### FIXED CODE ###

ans, w_idx = 0, 0
for i, s in enumerate(input()):
    if s != 'W':
        continue
    ans += i - w_idx
    w_idx += 1
print(ans)
S = input()
T = input()

lengt = len(S)
lst = []

for i in range(length):
    lst.append(S[i: length]+S[0: i])
    
if T in lst:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()

length = len(S)
lst = []

for i in range(length):
    lst.append(S[i: length]+S[0: i])
    
if T in lst:
    print('Yes')
else:
    print('No')
import networkx as nx
from networkx.algorithms.flow import dinitz

n, m = map(int, input().split())

def inside(x, y):
	if 0 <= x < n and 0 <= y < m:
		return True
	else:
		return False

DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]

a = [list(input()) for _ in range(n)]
S, T = n*m, n*m+1
g = nx.DiGraph()
for i in range(n):
	for j in range(m):
		if a[i][j] == "#":
			continue
		if (i+j)%2:
			g.add_edge(i*m+j, T, capacity=1)
		else:
			g.add_edge(S, i*m+j, capacity=1)
			for k in range(4):
				di, dj = i+DI[k], j+DJ[k]
				if inside(di, dj) and a[di][dj] == ".":
					g.add_edge(i*m+j, di*m+dj, capacity=1)
r = dinitz(g, S, T)
print(r.graph["flow_value"])
#print(*r.edges)
for e in r.edges:
	fr, to = e
	#print(fr, to)
	if fr == S or to == T or r[fr][to]["flow"] < 1:
		continue
	i0, j0 = fr//m, fr%m
	i1, j1 = to//m, to%m
	if i1 == i0+1:
		a[i0][j0] = "v"
		a[i1][j1] = "^"
	elif i1 == i0-1:
		a[i0][j0] = "^"
		a[i1][j1] = "v"
	elif j1 == j0+1:
		a[i0][j0] = ">"
		a[i1][j1] = "<"
	else:
		a[i0][j0] = "<"
		a[i1][j1] = ">"
print(*["".join(x) for x in a], sep="\n")

### FIXED CODE ###

import networkx as nx
from networkx.algorithms.bipartite import hopcroft_karp_matching

n, m = map(int, input().split())

def inside(x, y):
	if 0 <= x < n and 0 <= y < m:
		return True
	else:
		return False

DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]

a = [list(input()) for _ in range(n)]
g = nx.Graph()
g.add_nodes_from(range(n*m))
zero = True
top = set()
for i in range(n):
	for j in range(m):
		if a[i][j] == "#":
			continue
		if (i+j)%2 == 0:
			for k in range(4):
				di, dj = i+DI[k], j+DJ[k]
				if inside(di, dj) and a[di][dj] == ".":
					zero = False
					g.add_edge(i*m+j, di*m+dj)
					top.add(i*m+j)
if zero:
	print(0)
else:
	h = hopcroft_karp_matching(g, top_nodes=top)
	print(len(h)//2)
	for fr, to in h.items():
		i0, j0 = fr//m, fr%m
		i1, j1 = to//m, to%m
		if a[i0][j0] != ".":
			continue
		if i1 == i0+1:
			a[i0][j0] = "v"
			a[i1][j1] = "^"
		elif i1 == i0-1:
			a[i0][j0] = "^"
			a[i1][j1] = "v"
		elif j1 == j0+1:
			a[i0][j0] = ">"
			a[i1][j1] = "<"
		else:
			a[i0][j0] = "<"
			a[i1][j1] = ">"
print(*["".join(x) for x in a], sep="\n")
ret = ''
for a in input():
  if a = '1':
    ret += '9'
  elif a = '9':
    ret += '1'
  else:
    ret += a
print(ret)

### FIXED CODE ###

print(((input().replace("1","d")).replace("9","1")).replace("d","9"))
s = list(set(list(input())))
a = list("abcdefghijklmnopqrstuvwxyz")
for c in s:
  a.remove(c)
print(a[0])


### FIXED CODE ###

s = list(set(list(input())))
a = list("abcdefghijklmnopqrstuvwxyz")
for c in s:
  a.remove(c)
print(a[0]) if len(a)>0 else print("None")