Problem:


Score : 100 points

Problem Statement

You are given an undirected graph with N vertices and 0 edges. Process Q queries of the following types.

0 u v: Add an edge (u, v).

1 u v: Print 1 if u and v are in the same connected component, 0 otherwise.

Constraints

1 \leq N \leq 200,000

1 \leq Q \leq 200,000

0 \leq u_i, v_i \lt N

Input

Input is given from Standard Input in the following format:

N Q
t_1 u_1 v_1
t_2 u_2 v_2
:
t_Q u_Q v_Q

出力

For each query of the latter type, print the answer.

Sample Input 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

Sample Output 1

0
1
0
1



Sample input:
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3


Sample output:
0
1
0
1

Submission status: Accepted

Solution code:
# Date [ 2020-09-07 23:55:41 ]
# Problem [ a.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def Main():
    n, q = read_ints()
    uf = UnionFind(n)
    for _ in range(q):
        t, u, v = read_ints()
        if t == 0:
            uf.union(u, v)
        else:
            if uf.same(u, v):
                print(1)
            else:
                print(0)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            while self.root[x] >= 0:
                x = self.root[x]
            return x

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    N, Q = map(int, input().split())
    UF = UnionFind(N)
    for _ in range(Q):
        q, u, v = map(int, input().split())
        if q == 0:
            UF.unite(u+1, v+1)
        else:
            print(int(UF.isSameGroup(u+1, v+1)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
Created on 2020/09/07

@author: harurun
'''
from dataclasses import *
@dataclass
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,Q=map(int,pin().split())
  uf=UnionFind(N)
  for i in range(Q):
    t,u,v=map(int,pin().split())
    if t==0:
      uf.union(u, v)
    else:
      if uf.same(u,v):
        print(1)
      else:
        print(0)
  return 
main()

Submission status: Accepted

Solution code:
n, q = map(int,input().split())

class UnionFind:
	"""
	class UnionFind
	https://note.nkmk.me/python-union-find/
	
	order O(log(n))
	
	n = the number of elements
	parents = the list that contains "parents" of x. be careful that it doesn't contain "root" of x.
	"""
	def __init__(self, n):
		"""
		make UnionFind
		:param n: the number of elements
		"""
		self.n = n
		self.parents = [-1] * n
	
	def find(self, x):
		"""
		:param x: an element
		:return: the root containing x
		"""
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]
	
	def union(self, x, y):
		"""
		:param x, y: an element
		"""
		# root
		x = self.find(x)
		y = self.find(y)
		if x == y:
			# already same group so do nothing
			return
		if self.parents[x] > self.parents[y]:
			# the root should be min of group
			x, y = y, x
		# remind that x, y is the root, x < y, then, y unions to x.
		self.parents[x] += self.parents[y]
		# and then y's parent is x.
		self.parents[y] = x
	def size(self, x):
		# return the size of group
		return -self.parents[self.find(x)]
	
	def same(self, x, y):
		# return whether the x, y are in same group
		return self.find(x) == self.find(y)
	
	def members(self, x):
		# return members of group
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]
	
	def roots(self):
		# return all roots
		return [i for i, x in enumerate(self.parents) if x < 0]
	
	def group_count(self):
		# return how many groups
		return len(self.roots())
	
	def all_group_members(self):
		# return all members of all groups
		return {r: self.members(r) for r in self.roots()}

targ = UnionFind(n)

for i in range(q):
	t, u, v = map(int,input().split())
	if t == 0:
		targ.union(u, v)
	else:
		if targ.same(u, v):
			print(1)
		else:
			print(0)

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n, q = map(int, input().split())
par = [-1 for i in range(n)]
for i in range(q):
    t, u, v = map(int, input().split())
    if t == 0:
        unite(u, v)
    else:
        print(1 if same(u, v) else 0)

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
#================================================
N,Q=map(int,input().split())
U=Union_Find(N)

X=[]
for _ in range(Q):
    t,u,v=map(int,input().split())
    if t==0:
        U.union(u,v)
    else:
        X.append(1*U.same(u,v))

print("\n".join(map(str,X)))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def par(a):
    L = []
    while P[a] >= 0:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    if par(a) != par(b):
        if P[par(b)] >= P[par(a)]:
            if P[par(b)] == P[par(a)]: P[par(a)] -= 1
            P[par(b)] = par(a)
        else:
            P[par(a)] = par(b)

N, Q = map(int, input().split())
P = [-1 for i in range(N)]
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        unite(u, v)
    else:
        print(1 if par(u) == par(v) else 0)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            li = []
            while self.parents[x] >= 0:
                li.append(x)
                x = self.parents[x]
            for y in li:
                self.parents[y] = x
            return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys
input = sys.stdin.buffer.readline
N,Q = map(int,input().split())
uf = UnionFind(N)
for i in range(Q):
    t,u,v = map(int,input().split())
    if t == 0:
        uf.union(u,v)
    else:
        if uf.same(u,v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, q = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]

for _ in range(q):
    t, u, v = map(int, input().split())
    if t == 0:
        unite(u, v)
    else:
        print(1 if same(u, v) else 0)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x): #親を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y): #和集合の生成
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x): #所属する集合の大きさ
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じ集合に属しているか判定
        return self.find(x) == self.find(y)

    def members(self, x): #同じ集合に属する要素全列挙
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self): #集合のリーダー全列挙
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self): #集合の数
        return len(self.roots())

    def all_group_members(self): #辞書型,{(リーダーの番号):(その集合の要素全列挙)}
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,q=map(int,input().split())
uf=UnionFind(n)
for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        uf.union(b,c)
    else:
        if uf.same(b,c):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n+1)]  # �?要�?の親要�?の番号を�?�納するリス�?
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # 根?��ルート）�?�場合、そのグループ�?�要�?数を�?�納するリス�?

    # 要�? x が属するグループ�?�根を返す
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 要�? x が属するグループと要�? y が属するグループとを併合す�?
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 要�? x, y が同じグループに属するかど�?かを返す
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要�? x が属するグループに属する要�?をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(1,self.n+1) if self.find(i) == root]

    # 要�? x が属するグループ�?�サイズ?��要�?数?��を返す
    def get_size(self, x):
        return self.size[self.find(x)]

    # すべての根の要�?をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.par) if x == i and i != 0]
    
    # グループ�?�数を返す
    def group_count(self):
        return len(self.roots())
    
    # {ルート要�?: [そ�?�グループに含まれる要�?のリス�?], ...} の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
n,q = map(int,input().split())
uf = UnionFind(n)
for i in range(q):
    p,a,b = map(int,input().split())
    if p:
        print(1 if uf.same_check(a,b) else 0)
        continue
    else:
        uf.union(a,b)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
TUV = [tuple(map(int,input().split())) for i in range(Q)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
for t,u,v in TUV:
    u,v = u-1,v-1
    if t:
        print(int(uf.is_same(u,v)))
    else:
        uf.unite(u,v)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			if self.table[self.table[x]] >= 0:
				self.table[x] = self.table[self.table[x]]
			x = self.table[x]
		return x

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

n, q = map(int, input().split())
uf = UnionFind(n)
for _ in range(q):
	t, u, v = map(int, input().split())
	if t == 0:
		uf.unite(u, v)
	else:
		if uf.find(u) == uf.find(v):
			print(1)
		else:
			print(0)

Submission status: Runtime Error

Solution code:
#![allow(unused_imports, non_snake_case, dead_code)]
use proconio::{
    input, fastout,
    marker::{Chars, Bytes, Usize1}
};

struct UnionFind {
    size: usize,
    pos: Vec<isize>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        let size = n;
        let pos = vec![-1; n + 1];
        UnionFind { size, pos }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.pos[x] < 0 {
            x
        } else {
            let v = self.pos[x] as usize;
            self.pos[x] = self.find(v) as isize;
            self.pos[x] as usize
        }
    }
    fn unite(&mut self, x: usize, y: usize) -> Result<(), ()> {
        let mut x = self.find(x);
        let mut y = self.find(y);
        if x == y {
            return Err(());
        };
        if self.pos[x] > self.pos[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.pos[x] += self.pos[y];
        self.pos[y] = x as isize;
        Ok(())
    }
    fn same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
    fn size(&mut self, x: usize) -> usize {
        let x = self.find(x);
        -self.pos[x] as usize
    }
}

#[fastout]
fn main() {
    input! {
        N: usize, Q: usize,
        l: [(usize, usize, usize); Q]
    }
    let mut uf = UnionFind::new(N);
    for &(t, x, y) in &l {
        if t > 0 {
            println!("{}", if uf.same(x, y) {1} else {0});
        } else {
            uf.unite(x,y).ok();
        }
    }
    // println!("{}", N);
}

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
dsu = DSU(N)

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        # add line
        dsu.merge(u, v)
    else:
        # concat
        if dsu.same(u, v):
            print(1)
        else:
            print(0)

import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;

int main() {
    int N, Q;
    cin >> N >> Q;
    dsu d(N);
    for (int i = 0; i < Q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t) {
            cout << d.same(u, v) << endl;
        } else {
            d.merge(u, v);
        }
    }
}

Submission status: Runtime Error

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x


import sys

read = sys.stdin.read

N, _, *X = map(int, readline().split())
tree = UnionFind(N)
res = []
for t, u, v in zip(*[iter(X)] * 3):
    if t:
        res.append(int(tree.is_connected(u, v)))
    else:
        tree.unite(u, v)
print("\n".join(map(str, res)))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/practice2/submissions/16598132
# 上記のリンクの提出をいじらせてもらってます。

class mf_graph:

    __slots__ = ["N", "graph", "capacities", "level", "it"]

    def __init__(self, N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.capacities = [dict() for _ in range(N)]

    def add_edge(self, v, w, cap):
        self.graph[v].append(w)
        self.graph[w].append(v)
        self.capacities[v][w] = cap
        self.capacities[w][v] = 0

    # def bfs(self, s, t):
    #     self.level = [-1] * self.N
    #     q = deque([s])
    #     self.level[s] = 0
    #     while q:
    #         v = q.popleft()
    #         if v == t:
    #             return True
    #         for w, cap in self.capacities[v].items():
    #             if cap and self.level[w] == -1:
    #                 self.level[w] = self.level[v] + 1
    #                 q.append(w)
    #     return False

    def bfs(self, s, t):
        self.level = [-1] * self.N
        q = [s]
        nq = []
        self.level[s] = 0
        while q:
            nq = []
            for v in q:
                if v == t:
                    return True
                for w, cap in self.capacities[v].items():
                    if cap and self.level[w] == -1:
                        self.level[w] = self.level[v] + 1
                        nq.append(w)
            q = nq
        return False

    def dfs(self, s, t, up):
        st = [t]
        while st:
            v = st[-1]
            if v == s:
                flow = up
                for i in range(len(st) - 2):
                    flow = min(flow, self.capacities[st[i+1]][st[i]])
                for i in range(len(st) - 1):
                    self.capacities[st[i]][st[i+1]] += flow
                    self.capacities[st[i+1]][st[i]] -= flow
                return flow
            while self.it[v] < len(self.graph[v]):
                w = self.graph[v][self.it[v]]
                cap = self.capacities[w][v]
                if cap and self.level[w] != -1:
                    if self.level[v] > self.level[w]:
                        st.append(w)
                        break
                self.it[v] += 1
            else:
                st.pop()
                self.level[v] = self.N
        return 0

    def flow(self, s, t, flow_limit=18446744073709551615):
        flow = 0
        while flow < flow_limit and self.bfs(s, t):
            self.it = [0]*self.N
            while flow < flow_limit:
                f = self.dfs(s, t, flow_limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [False]*self.N
        q = [s]
        while q:
            v = q.pop()
            visited[v] = True
            for w, cap in self.capacities[v].items():
                if cap and not visited[w]:
                    q.append(w)


# """
N, M = map(int, input().split())
S = [list(input()) for i in range(N)]
"""
with open("flow.txt") as f:
    N, M = map(int, f.readline().rstrip().split())
    S = [list(f.readline().rstrip()) for i in range(N)]
#"""
dc = mf_graph(N*M+2)

s = N*M
t = N*M+1
for i in range(N):
    for j in range(M):
        if (i+j) % 2 == 0:
            dc.add_edge(s, M*i+j, 1)
        else:
            dc.add_edge(M*i+j, t, 1)

for i in range(N):
    for j in range(M):
        if j+1 < M and S[i][j] == "." and S[i][j+1] == ".":
            u, v = M*i+j, M*i+j+1
            if (i+j) % 2 == 1:
                u, v = v, u
            dc.add_edge(u, v, 1)
        if i+1 < N and S[i][j] == "." and S[i + 1][j] == ".":
            u, v = M*i+j, M*(i+1)+j
            if (i+j) % 2 == 1:
                u, v = v, u
            dc.add_edge(u, v, 1)

print(dc.flow(s, t))
for u in range(N*M+2):
    ui, uj = divmod(u, M)
    if (ui+uj) % 2 == 1:
        continue
    for v, cap in dc.capacities[u].items():
        if cap != 0:
            continue
        vi, vj = divmod(v, M)
        if u != s and u != t and v != s and v != t:
            if ui+1 == vi:
                S[ui][uj] = "v"
                S[vi][vj] = "^"
            elif ui == vi+1:
                S[ui][uj] = "^"
                S[vi][vj] = "v"
            elif uj+1 == vj:
                S[ui][uj] = ">"
                S[vi][vj] = "<"
            elif uj == vj+1:
                S[ui][uj] = "<"
                S[vi][vj] = ">"

for res in S:
    print("".join(res))