Problem p02561 (python)

Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap, reverse=True):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        cap2 = cap if reverse else 0
        self.graph[to].append([fr, cap2, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[s] = 0
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)


def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*m+j+1, 1, reverse=False)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            flow.add_edge(i*m+j+1, ni*m+nj+1, 1, reverse=False)
                else:
                    flow.add_edge(i*m+j+1, end, 1, reverse=False)
    
    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(m)] for i in range(n)]

    flow_list = dict()
    for i, g in enumerate(flow.graph):
        for node in g:
            fr, to = i, node[0]
            if fr == start or to == end or to == start or fr == end:
                continue
            fr -= 1
            to -= 1
            xi, xj = divmod(fr, m)
            if (xi + xj) % 2 == 0:
                continue
            if node[1] == 0:
                if fr > to:
                    fr, to = to, fr
                flow_list[fr] = to
    
    for k, v in flow_list.items():
        if v-k == m:
            ans[k//m][k%m] = "v"
            ans[v//m][v%m] = "^"
        else:
            ans[k//m][k%m] = ">"
            ans[v//m][v%m] = "<"

    for a in ans:
        print("".join(a))

    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap, reverse=True):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        cap2 = cap if reverse else 0
        self.graph[to].append([fr, cap2, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[s] = 0
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)
def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*m+j+1, 1, reverse=False)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            p, q = min(i*m+j+1, ni*m+nj+1), max(i*m+j+1, ni*m+nj+1)
                            flow.add_edge(p, q, 1, reverse=False)
                else:
                    flow.add_edge(i*m+j+1, end, 1, reverse=False)
    

    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]

    flow_list = []
    for i, g in enumerate(flow.graph):
        for node in g:
            fr, to = i, node[0]
            if fr > to:
                continue
            if fr == start or to == end:
                continue
            cap = node[1]
            if cap == 0:
                flow_list.append((fr-1, to-1))
            
    for k, v in flow_list:
        if v-k == m:
            ans[k//m][k%m] = "v"
            ans[v//m][v%m] = "^"
        else:
            ans[k//m][k%m] = ">"
            ans[v//m][v%m] = "<"

    for a in ans:
        print("".join(a))


    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap, reverse=True):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        cap2 = cap if reverse else 0
        self.graph[to].append([fr, cap2, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[s] = 0
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)
def main():
    
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*m+j+1, 1, reverse=False)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            p, q = min(i*m+j+1, ni*m+nj+1), max(i*m+j+1, ni*m+nj+1)
                            flow.add_edge(p, q, 1, reverse=False)
                else:
                    flow.add_edge(i*m+j+1, end, 1, reverse=False)
    

    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]
    try:
        flow_list = []
        for i, g in enumerate(flow.graph):
            for node in g:
                fr, to = i, node[0]
                if fr > to:
                    continue
                if fr == start or to == end:
                    continue
                cap = node[1]
                if cap == 0:
                    flow_list.append((fr-1, to-1))
                
        for k, v in flow_list:
            if v-k == m:
                ans[k//m][k%m] = "v"
                ans[v//m][v%m] = "^"
            else:
                ans[k//m][k%m] = ">"
                ans[v//m][v%m] = "<"

        for a in ans:
            print("".join(a))
    finally:
        return 

    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap, reverse=True):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        cap2 = cap if reverse else 0
        self.graph[to].append([fr, cap2, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[s] = 0
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = self.dfs(s, t, self.inf)
            while f:
                flow += f
                f = self.dfs(s, t, self.inf)
def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*m+j+1, 1, reverse=False)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            p, q = min(i*m+j+1, ni*m+nj+1), max(i*m+j+1, ni*m+nj+1)
                            flow.add_edge(p, q, 1, reverse=False)
                else:
                    flow.add_edge(i*m+j+1, end, 1, reverse=False)
    

    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]

    flow_list = []
    for i, g in enumerate(flow.graph):
        for node in g:
            fr, to = i, node[0]
            if fr == start or fr == end or to == start or to == end:
                continue
            if fr > to:
                continue
            cap = node[1]
            if cap == 0:
                flow_list.append((fr-1, to-1))
            
    for k, v in flow_list:
        if m > 1 and v-k == 1:
            ans[k//m][k%m] = ">"
            ans[v//m][v%m] = "<"
        else:
            ans[k//m][k%m] = "v"
            ans[v//m][v%m] = "^"


    for a in ans:
        print("".join(a))


    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, cap, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[0] = s
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = 1
            while f:
                f = self.dfs(s, t, self.inf)
                if f == 0:
                    break
                flow += f


def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*m+j+1, 1)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            flow.add_edge(i*m+j+1, ni*m+nj+1, 1)
                else:
                    flow.add_edge(i*m+j+1, end, 1)
    

    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]

    flow_list = dict()
    for i, g in enumerate(flow.graph):
        for node in g:
            fr, to = i, node[0]
            if fr == start or fr == end or to == start or to == end:
                continue
            cap = node[1]
            if cap != 1:
                fr, to = min(fr, to)-1, max(fr, to)-1
                flow_list[fr] = to
            
    for k, v in flow_list.items():
        if m > 1 and v-k == 1:
            ans[k//m][k%m] = ">"
            ans[v//m][v%m] = "<"
        else:
            ans[k//m][k%m] = "v"
            ans[v//m][v%m] = "^"


    for a in ans:
        print("".join(a))


    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [0]*v
        self.iter = [0]*v
    
    def add_edge(self, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, cap, len(self.graph[fr])-1])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[0] = s
        que.append(s)

        while que:
            v = que.popleft()
            for i in range(len(self.graph[v])):
                e = self.graph[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.append(e[0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.graph[v])):
            self.iter[v] = i
            e = self.graph[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.graph[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = 1
            while f:
                f = self.dfs(s, t, self.inf)
                if f == 0:
                    break
                flow += f


def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*n+j+1, 1)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            flow.add_edge(i*n+j+1, ni*n+nj+1, 1)
                else:
                    flow.add_edge(i*n+j+1, end, 1)
    

    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]

    flow_list = dict()
    for i, g in enumerate(flow.graph):
        for node in g:
            fr, to = i, node[0]
            if fr == start or fr == end or to == start or to == end:
                continue
            cap = node[1]
            if cap != 1:
                fr, to = min(fr, to)-1, max(fr, to)-1
                flow_list[fr] = to
            
    for k, v in flow_list.items():
        if m > 1 and v-k == 1:
            ans[k//n][k%n] = ">"
            ans[v//n][v%n] = "<"
        else:
            ans[k//n][k%n] = "v"
            ans[v//n][v%n] = "^"


    for a in ans:
        print("".join(a))


    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
input = sys.stdin.readline


class Dinic:
    def __init__(self, v):
        self.vertice = v
        self.inf = int(1e9)
        self.graph = [[] for i in range(v)]
        self.level = [[] for i in range(v)]
        self.iter = [[] for i in range(v)]
    
    def add_edge(self, fr, to, cap):
        self.graph[fr].append([to, cap, len(self.graph[to])])
        self.graph[to].append([fr, cap, len(self.graph[fr])])
    
    def bfs(self, s):
        self.level = [-1]*self.vertice
        que = deque([])
        self.level[0] = s
        que.append(s)

        while que:
            v = que.pop()
            for i in range(len(self.graph[v])):
                if self.graph[v][i][1] > 0 and self.level[self.graph[v][i][0]] < 0:
                    self.level[self.graph[v][i][0]] = self.level[v] + 1
                    que.append(self.graph[v][i][0])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(len(self.graph[v])):
            if self.graph[v][i][1] > 0 and self.level[v] < self.level[self.graph[v][i][0]]:
                d = self.dfs(self.graph[v][i][0], t, min(f, self.graph[v][i][1]))
                if d > 0:
                    self.graph[v][i][1] -= d
                    self.graph[self.graph[v][i][0]][self.graph[v][i][2]][1] += d
                    return d
            self.iter[v] += 1
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0]*self.vertice

            f = 1
            while f:
                f = self.dfs(s, t, self.inf)
                if f == 0:
                    break
                flow += f


def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = Dinic(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*n+j+1, 1)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            flow.add_edge(i*n+j+1, ni*n+nj+1, 1)
                else:
                    flow.add_edge(i*n+j+1, end, 1)
    

    res = flow.max_flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]

    flow_list = dict()
    for i, g in enumerate(flow.graph):
        for node in g:
            fr, to = i, node[0]
            if fr == start or fr == end or to == start or to == end:
                continue
            cap = node[1]
            if cap != 1:
                fr, to = min(fr, to)-1, max(fr, to)-1
                flow_list[fr] = to
            
    for k, v in flow_list.items():
        if m > 1 and v-k == 1:
            ans[k//n][k%n] = ">"
            ans[v//n][v%n] = "<"
        else:
            ans[k//n][k%n] = "v"
            ans[v//n][v%n] = "^"


    for a in ans:
        print("".join(a))


    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


class FordFulkerson:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.ans = dict()
        
    #二頂点間を結ぶ経路の追加
    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, cap, forward]
        self.graph[fr].append(forward)
        self.graph[to].append(backward)

    #二頂点間を結ぶ経路の追加（ただし距離が異なる：単方向とかはこれで実装） 
    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.graph[v1].append(edge1)
        self.graph[v2].append(edge2)
    
    def dfs(self, v, t, f, start, end):
        if v == t:
            return f
        used = self.used
        used[v] = 1
        for e in self.graph[v]:
            w, cap, rev = e
            if cap and not used[w]:
                d = self.dfs(w, t, min(f, cap), start, end)
                if d:
                    e[1] -= d
                    rev[1] += d
                    self.ans[w] = rev[0]
                    return d
        return 0
    

    def flow(self, s, t):
        flow = 0
        f = INF = 10**9 + 7
        N = self.n
        while f:
            self.used = [0]*N
            f = self.dfs(s, t, INF, s, t)
            flow += f
        return flow


def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = FordFulkerson(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*n+j+1, 1)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            flow.add_edge(i*n+j+1, ni*n+nj+1, 1)
                else:
                    flow.add_edge(i*n+j+1, end, 1)
    

    res = flow.flow(start, end)
    print(res)

    ans = [["#" if s[i][j] else "." for j in range(n)] for i in range(n)]

    flow_list = dict()
    for g in flow.graph:
        for node in g:
            fr, to = node[0], node[2][0]
            if fr == start or fr == end or to == start or to == end:
                continue
            cap = node[1]
            if cap != 1:
                fr, to = min(fr, to)-1, max(fr, to)-1
                flow_list[fr] = to
            
    for k, v in flow_list.items():
        if m > 1 and v-k == 1:
            ans[k//n][k%n] = ">"
            ans[v//n][v%n] = "<"
        else:
            ans[k//n][k%n] = "v"
            ans[v//n][v%n] = "^"


    for a in ans:
        print("".join(a))


    
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


class FordFulkerson:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.ans = dict()
        
    #二頂点間を結ぶ経路の追加
    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, cap, forward]
        self.graph[fr].append(forward)
        self.graph[to].append(backward)

    #二頂点間を結ぶ経路の追加（ただし距離が異なる：単方向とかはこれで実装） 
    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.graph[v1].append(edge1)
        self.graph[v2].append(edge2)
    
    def dfs(self, v, t, f, start, end):
        if v == t:
            return f
        used = self.used
        used[v] = 1
        for e in self.graph[v]:
            w, cap, rev = e
            if cap and not used[w]:
                d = self.dfs(w, t, min(f, cap), start, end)
                if d:
                    e[1] -= d
                    rev[1] += d
                    self.ans[w] = rev[0]
                    return d
        return 0
    

    def flow(self, s, t):
        flow = 0
        f = INF = 10**9 + 7
        N = self.n
        while f:
            self.used = [0]*N
            f = self.dfs(s, t, INF, s, t)
            flow += f
        return flow


def main():
    n, m = map(int, input().split())
    s = [[1 if x == "#" else 0 for x in input()[:-1]] for i in range(n)]
    
    flow = FordFulkerson(n*m+2)
    start = 0
    end = n*m+1
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                if (i+j)%2:
                    flow.add_edge(start, i*n+j+1, 1)
                    for x, y in direction:
                        ni, nj = x + i, y + j
                        if 0 <= ni < n and 0 <= nj < m and s[ni][nj] == 0:
                            flow.add_edge(i*n+j+1, ni*n+nj+1, 1)
                else:
                    flow.add_edge(i*n+j+1, end, 1)
    

    res = flow.flow(start, end)
    print(res)

    judge1 = set()
    judge2 = set()
    for k, v in flow.ans.items():
        if v == start or v == end or k == start or k == end:
            continue
        judge1.add(k)
        judge2.add(v)
    
    not_use = set()
    for k in judge1:
        if k in judge2 and flow.ans[k] in judge1:
            not_use.add(k)

    for i in range(n):
        for j in range(m):
            if s[i][j] == 1:
                s[i][j] = "#"
            if s[i][j] == 0:
                s[i][j] = "."

    for k in judge1:
        if k in not_use:
            continue
        v = flow.ans[k]
        p, q = min(k, v)-1, max(k, v)-1
        if m > 1 and q - p == 1:
            s[p//n][p%n] = ">"
            s[q//n][q%n] = "<"
        else:
            s[p//n][p%n] = "v"
            s[q//n][q%n] = "^"
    

    for ans in s:
        print("".join(ans))





    
if __name__ == "__main__":
    main()