maehrm

import sys

sys.setrecursionlimit(10**7)


def dfs(v):
    if dp[v] != -1:             # 調査済み
        return dp[v]
    ret = 0
    for nxt in G[v]:

maehrm

idx = [-1] * 1609
fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]

def ask(i):
    if idx[i] == -1:
        print("?", i)
        idx[i] = int(input())
    return idx[i]

def solv():

maehrm

N = int(input())
S = input()
T = input()
MOD = 699999953
seq1 = [0] * N
seq3 = [0] * N
for i in range(N):
    if S[i] == "G":
        seq1[i] = 1
    elif S[i] == "B":

maehrm

S = 1 << 1 | 1 << 3 | 1 << 5  # S = {1, 3, 5}
N = 6  # 6ビット使用するため
PS = S  # 集合Sの冪集合PSを求める。
ans = [[]]  # 空集合は含めておく
while PS > 0:
    tmp = []
    for i in range(N):
        if (PS >> i) & 1:
            tmp.append(i)
    ans.append(tmp)

maehrm

N, M = map(int, input().split())
G = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a][b] = True
    G[b][a] = True

ok = [True] * (1 << N)  # 各頂点が繋がっているかどうか?
for bit in range(1 << N):
    vs = []

maehrm

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
cst = [0] * (1 << N)
for msk in range(1 << N):       # あらかじめmskグループのときの点数をcstに求めておく
    for i in range(N):
        for j in range(i + 1, N):
            if (msk & (1 << i)) and (msk & (1 << j)):
                cst[msk] += a[i][j]
for msk in range(1 << N):

maehrm

class RollingHash:
    def __init__(self, str, base, mod):
        self.base = base
        self.mod = mod
        self.pow = [1] * (len(str) + 1)
        self.hash = [0] * (len(str) + 1)
        for i in range(len(str)):
            self.hash[i + 1] = (self.hash[i] * base + ord(str[i])) % mod
            self.pow[i + 1] = self.pow[i] * base % mod

maehrm

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

maehrm

from collections import deque


class Dinic:
    def __init__(self, max_v):
        self.n = max_v
        self.G = [[] for _ in range(self.n)]

    def add_edge(self, fr, to, cap):  # frからtoへ向かう容量capの辺を追加する
        self.G[fr].append([to, cap, len(self.G[to])])

maehrm

from atcoder.maxflow import MFGraph


def index(i, j):
    return i * M + j


N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]
g = MFGraph(N * M + 2)