#line 2 "/home/yuruhiya/programming/library/Utility/get_MOD.cpp"
constexpr long long get_MOD(){
#ifdef SET_MOD
return SET_MOD;
#else 
return 1000000007;
#endif
}
#line 3 "/home/yuruhiya/programming/library/Utility/constants.cpp"
#include<vector>
#include<string>
#include<utility>
#include<queue>

#define rep(i,n)for(int i=0;i<(n);++i)
#define FOR(i,m,n)for(int i=(m);i<(n);++i)
#define rrep(i,n)for(int i=(n)-1;i>=0;--i)
#define rfor(i,m,n)for(int i=(m);i>=(n);--i)
#define INTERNAL_CAT_IMPL(s1,s2)s1##s2
#define INTERNAL_CAT(s1,s2)INTERNAL_CAT_IMPL(s1,s2)
#ifdef __COUNTER__
#define loop(n)rep(INTERNAL_CAT(_i,__COUNTER__),n)
#else 
#define loop(n)rep(INTERNAL_CAT(_i,__COUNTER__),n)
#endif
#define unless(c)if(!(c))
#define ALL(x)(x).begin(),(x).end()
#define RALL(x)(x).rbegin(),(x).rend()
#define range_it(a,l,r)(a).begin()+(l),(a).begin()+(r)
using ll=long long;using LD=long double;using VB=std::vector<bool>;using VVB=std::vector<VB>;using VI=std::vector<int>;using VVI=std::vector<VI>;using VL=std::vector<ll>;using VVL=std::vector<VL>;using VS=std::vector<std::string>;using VD=std::vector<LD>;using PII=std::pair<int,int>;using VP=std::vector<PII>;using PLL=std::pair<ll,ll>;using VPL=std::vector<PLL>;template<class T>using PQ=std::priority_queue<T>;template<class T>using PQS=std::priority_queue<T,std::vector<T>,std::greater<T>>;constexpr int inf=1000000000;constexpr long long inf_ll=1000000000000000000ll,MOD=get_MOD();constexpr long double PI=3.14159265358979323846,tau=PI*2,EPS=1e-12;
#line 2 "/home/yuruhiya/programming/library/Utility/Scanner.cpp"
#include<iostream>
#line 6 "/home/yuruhiya/programming/library/Utility/Scanner.cpp"
#include<tuple>
#include<type_traits>

#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#define fwrite_unlocked fwrite
#define fflush_unlocked fflush
#endif
class Scanner{template<class T,class=void>struct has_scan : std::false_type{};template<class T>struct has_scan<T,std::void_t<decltype(std::declval<T>().template scan<Scanner>())>>: std::true_type{};public:static int gc(){return getchar_unlocked();}static char next_char(){char c;scan(c);return c;}template<class T>static void scan(T&v){if(has_scan<T>::value){v.template scan<Scanner>();}else{std::cin>>v;}}static void scan(char&v){while(std::isspace(v=gc()));}static void scan(bool&v){v=next_char()!='0';}static void scan(std::vector<bool>::reference v){bool b;scan(b);v=b;}static void scan(std::string&v){v.clear();for(char c=next_char();!std::isspace(c);c=gc())v+=c;}static void scan(int&v){v=0;bool neg=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c);c=gc())v=v*10+(c-'0');if(neg)v=-v;}static void scan(long long&v){v=0;bool neg=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c);c=gc())v=v*10+(c-'0');if(neg)v=-v;}static void scan(double&v){v=0;double dp=1;bool neg=false,after_dp=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c)||c=='.';c=gc()){if(c=='.'){after_dp=true;}else if(after_dp){v+=(c-'0')*(dp*=0.1);}else{v=v*10+(c-'0');}}if(neg)v=-v;}static void scan(long double&v){v=0;long double dp=1;bool neg=false,after_dp=false;char c=next_char();if(c=='-'){neg=true;c=gc();}for(;std::isdigit(c)||c=='.';c=gc()){if(c=='.'){after_dp=true;}else if(after_dp){v+=(c-'0')*(dp*=0.1);}else{v=v*10+(c-'0');}}if(neg)v=-v;}template<class T,class U>static void scan(std::pair<T,U>&v){scan(v.first);scan(v.second);}template<class T,std::enable_if_t<!std::is_same_v<bool,T>,std::nullptr_t> =nullptr>static void scan(std::vector<T>&v){for(auto&e : v)scan(e);}template<class T,std::enable_if_t<std::is_same_v<bool,T>,std::nullptr_t> =nullptr>static void scan(std::vector<T>&v){for(auto e : v)scan(e);}private:template<std::size_t N=0,class T>static void scan_tuple_impl(T&v){if constexpr(N<std::tuple_size_v<T>){scan(std::get<N>(v));scan_tuple_impl<N+1>(v);}}public:template<class... T>static void scan(std::tuple<T...>&v){scan_tuple_impl(v);}private:struct Read2DVectorHelper{std::size_t h,w;Read2DVectorHelper(std::size_t _h,std::size_t _w): h(_h),w(_w){}template<class T>operator std::vector<std::vector<T>>(){std::vector vector(h,std::vector<T>(w));scan(vector);return vector;}};struct ReadVectorHelper{std::size_t n;ReadVectorHelper(std::size_t _n): n(_n){}template<class T>operator std::vector<T>(){std::vector<T>vector(n);scan(vector);return vector;}auto operator[](std::size_t m){return Read2DVectorHelper(n,m);}};public:template<class T>T read()const{T result;scan(result);return result;}template<class T>auto read(std::size_t n)const{std::vector<T>result(n);scan(result);return result;}template<class T>auto read(std::size_t h,std::size_t w)const{std::vector result(h,std::vector<T>(w));scan(result);return result;}std::string read_line()const{std::string v;for(char c=gc();c!='\n'&&c!='\0';c=gc())v+=c;return v;}template<class T>operator T()const{return read<T>();}int operator--(int)const{return read<int>()-1;}auto operator[](std::size_t n)const{return ReadVectorHelper(n);}auto operator[](const std::pair<std::size_t,std::size_t>&nm)const{return Read2DVectorHelper(nm.first,nm.second);}void operator()()const{}template<class H,class... T>void operator()(H&&h,T&&... t)const{scan(h);operator()(std::forward<T>(t)...);}private:template<template<class...>class,class...>struct Column;template<template<class...>class V,class Head,class... Tail>struct Column<V,Head,Tail...>{template<class... Args>using vec=V<std::vector<Head>,Args...>;using type=typename Column<vec,Tail...>::type;};template<template<class...>class V>struct Column<V>{using type=V<>;};template<class... T>using column_t=typename Column<std::tuple,T...>::type;template<std::size_t N=0,class T>void column_impl(T&t)const{if constexpr(N<std::tuple_size_v<T>){auto&vec=std::get<N>(t);using V=typename std::remove_reference_t<decltype(vec)>::value_type;vec.push_back(read<V>());column_impl<N+1>(t);}}public:template<class... T>auto column(std::size_t h)const{column_t<T...>result;while(h--)column_impl(result);return result;}}in;
#define inputs(T,...)\
T __VA_ARGS__;\in(__VA_ARGS__)
#define ini(...)inputs(int,__VA_ARGS__)
#define inl(...)inputs(long long,__VA_ARGS__)
#define ins(...)inputs(std::string,__VA_ARGS__)
#line 5 "/home/yuruhiya/programming/library/Utility/Printer.cpp"
#include<array>
#line 7 "/home/yuruhiya/programming/library/Utility/Printer.cpp"
#include<string_view>
#include<optional>
#include<charconv>
#line 11 "/home/yuruhiya/programming/library/Utility/Printer.cpp"
#include<cstring>
#include<cassert>
class Printer{public:struct BoolString{std::string_view t,f;BoolString(std::string_view _t,std::string_view _f): t(_t),f(_f){}};struct Separator{std::string_view div,sep,last;Separator(std::string_view _div,std::string_view _sep,std::string_view _last): div(_div),sep(_sep),last(_last){}};inline static const BoolString Yes{"Yes","No"},yes{"yes","no"},YES{"YES","NO"},Int{"1","0"},Possible{"Possible","Impossible"};inline static const Separator space{" "," ","\n"},no_space{"","","\n"},endl{"\n","\n","\n"},comma{",",",","\n"},no_endl{" "," ",""},sep_endl{" ","\n","\n"};BoolString bool_str{Yes};Separator separator{space};private:template<class T,class=void>struct has_print : std::false_type{};template<class T>struct has_print<T,std::void_t<decltype(std::declval<T>().print(std::declval<Printer>()))>>: std::true_type{};public:void print(int v)const{char buf[12]{};if(auto [ptr,e]=std::to_chars(std::begin(buf),std::end(buf),v);e==std::errc{}){print(std::string_view(buf,ptr-buf));}else{assert(false);}}void print(long long v)const{char buf[21]{};if(auto [ptr,e]=std::to_chars(std::begin(buf),std::end(buf),v);e==std::errc{}){print(std::string_view(buf,ptr-buf));}else{assert(false);}}void print(bool v)const{print(v ? bool_str.t : bool_str.f);}void print(std::vector<bool>::reference v)const{print(v ? bool_str.t : bool_str.f);}void print(char v)const{putchar_unlocked(v);}void print(std::string_view v)const{fwrite_unlocked(v.data(),sizeof(std::string_view::value_type),v.size(),stdout);}void print(double v)const{std::printf("%.20f",v);}void print(long double v)const{std::printf("%.20Lf",v);}template<class T,std::enable_if_t<has_print<T>::value,std::nullptr_t> =nullptr>void print(const T&v)const{v.print(*this);}template<class T,std::enable_if_t<!has_print<T>::value,std::nullptr_t> =nullptr>void print(const T&v)const{std::cout<<v;}template<class T,class U>void print(const std::pair<T,U>&v)const{print(v.first);print(separator.div);print(v.second);}template<class T>void print(const std::optional<T>&v)const{print(*v);}template<class InputIterater>void print_range(const InputIterater&begin,const InputIterater&end)const{for(InputIterater i=begin;i!=end;++i){if(i!=begin)print(separator.sep);print(*i);}}template<class T>void print(const std::vector<T>&v)const{print_range(v.begin(),v.end());}template<class T,std::size_t N>void print(const std::array<T,N>&v)const{print_range(v.begin(),v.end());}template<class T>void print(const std::vector<std::vector<T>>&v)const{for(std::size_t i=0;i<v.size();++i){if(i)print(separator.last);print(v[i]);}}Printer()=default;Printer(const BoolString&_bool_str,const Separator&_separator): bool_str(_bool_str),separator(_separator){}Printer&operator()(){print(separator.last);return*this;}template<class Head>Printer&operator()(Head&&head){print(head);print(separator.last);return*this;}template<class Head,class... Tail>Printer&operator()(Head&&head,Tail&&... tail){print(head);print(separator.sep);return operator()(std::forward<Tail>(tail)...);}template<class... Args>Printer&flag(bool f,Args&&... args){if(f){return operator()(std::forward<Args>(args)...);}else{return*this;}}template<class InputIterator>Printer&range(const InputIterator&begin,const InputIterator&end){print_range(begin,end);print(separator.last);return*this;}template<class Container>Printer&range(const Container&a){range(a.begin(),a.end());return*this;}template<class... T>void exit(T&&... t){operator()(std::forward<T>(t)...);std::exit(EXIT_SUCCESS);}Printer&flush(){fflush_unlocked(stdout);return*this;}Printer&set(const BoolString&_bool_str){bool_str=_bool_str;return*this;}Printer&set(const Separator&_separator){separator=_separator;return*this;}Printer&set(std::string_view t,std::string_view f){bool_str=BoolString(t,f);return*this;}}out;
#line 2 "/home/yuruhiya/programming/library/Utility/functions.cpp"
#include<algorithm>
#include<numeric>
#include<cmath>
#line 8 "/home/yuruhiya/programming/library/Utility/functions.cpp"
template<class T=long long>constexpr T TEN(std::size_t n){T result=1;for(std::size_t i=0;i<n;++i)result*=10;return result;}template<class T,class U,std::enable_if_t<std::is_integral_v<T>&&std::is_integral_v<U>,std::nullptr_t> =nullptr>constexpr auto div_ceil(T n,U m){return(n+m-1)/m;}template<class T,class U>constexpr auto div_ceil2(T n,U m){return div_ceil(n,m)*m;}template<class T>constexpr T triangle(T n){return(n&1)?(n+1)/2*n : n/2*(n+1);}template<class T>constexpr T nC2(T n){return(n&1)?(n-1)/2*n : n/2*(n-1);}template<class T,class U>constexpr auto middle(const T&l,const U&r){return l+(r-l)/2;}template<class T,class U,class V>constexpr bool in_range(const T&v,const U&lower,const V&upper){return lower<=v&&v<upper;}template<class T,std::enable_if_t<std::is_integral_v<T>,std::nullptr_t> =nullptr>constexpr bool is_square(T n){T s=std::sqrt(n);return s*s==n||(s+1)*(s+1)==n;}template<class T=long long>constexpr T BIT(int b){return T(1)<<b;}template<class T>constexpr int BIT(T x,int i){return(x&(T(1)<<i))? 1 : 0;}template<class T>constexpr int Sgn(T x){return(0<x)-(0>x);}template<class T>bool is_leap(T year){return!(year%4)&&(year%100||!(year%400));}template<class T,class U,std::enable_if_t<std::is_integral_v<U>,std::nullptr_t> =nullptr>constexpr T Pow(T a,U n){assert(n>=0);T result=1;while(n>0){if(n&1){result*=a;n--;}else{a*=a;n>>=1;}}return result;}template<class T,class U,std::enable_if_t<std::is_integral_v<U>,std::nullptr_t> =nullptr>constexpr T Powmod(T a,U n,T mod){assert(n>=0);if(a>mod)a%=mod;T result=1;while(n>0){if(n&1){result=result*a%mod;n--;}else{a=a*a%mod;n>>=1;}}return result;}template<class T>bool chmax(T&a,const T&b){return a<b ? a=b,true : false;}template<class T>bool chmin(T&a,const T&b){return a>b ? a=b,true : false;}template<class T>int sz(const T&v){return v.size();}template<class T,class U>int lower_index(const T&a,const U&v){return std::lower_bound(a.begin(),a.end(),v)-a.begin();}template<class T,class U,class F>int lower_index(const T&a,const U&v,const F&f){return std::lower_bound(a.begin(),a.end(),v,f)-a.begin();}template<class T,class U>int upper_index(const T&a,const U&v){return std::upper_bound(a.begin(),a.end(),v)-a.begin();}template<class T,class U,class F>int upper_index(const T&a,const U&v,const F&f){return std::upper_bound(a.begin(),a.end(),v,f)-a.begin();}template<class T,class U=typename T::value_type>U Gcdv(const T&v){return std::accumulate(std::next(v.begin()),v.end(),U(*v.begin()),std::gcd<U,U>);}template<class T,class U=typename T::value_type>U Lcmv(const T&v){return std::accumulate(std::next(v.begin()),v.end(),U(*v.begin()),std::lcm<U,U>);}template<class T>T&Concat(T&v,const T&vec){v.insert(v.end(),vec.begin(),vec.end());return v;}namespace internal{template<class T,std::size_t N>auto make_vector(std::vector<int>&sizes,const T&init){if constexpr(N==1){return std::vector(sizes[0],init);}else{int size=sizes[N-1];sizes.pop_back();return std::vector(size,make_vector<T,N-1>(sizes,init));}}}template<class T,std::size_t N>auto make_vector(const int(&sizes)[N],const T&init=T()){std::vector s(std::rbegin(sizes),std::rend(sizes));return internal::make_vector<T,N>(s,init);}template<class F>struct rec_lambda{F f;rec_lambda(F&&f_): f(std::forward<F>(f_)){}template<class... Args>auto operator()(Args&&... args)const{return f(*this,std::forward<Args>(args)...);}};namespace lambda{auto char_to_int=[](char c){return c-'0';};auto lower_to_int=[](char c){return c-'a';};auto upper_to_int=[](char c){return c-'A';};auto int_to_char=[](int i)->char{return '0'+i;};auto int_to_lower=[](int i)->char{return 'a'+i;};auto int_to_upper=[](int i)->char{return 'A'+i;};auto is_odd=[](auto n){return n%2==1;};auto is_even=[](auto n){return n%2==0;};auto is_positive=[](auto n){return n>0;};auto is_negative=[](auto n){return n<0;};auto increment=[](auto n){return++n;};auto decrement=[](auto n){return--n;};auto self=[](const auto&n){return n;};auto first=[](const auto&n){return n.first;};auto second=[](const auto&n){return n.second;};template<class T>auto cast(){return [](const auto&n){return static_cast<T>(n);};};template<class T>auto equal_to(const T&x){return [x](auto y){return x==y;};}template<std::size_t I>auto get(){return [](const auto&n){return std::get<I>(n);};}template<class F>auto cmp(F&&f){return [f](const auto&a,const auto&b){return f(a)<f(b);};}}
#line 6 "/home/yuruhiya/programming/library/template_no_Ruby.cpp"
#if __has_include(<library/dump.hpp>)
#include<library/dump.hpp>
#define LOCAL
#else 
#define dump(...)((void)0)
#define dump2(...)((void)0)
#endif
#line 2 "/home/yuruhiya/programming/library/Utility/oj_local.cpp"
template<class T>constexpr T oj_local(const T&oj,const T&local){
#ifndef LOCAL
return oj;
#else 
return local;
#endif
}
#line 14 "/home/yuruhiya/programming/library/template_no_Ruby.cpp"
#include<bits/stdc++.h>
#line 6 "/home/yuruhiya/programming/library/Graph/BipartiteMatching.cpp"
class BipartiteMatching{std::size_t left,right;std::vector<std::vector<int>>graph;std::vector<bool>used;std::vector<int>left_match,right_match;bool dfs(int v){if(used[v]){return false;}used[v]=true;for(int u : graph[v]){if(right_match[u]==-1||dfs(right_match[u])){left_match[v]=u;right_match[u]=v;return true;}}return false;}public:BipartiteMatching(std::size_t _left,std::size_t _right): left(_left),right(_right),graph(left),used(left),left_match(left),right_match(right){}BipartiteMatching(std::size_t _left,std::size_t _right,const std::vector<std::vector<int>>&_graph): left(_left),right(_right),graph(_graph),used(left),left_match(left),right_match(right){assert(graph.size()==left);}BipartiteMatching(std::size_t _left,std::size_t _right,const std::vector<std::pair<int,int>>&edges): left(_left),right(_right),graph(left),used(left),left_match(left),right_match(right){for(auto [u,v] : edges){graph[u].push_back(v);}}void add_edge(int l,int r){graph[l].push_back(r);}int solve(){int result=0;std::fill(left_match.begin(),left_match.end(),-1);std::fill(right_match.begin(),right_match.end(),-1);std::fill(used.begin(),used.end(),false);for(bool update=true;update;){update=false;for(std::size_t i=0;i<left;++i){if(left_match[i]==-1&&dfs(i)){update=true;++result;}}if(update){std::fill(used.begin(),used.end(),false);}}return result;}std::vector<std::pair<int,int>>edges()const{std::vector<std::pair<int,int>>result;for(std::size_t i=0;i<left;++i){if(left_match[i]!=-1){result.emplace_back(i,left_match[i]);}}return result;}};
#line 11 "/home/yuruhiya/programming/library/Utility/Point.cpp"
struct Point{using direction_iterator=std::vector<Point>::const_iterator;private:static inline int W,H;public:static void set_range(int height,int width){H=height;W=width;}static int height(){return H;}static int width(){return W;}static constexpr Point zero(){return{0,0};}static constexpr Point L(){return{0,-1};}static constexpr Point R(){return{0,1};}static constexpr Point U(){return{-1,0};}static constexpr Point D(){return{1,0};}static constexpr Point LU(){return{-1,-1};}static constexpr Point LD(){return{1,-1};}static constexpr Point RU(){return{-1,1};}static constexpr Point RD(){return{1,1};}static const std::vector<Point>direction;int y,x;constexpr Point(): y(0),x(0){}constexpr Point(int _y,int _x): y(_y),x(_x){}constexpr Point(const std::pair<int,int>&yx): y(yx.first),x(yx.second){}Point(int n): y(n/W),x(n%W){}constexpr Point operator+()const{return*this;}constexpr Point operator-()const{return{-y,-x};}constexpr Point operator+(const Point&p)const{return Point(*this)+=p;}constexpr Point operator-(const Point&p)const{return Point(*this)-=p;}constexpr Point operator*(const Point&p)const{return Point(*this)*=p;}constexpr Point operator/(const Point&p)const{return Point(*this)/=p;}constexpr Point operator%(const Point&p)const{return Point(*this)%=p;}constexpr Point operator+(int n)const{return Point(*this)+=n;}constexpr Point operator-(int n)const{return Point(*this)-=n;}constexpr Point operator*(int n)const{return Point(*this)*=n;}constexpr Point operator/(int n)const{return Point(*this)/=n;}constexpr Point operator%(int n)const{return Point(*this)%=n;}constexpr Point&operator+=(const Point&p){y+=p.y;x+=p.x;return*this;}constexpr Point&operator-=(const Point&p){y-=p.y;x-=p.x;return*this;}constexpr Point&operator*=(const Point&p){y*=p.y;x*=p.x;return*this;}constexpr Point&operator/=(const Point&p){y/=p.y;x/=p.x;return*this;}constexpr Point&operator%=(const Point&p){y%=p.y;x%=p.x;return*this;}constexpr Point&operator+=(int n){y+=n;x+=n;return*this;}constexpr Point&operator-=(int n){y-=n;x-=n;return*this;}constexpr Point&operator*=(int n){y*=n;x*=n;return*this;}constexpr Point&operator/=(int n){y/=n;x/=n;return*this;}constexpr Point&operator%=(int n){y%=n;x%=n;return*this;}constexpr bool operator==(const Point&p)const{return y==p.y&&x==p.x;}constexpr bool operator!=(const Point&p)const{return y!=p.y||x!=p.x;}bool operator<(const Point&p)const{return to_i()<p.to_i();}bool operator<=(const Point&p)const{return to_i()<=p.to_i();}bool operator>(const Point&p)const{return to_i()>p.to_i();}bool operator>=(const Point&p)const{return to_i()>=p.to_i();}constexpr bool in_range(int height,int width)const{return 0<=y&&y<height&&0<=x&&x<width;}bool in_range()const{return in_range(H,W);}int to_i()const{return y*W+x;}constexpr Point yx()const{return{y,x};}constexpr std::pair<int,int>pair()const{return{y,x};}constexpr std::pair<int,int>anti_pair()const{return{x,y};}constexpr int manhattan(const Point&p)const{return std::abs(x-p.x)+std::abs(y-p.y);}constexpr int chebyshev(const Point&p)const{return std::max(std::abs(y-p.y),std::abs(x-p.x));}constexpr int distance_square(const Point&p)const{return(y-p.y)*(y-p.y)+(x-p.x)*(x-p.x);}template<class Real>constexpr Real distance(const Point&p)const{return std::sqrt(static_cast<Real>(distance_square(p)));}constexpr Point absolute(const Point&p)const{return absolute(*this-p);}constexpr Point absolute()const{return{std::abs(y),std::abs(x)};}class enumerate_adjacent_helper{std::shared_ptr<Point>p;direction_iterator first,last;class iterator{std::shared_ptr<Point>p;direction_iterator it;public:iterator(std::shared_ptr<Point>_p,direction_iterator _it): p(_p),it(_it){}Point operator*()const{return*p+*it;}iterator&operator++(){++it;return*this;}bool operator!=(iterator other)const{return it!=other.it;}};public:enumerate_adjacent_helper(std::shared_ptr<Point>_p,direction_iterator _first,direction_iterator _last): p(_p),first(_first),last(_last){}iterator begin()const{return iterator(p,first);}iterator end()const{return iterator(p,last);}};auto enumerate_adjacent(direction_iterator first,direction_iterator last)const{return enumerate_adjacent_helper(std::make_shared<Point>(*this),first,last);}auto adj4()const{return enumerate_adjacent(direction.begin()+1,direction.begin()+5);}auto adj4_and_this()const{return enumerate_adjacent(direction.begin(),direction.begin()+5);}auto adjacent8()const{return enumerate_adjacent(direction.begin()+1,direction.begin()+9);}auto adj8_and_this()const{return enumerate_adjacent(direction.begin(),direction.begin()+9);}class enumerate_adj_in_range_helper{std::shared_ptr<Point>p;direction_iterator first,last;class sentinel{};class iterator{std::shared_ptr<Point>p;direction_iterator first,last;void increment_until_in_range(){for(;first!=last;++first){if((*p+*first).in_range())return;}}public:iterator(std::shared_ptr<Point>_p,direction_iterator _first,direction_iterator _last): p(_p),first(_first),last(_last){increment_until_in_range();}Point operator*()const{return*p+*first;}iterator&operator++(){++first;increment_until_in_range();return*this;}bool operator!=([[maybe_unused]] sentinel other)const{return first!=last;}};public:enumerate_adj_in_range_helper(std::shared_ptr<Point>_p,direction_iterator _first,direction_iterator _last): p(_p),first(_first),last(_last){}iterator begin()const{return iterator(p,first,last);}sentinel end()const{return sentinel();}};template<class InputIterator>auto enumerate_adj_in_range(InputIterator first,InputIterator last)const{return enumerate_adj_in_range_helper(std::make_shared<Point>(*this),first,last);}auto adj4_in_range()const{return enumerate_adj_in_range(direction.begin()+1,direction.begin()+5);}auto adj4_and_this_in_range()const{return enumerate_adj_in_range(direction.begin(),direction.begin()+5);}auto adj8_in_range()const{return enumerate_adj_in_range(direction.begin()+1,direction.begin()+9);}auto ajd8_and_this_in_range()const{return enumerate_adj_in_range(direction.begin(),direction.begin()+9);}constexpr Point left()const{return{y,x-1};}constexpr Point right()const{return{y,x+1};}constexpr Point up()const{return{y-1,x};}constexpr Point down()const{return{y+1,x};}Point succ()const{if(x!=W-1){return{y,x+1};}else{return{y+1,0};}}Point pred()const{if(x!=0){return{y,x-1};}else{return{y-1,W-1};}}constexpr Point moved(char c)const{return Point(*this).move(c);}constexpr Point&move(char c){switch(c){case 'L':case 'l':case 'W':case '>':x--;break;case 'R':case 'r':case 'E':case '<':x++;break;case 'U':case 'u':case 'N':case '^':y--;break;case 'D':case 'd':case 'S':case 'v':y++;break;}return*this;}constexpr Point rotate90()const{return{-x,y};}constexpr Point rotate180()const{return{-y,-x};}constexpr Point rotate270()const{return{x,-y};}char to_direction_char(std::string_view lrud="LRUD")const{assert(4<=lrud.size()&&lrud.size()<=5);if(y==0&&x<0){return lrud[0];}else if(y==0&&x>0){return lrud[1];}else if(x==0&&y<0){return lrud[2];}else if(x==0&&y>0){return lrud[3];}else if(lrud.size()==5){return lrud[4];}else{assert(false);}}static Point to_direction(char c,std::string_view lrud="LRUD"){assert(lrud.size()==4);if(c==lrud[0]){return L();}else if(c==lrud[1]){return R();}else if(c==lrud[2]){return U();}else if(c==lrud[3]){return D();}else{return zero();}}static Point to_direction(std::string s,std::string_view lrud="LRUD"){if(s.size()==1){return to_direction(s[0],lrud);}else if(s.size()==2){Point p1=to_direction(s[0],lrud),p2=to_direction(s[1],lrud);assert((p1.x==0)^(p2.x==0));assert((p1.y==0)^(p2.y==0));return p1+p2;}else{assert(false);}}template<class T,class value_type=typename T::value_type::value_type>static std::optional<Point>find(const T&grid,const value_type&val){assert(static_cast<int>(grid.size())==H);for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(grid[i][j]==val){return Point(i,j);}}}return std::nullopt;}template<class T,class Predicate>static std::optional<Point>find_if(const T&grid,Predicate pred){assert(static_cast<int>(grid.size())==H);for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(pred(grid[i][j])){return Point(i,j);}}}return std::nullopt;}template<class T,class value_type=typename T::value_type::value_type>static std::optional<Point>find_one(const T&grid,const value_type&val){assert(static_cast<int>(grid.size())==H);std::optional<Point>result;for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(grid[i][j]==val){assert(!result);result=Point(i,j);}}}return result;}template<class T,class value_type=typename T::value_type::value_type>static std::vector<Point>find_all(const T&grid,const value_type&val){assert(static_cast<int>(grid.size())==H);std::vector<Point>result;for(int i=0;i<H;++i){assert(static_cast<int>(grid[i].size())==W);for(int j=0;j<W;++j){if(grid[i][j]==val){result.emplace_back(i,j);}}}return result;}static auto enumerate_2D_points(){class enumerate_2D_points_helper{public:class iterator{Point p;public:iterator(const Point&_p): p(_p){}Point operator*()const{return p;}iterator&operator++(){p=p.succ();return*this;}iterator&operator--(){p=p.pred();return*this;}bool operator!=(iterator other)const{return p!=other.p;}};iterator begin()const{return iterator(Point(0,0));}iterator end()const{return iterator(Point(H,0));}};return enumerate_2D_points_helper();}friend std::ostream&operator<<(std::ostream&os,const Point&p){return os<<'('<<p.y<<","<<p.x<<')';}friend std::istream&operator>>(std::istream&is,Point&p){return is>>p.y>>p.x;}};const std::vector<Point>Point::direction{Point::zero(),Point::R(),Point::D(),Point::U(),Point::L(),Point::RD(),Point::LU(),Point::RU(),Point::LD()};
#line 4 "a.cpp"
using namespace std;int main(){int h=in,w=in;VVI a=in[h][w];map<int,vector<Point>>points_map;rep(i,h)rep(j,w){points_map[a[i][j]].emplace_back(i,j);}int l=0,r=0;VP edges;for(auto [val,points] : points_map){if(val==0)continue;map<int,int>row,column;for(Point p : points){int ll=row.count(p.y)? row[p.y] :(row[p.y]=l++);int rr=column.count(p.x)? column[p.x] :(column[p.x]=r++);edges.emplace_back(ll,rr);}}BipartiteMatching g(l,r,edges);out(g.solve());}