#ifndef INCLUDE_MODE #define INCLUDE_MODE // #define REACTIVE // #define USE_GETLINE #endif #ifdef INCLUDE_MAIN inline void Solve() { // 入力受け取り。 CEXPR( int , bound_N , 1e5 ); CIN_ASSERT( N , 1 , bound_N ); CEXPR( ll , bound_M , 1e18 ); CIN_ASSERT( M , 2 , bound_M ); CIN_A( T2 , 0 , N , LR ); // 座標圧縮。実装は好きにして良い。 CoordinateCompress cc{}; FOR( i , 0 , N ){ auto& [Li,Ri] = LR[i]; ASSERT( Li , 1 , M ); ASSERT( Ri , Li + 1 , M ); cc.SetL( --Li ); cc.SetL( --Ri ); } M = cc.GetL(); // 辺を計算する関数。 auto edge = [&]( const int& i ){ auto& [Li,Ri] = LR[i]; return vector{ int( Li ) , int( Ri ) }; }; // ホップクロフトカープ法で最大マッチングを計算。実装は好きにして良い。 HopcroftKarp hk{}; auto mm = hk.GetMaximumMatching( N , M , edge ); // 最大マッチングのサイズを出力。 RETURN( mm.size() ); } REPEAT_MAIN(1); #else // INCLUDE_MAIN #ifdef INCLUDE_LIBRARY // https://github.com/p-adic/cpp // VVV ライブラリは以下に挿入する。 // 圧縮用 #define TE template #define TY typename #define US using #define ST static #define AS assert #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define LE length #define PW Power #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define VI virtual #define IS basic_istream #define OS basic_ostream #define ST_AS static_assert #define reMO_CO remove_const #define is_COructible_v is_constructible_v #define rBE rbegin #define reSZ resize // Random（1KB） ll GetRand(CRI Rand_min,CRI Rand_max){AS(Rand_min <= Rand_max);ll AN = time(NULL);RE AN * rand()%(Rand_max + 1 - Rand_min)+ Rand_min;} // Map (2KB) #define DC_OF_HASH(...)struct hash<__VA_ARGS__>{IN size_t OP()(CO __VA_ARGS__& n)CO;}; CL is_ordered{PU:is_ordered()= delete;TE ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE ST CE CO bool value = is_same_v< decltype(Check(declval())),true_type >;}; TE US Set = conditional_t>,unordered_set,conditional_t,set,VO>>; #define DF_OF_AR_FOR_MAP(MAP,OPR)TE IN MAP& OP OPR ## =(MAP& a,CO pair& v){a[v.first]OPR ## = v.second;RE a;}TE IN MAP& OP OPR ## =(MAP& a0,CO MAP& a1){for(auto&[t,u]:a1){a0[t]OPR ## = u;}RE a0;}TE IN MAP OP OPR(MAP a,CO ARG& arg){RE MO(a OPR ## = arg);} #define DF_OF_ARS_FOR_MAP(MAP)DF_OF_AR_FOR_MAP(MAP,+);DF_OF_AR_FOR_MAP(MAP,-);DF_OF_AR_FOR_MAP(MAP,*);DF_OF_AR_FOR_MAP(MAP,/);DF_OF_AR_FOR_MAP(MAP,%); TE US Map = conditional_t>,unordered_map,conditional_t,map,VO>>; DF_OF_ARS_FOR_MAP(map);DF_OF_ARS_FOR_MAP(unordered_map); // Module (6KB) #define DC_OF_CPOINT(POINT)IN CO U& POINT()CO NE #define DC_OF_POINT(POINT)IN U& POINT()NE #define DF_OF_CPOINT(POINT)TE IN CO U& VirtualPointedSet::POINT()CO NE{RE Point();} #define DF_OF_POINT(POINT)TE IN U& VirtualPointedSet::POINT()NE{RE Point();} TE CL UnderlyingSet{PU:US type = U;};TE CL VirtualPointedSet:VI PU UnderlyingSet{PU:VI CO U& Point()CO NE = 0;VI U& Point()NE = 0;DC_OF_CPOINT(Unit);DC_OF_CPOINT(Zero);DC_OF_CPOINT(One);DC_OF_CPOINT(Infty);DC_OF_POINT(init);DC_OF_POINT(root);};TE CL PointedSet:VI PU VirtualPointedSet{PU:U m_b_U;IN PointedSet(U b_u = U());IN CO U& Point()CO NE;IN U& Point()NE;};TE CL VirtualNSet:VI PU UnderlyingSet{PU:VI U Transfer(CO U& u)= 0;IN U Inverse(CO U& u);};TE CL AbstractNSet:VI PU VirtualNSet{PU:F_U m_f_U;IN AbstractNSet(F_U f_U);IN AbstractNSet& OP=(CO AbstractNSet&)NE;IN U Transfer(CO U& u);};TE CL VirtualMagma:VI PU UnderlyingSet{PU:VI U Product(U u0,CO U& u1)= 0;IN U Sum(U u0,CO U& u1);};TE CL AdditiveMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL MultiplicativeMagma:VI PU VirtualMagma{PU:IN U Product(U u0,CO U& u1);};TE CL AbstractMagma:VI PU VirtualMagma{PU:M_U m_m_U;IN AbstractMagma(M_U m_U);IN AbstractMagma& OP=(CO AbstractMagma&)NE;IN U Product(U u0,CO U& u1);}; TE IN PointedSet::PointedSet(U b_U):m_b_U(MO(b_U)){}TE IN CO U& PointedSet::Point()CO NE{RE m_b_U;}TE IN U& PointedSet::Point()NE{RE m_b_U;}DF_OF_CPOINT(Unit);DF_OF_CPOINT(Zero);DF_OF_CPOINT(One);DF_OF_CPOINT(Infty);DF_OF_POINT(init);DF_OF_POINT(root);TE IN AbstractNSet::AbstractNSet(F_U f_U):m_f_U(MO(f_U)){ST_AS(is_invocable_r_v);}TE IN AbstractNSet& AbstractNSet::operator=(CO AbstractNSet&)NE{RE *TH;}TE IN U AbstractNSet::Transfer(CO U& u){RE m_f_U(u);}TE IN U VirtualNSet::Inverse(CO U& u){RE Transfer(u);}TE IN AbstractMagma::AbstractMagma(M_U m_U):m_m_U(MO(m_U)){ST_AS(is_invocable_r_v);}TE IN AbstractMagma& AbstractMagma::OP=(CO AbstractMagma&)NE{RE *TH;}TE IN U AdditiveMagma::Product(U u0,CO U& u1){RE MO(u0 += u1);}TE IN U MultiplicativeMagma::Product(U u0,CO U& u1){RE MO(u0 *= u1);}TE IN U AbstractMagma::Product(U u0,CO U& u1){RE m_m_U(MO(u0),u1);}TE IN U VirtualMagma::Sum(U u0,CO U& u1){RE Product(MO(u0),u1);} TE CL VirtualMonoid:VI PU VirtualMagma,VI PU VirtualPointedSet{};TE CL AdditiveMonoid:VI PU VirtualMonoid,PU AdditiveMagma,PU PointedSet{};TE CL MultiplicativeMonoid:VI PU VirtualMonoid,PU MultiplicativeMagma,PU PointedSet{PU:IN MultiplicativeMonoid(U e_U);};TE CL AbstractMonoid:VI PU VirtualMonoid,PU AbstractMagma,PU PointedSet{PU:IN AbstractMonoid(M_U m_U,U e_U);}; TE IN MultiplicativeMonoid::MultiplicativeMonoid(U e_U):PointedSet(MO(e_U)){}TE IN AbstractMonoid::AbstractMonoid(M_U m_U,U e_U):AbstractMagma(MO(m_U)),PointedSet(MO(e_U)){} TE CL VirtualGroup:VI PU VirtualMonoid,VI PU VirtualPointedSet,VI PU VirtualNSet{};TE CL AdditiveGroup:VI PU VirtualGroup,PU AdditiveMonoid{PU:IN U Transfer(CO U& u);};TE CL AbstractGroup:VI PU VirtualGroup,PU AbstractMonoid,PU AbstractNSet{PU:IN AbstractGroup(M_U m_U,U e_U,I_U i_U);}; TE IN AbstractGroup::AbstractGroup(M_U m_U,U e_U,I_U i_U):AbstractMonoid(MO(m_U),MO(e_U)),AbstractNSet(MO(i_U)){}TE IN U AdditiveGroup::Transfer(CO U& u){RE -u;} TE CL VirtualRSet:VI PU UnderlyingSet{PU:VI U Action(CO R& r,U u)= 0;IN U PW(U u,CO R& r);IN U ScalarProduct(CO R& r,U u);};TE CL RegularRSet:VI PU VirtualRSet,PU MAGMA{PU:IN RegularRSet(MAGMA magma);IN U Action(CO U& r,U u);};TE RegularRSet(MAGMA magma)-> RegularRSet,MAGMA>;TE CL AbstractRSet:VI PU VirtualRSet{PU:O_U m_o_U;IN AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U);IN AbstractRSet& OP=(CO AbstractRSet&)NE;IN U Action(CO R& r,U u);};TE CL AbstractModule:PU AbstractRSet,PU GROUP{PU:IN AbstractModule(CO R& dummy,O_U o_U,GROUP M);};TE AbstractModule(CO R& dummy,O_U o_U,GROUP M)-> AbstractModule,O_U,GROUP>;TE CL Module:VI PU VirtualRSet,PU AdditiveGroup{PU:IN U Action(CO R& r,U u);}; TE IN RegularRSet::RegularRSet(MAGMA magma):MAGMA(MO(magma)){}TE IN AbstractRSet::AbstractRSet(CO R& dummy0,CO U& dummy1,O_U o_U):m_o_U(MO(o_U)){ST_AS(is_invocable_r_v);}TE IN AbstractModule::AbstractModule(CO R& dummy,O_U o_U,GROUP M):AbstractRSet(dummy,M.One(),MO(o_U)),GROUP(MO(M)){ST_AS(is_same_v>);}TE IN AbstractRSet& AbstractRSet::OP=(CO AbstractRSet&)NE{RE *TH;}TE IN U RegularRSet::Action(CO U& r,U u){RE TH->Product(r,MO(u));}TE IN U AbstractRSet::Action(CO R& r,U u){RE m_o_U(r,MO(u));}TE IN U Module::Action(CO R& r,U u){RE MO(u *= r);}TE IN U VirtualRSet::PW(U u,CO R& r){RE Action(r,MO(u));}TE IN U VirtualRSet::ScalarProduct(CO R& r,U u){RE Action(r,MO(u));} // Graph (5KB) TE CL VirtualGraph:VI PU UnderlyingSet{PU:VI R1 Enumeration(CRI i)= 0;IN R2 Enumeration_inv(CO T& t);TE IN R2 Enumeration_inv(CO PATH& p);IN VO Reset();VI CRI SZ()CO NE = 0;VI E& edge()NE = 0;VI ret_t Edge(CO T& t)= 0;TE IN ret_t Edge(CO PATH& p);ST IN CO T& Vertex(CO T& t)NE;TE ST IN CO T& Vertex(CO PATH& e)NE;VI R2 Enumeration_inv_Body(CO T& t)= 0;};TE CL EdgeImplimentation:VI PU VirtualGraph{PU:int m_SZ;E m_edge;IN EdgeImplimentation(CRI SZ,E edge);IN CRI SZ()CO NE;IN E& edge()NE;IN ret_t Edge(CO T& t);};TE CL Graph:PU EdgeImplimentation{PU:IN Graph(CRI SZ,E edge);IN CRI Enumeration(CRI i);TE IN Graph GetGraph(F edge)CO;IN CRI Enumeration_inv_Body(CRI t);};TE CL EnumerationGraph:PU EdgeImplimentation,ret_t,E>{PU:Enum_T m_enum_T;Enum_T_inv m_enum_T_inv;IN EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv,E edge);IN ret_t Enumeration(CRI i);TE IN EnumerationGraph GetGraph(F edge)CO;IN ret_t Enumeration_inv_Body(CO T& t);};TE EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv,E edge)-> EnumerationGraph()(0)),Enum_T,Enum_T_inv,E>;TE CL MemorisationGraph:PU EdgeImplimentation{PU:int m_LE;VE m_memory;Map m_memory_inv;IN MemorisationGraph(CRI SZ,CO T& dummy,E edge);IN T Enumeration(CRI i);IN VO Reset();TE IN MemorisationGraph GetGraph(F edge)CO;IN CRI Enumeration_inv_Body(CO T& t);}; TE IN EdgeImplimentation::EdgeImplimentation(CRI SZ,E edge):m_SZ(SZ),m_edge(MO(edge)){ST_AS(is_COructible_v && is_COructible_v && is_invocable_v);}TE IN Graph::Graph(CRI SZ,E edge):EdgeImplimentation(SZ,MO(edge)){}TE IN EnumerationGraph::EnumerationGraph(CRI SZ,Enum_T enum_T,Enum_T_inv enum_T_inv,E edge):EdgeImplimentation,ret_t,E>(SZ,MO(edge)),m_enum_T(MO(enum_T)),m_enum_T_inv(MO(enum_T_inv)){}TE IN MemorisationGraph::MemorisationGraph(CRI SZ,CO T& dummy,E edge):EdgeImplimentation(SZ,MO(edge)),m_LE(),m_memory(),m_memory_inv(){ST_AS(is_invocable_v);}TE IN CRI Graph::Enumeration(CRI i){RE i;}TE IN ret_t EnumerationGraph::Enumeration(CRI i){RE m_enum_T(i);}TE IN T MemorisationGraph::Enumeration(CRI i){AS(0 <= i && i < m_LE);RE m_memory[i];}TE IN R2 VirtualGraph::Enumeration_inv(CO T& t){RE Enumeration_inv_Body(t);}TE TE IN R2 VirtualGraph::Enumeration_inv(CO PATH& p){RE Enumeration_inv_Body(get<0>(p));}TE IN CRI Graph::Enumeration_inv_Body(CRI i){RE i;}TE IN ret_t EnumerationGraph::Enumeration_inv_Body(CO T& t){RE m_enum_T_inv(t);}TE IN CRI MemorisationGraph::Enumeration_inv_Body(CO T& t){if(m_memory_inv.count(t)== 0){AS(m_LE < TH->SZ());m_memory.push_back(t);RE m_memory_inv[t]= m_LE++;}RE m_memory_inv[t];}TE VO VirtualGraph::Reset(){}TE IN VO MemorisationGraph::Reset(){m_LE = 0;m_memory.clear();m_memory_inv.clear();}TE IN CRI EdgeImplimentation::SZ()CO NE{RE m_SZ;}TE IN E& EdgeImplimentation::edge()NE{RE m_edge;}TE IN ret_t EdgeImplimentation::Edge(CO T& t){RE m_edge(t);}TE TE IN ret_t VirtualGraph::Edge(CO PATH& p){RE Edge(get<0>(p));}TE TE IN Graph Graph::GetGraph(F edge)CO{RE Graph(TH->SZ(),MO(edge));}TE TE IN EnumerationGraph EnumerationGraph::GetGraph(F edge)CO{RE EnumerationGraph(TH->SZ(),m_enum_T,m_enum_T_inv,MO(edge));}TE TE IN MemorisationGraph MemorisationGraph::GetGraph(F edge)CO{RE MemorisationGraph(TH->SZ(),MO(edge));}TE IN CO T& VirtualGraph::Vertex(CO T& t)NE{RE t;}TE TE IN CO T& VirtualGraph::Vertex(CO PATH& e)NE{RE Vertex(get<0>(e));} TE CL CoordinateCompress{PU:set m_r;VE m_l;IN CoordinateCompress();IN VO SetR(INT t);TE TY V > IN VO SetR(V a);pair,unordered_map> GetR();IN VO clearR();IN VO SetL(INT& t);TE TY V > IN VO SetL(V& a);int GetL();IN VO clearL();}; TE IN CoordinateCompress::CoordinateCompress():m_r(),m_l(){}TE IN VO CoordinateCompress::SetR(INT t){m_r.insert(MO(t));}TE TE TY V > IN VO CoordinateCompress::SetR(V a){for(auto& t:a){SetR(MO(t));}}TE pair,unordered_map> CoordinateCompress::GetR(){pair,unordered_map> AN{};AN.first.reSZ(m_r.SZ());int i = 0;for(auto t:m_r){AN.first[i]= t;AN.second[t]= i++;}RE AN;}TE IN VO CoordinateCompress::clearR(){m_r.clear();}TE IN VO CoordinateCompress::SetL(INT& t){m_l.push_back(&t);}TE TE TY V > IN VO CoordinateCompress::SetL(V& a){for(auto& t:a){SetL(t);}}TE int CoordinateCompress::GetL(){int i = -1;if(!m_l.empty()){auto comp =[](INT* CO& p0,INT* CO& p1){RE *p0 < *p1;};sort(m_l.BE(),m_l.end(),comp);INT temp = *(m_l[0])- 1;for(auto p:m_l){*p = temp == *p?i:(temp = *p,++i);}}RE ++i;}TE IN VO CoordinateCompress::clearL(){m_l.clear();} TE CL VirtualBreadthFirstSearch{PU:GRAPH& m_G;T m_not_found;bool m_initialised;LI m_next;VE m_found;VE m_prev;IN VirtualBreadthFirstSearch(GRAPH& G,CO T& not_found);TE IN VirtualBreadthFirstSearch(GRAPH& G,CO T& not_found,Arg&& init);IN VO Initialise();IN VO Initialise(CO T& init);IN VO Initialise(LI inits);IN VO Shift(CO T& init);IN VO Shift(LI inits);IN CRI SZ()CO NE;IN VE::reference found(CO T& t);IN CO T& prev(CO T& t);IN T Next();TE auto GetDistance()-> enable_if_t().edge())>>,Map>;TE auto GetDistance()-> enable_if_t().edge())>>,VE>;pair,int> GetConnectedComponent();VI VO Push(LI& next,CO T& t)= 0;TE IN VO Push(LI& next,CO PATH& p);}; TE IN VirtualBreadthFirstSearch::VirtualBreadthFirstSearch(GRAPH& G,CO T& not_found):m_G(G),m_not_found(not_found),m_initialised(false),m_next(),m_found(),m_prev(){ST_AS(is_same_v,T>);}TE TE IN VirtualBreadthFirstSearch::VirtualBreadthFirstSearch(GRAPH& G,CO T& not_found,Arg&& init):VirtualBreadthFirstSearch(G,not_found){Initialise(forward(init));}TE IN VO VirtualBreadthFirstSearch::Initialise(){m_initialised = true;CRI V = SZ();m_next.clear();m_found = VE(V);m_prev = VE(V,m_not_found);}TE IN VO VirtualBreadthFirstSearch::Initialise(CO T& init){auto&& i = m_G.Enumeration_inv(init);AS(0 <= i && i < SZ());Initialise();m_next.push_back(init);m_found[i]= true;}TE IN VO VirtualBreadthFirstSearch::Initialise(LI inits){Initialise();m_next = MO(inits);CRI V = SZ();for(auto& u:m_next){auto&& i = m_G.Enumeration_inv(u);AS(0 <= i && i < V);m_found[i]= true;}}TE IN VO VirtualBreadthFirstSearch::Shift(CO T& init){if(m_initialised){CRI V = SZ();auto&& i = m_G.Enumeration_inv(init);AS(0 <= i && i < V);m_next.clear();if(! m_found[i]){m_next.push_back(init);m_found[i]= true;}}else{Initialise(init);}}TE IN VO VirtualBreadthFirstSearch::Shift(LI inits){if(m_initialised){m_next.clear();CRI V = SZ();for(auto& u:m_next){auto&& i = m_G.Enumeration_inv(u);AS(0 <= i && i < V);if(! m_found[i]){m_next.push_back(u);m_found[i]= true;}}}else{Initialise(MO(inits));}}TE IN CRI VirtualBreadthFirstSearch::SZ()CO NE{RE m_G.SZ();}TE IN VE::reference VirtualBreadthFirstSearch::found(CO T& t){auto&& i = m_G.Enumeration_inv(t);AS(0 <= i && i < SZ());if(!m_initialised){Initialise();}RE m_found[i];}TE IN CO T& VirtualBreadthFirstSearch::prev(CO T& t){auto&& i = m_G.Enumeration_inv(t);AS(0 <= i && i < SZ());if(!m_initialised){Initialise();}RE m_prev[i];}TE IN T VirtualBreadthFirstSearch::Next(){if(m_next.empty()){RE m_not_found;}CO T t_curr = m_next.front();m_next.pop_front();auto&& edge = m_G.Edge(t_curr);for(auto& t:edge){auto&& i = m_G.Enumeration_inv(t);auto&& found_i = m_found[i];if(! found_i){Push(m_next,t);m_prev[i]= t_curr;found_i = true;}}RE t_curr;}TE TE auto VirtualBreadthFirstSearch::GetDistance()-> enable_if_t().edge())>>,Map>{Map AN{};for(auto IT = m_next.BE(),EN = m_next.EN();IT != EN;IT++){AN[*IT]= 0;}T t;WH((t = Next())!= m_not_found){if(AN.count(t) == 0){AN[t]= AN[m_prev[m_G.Enumeration_inv(t)]]+ 1;}}RE AN;}TE TE auto VirtualBreadthFirstSearch::GetDistance()-> enable_if_t().edge())>>,VE>{VE AN(SZ(),-1);for(auto IT = m_next.BE(),EN = m_next.EN();IT != EN;IT++){AN[m_G.Enumeration_inv(*IT)]= 0;}T t;WH((t = Next())!= m_not_found){auto&& i = m_G.Enumeration_inv(t);int& AN_i = AN[i];AN_i == -1?AN_i = AN[m_G.Enumeration_inv(m_prev[i])]+ 1:AN_i;}RE AN;}TE pair,int> VirtualBreadthFirstSearch::GetConnectedComponent(){ST_AS(!is_same_v>);CRI V = SZ();VE cc_num(V,-1);int count = 0;for(int i = 0;i < V;i++){if(cc_num[i]== -1){Shift(m_G.Enumeration(i));T t = Next();if(t != m_not_found){WH(t != m_not_found){cc_num[m_G.Enumeration_inv(t)]= count;t = Next();}count++;}}}RE{MO(cc_num),MO(count)};}TE TE IN VO VirtualBreadthFirstSearch::Push(LI& next,CO PATH& p){Push(next,get<0>(p));} TE CL BreadthFirstSearch:PU VirtualBreadthFirstSearch{PU:TE IN BreadthFirstSearch(GRAPH& G,CO T& not_found,Args&&... args);IN VO Push(LI& next,CO T& t);}; TE TE IN BreadthFirstSearch::BreadthFirstSearch(GRAPH& G,CO T& not_found,Args&&... args):VirtualBreadthFirstSearch(G,not_found,forward(args)...){}TE IN VO BreadthFirstSearch::Push(LI& next,CO T& t){next.push_back(t);} // (S,T,edge)が二部グラフである場合のみサポート。 // edgeのサイズをeと置く。最大二部マッチング問題を // 時間計算量O((S+T+e)√(S+T)) // 空間計算量O(S+T+e) // で解く。特に // - eがO(ST)の時は時間計算量O(ST√(S+T)) // - eがO(S+T)の時は時間計算量O((S+T)√(S+T)) // で解く。 class HopcroftKarp { public: template vector> GetMaximumMatching( const int& S , const int& T , Edge edge ); }; template vector> HopcroftKarp::GetMaximumMatching( const int& S , const int& T , Edge edge ) { static_assert( is_invocable_r_v,Edge,const int&> ); unordered_set unchosen_source{}; vector prev( T , -1 ); for( int s = 0 ; s < S ; s++ ){ unchosen_source.insert( s ); } // BFSのコンストラクタに渡す。 // (1) w=0の時は、未選択なSの頂点vectorを返す。 // (2) 0 answer{}; if( w == 0 ){ for( auto& us : unchosen_source ){ answer.push_back( 1 + us ); } } else if( w <= S ){ auto&& edge_w = edge( w - 1 ); answer.reserve( edge_w.size() ); for( auto& t : edge_w ){ answer.push_back( 1 + S + t ); } } else { const int t = w - 1 - S; assert( t < T ); const int& s = prev[t]; if( s != -1 ){ assert( 0 <= s && s < S ); answer.push_back( 1 + s ); } } return answer; }; Graph graph{ 1 + S + T , move( edge_shifted ) }; BreadthFirstSearch bfs{ graph , -1 }; vector chosen_source( S ); vector chosen_target( T ); vector> chosen_edge( S ); vector depth( 1 + S + T ); int depth_min = -1; vector root( S + T ); vector new_chosen_target{ 0 }; int v , w; bool found; while( ! new_chosen_target.empty() ){ new_chosen_target.clear(); bfs.Initialise( 0 ); v = bfs.Next(); found = false; while( ( v = bfs.Next() ) != -1 ){ w = bfs.prev( v ); int& depth_v = depth[v] = depth[w] + 1; if( found && depth_v > depth_min ){ break; } if( w == 0 ){ const int s = v - 1; assert( 0 <= s && s < S ); root[s] = s; } else { root[v - 1] = root[w - 1]; } if( ( depth_v & 1 ) == 0 ){ const int t = v - 1 - S; assert( 0 <= t && t < T ); auto&& chosen_target_t = chosen_target[t]; if( !chosen_target_t ){ const int& s = root[v - 1]; assert( 0 <= s && s < S ); auto&& chosen_source_s = chosen_source[s]; if( !chosen_source_s ){ chosen_source_s = true; chosen_target_t = true; new_chosen_target.push_back( v ); if( !found ){ found = true; depth_min = depth_v; } } } } } for( auto& nct : new_chosen_target ){ int* p[2] = { &w , &v }; int*& p0 = p[0]; int*& p1 = p[1]; v = nct; while( ( w = bfs.prev( v ) ) != 0 ){ const int s = *p0 - 1; const int t = *p1 - 1 - S; assert( 0 <= s && s < S && 0 <= t && t < T ); if( chosen_edge[s][t] ^= true ){ prev[t] = s; } swap( w , v ); swap( p0 , p1 ); } const int s = v - 1; assert( 0 <= s && s < S && unchosen_source.count( s ) == 1 ); unchosen_source.erase( s ); } } vector> answer{}; for( int t = 0 ; t < T ; t++ ){ const int& s = prev[t]; if( s != -1 ){ assert( 0 <= s && s < S && 0 <= t && t < T ); answer.push_back( { s , t } ); } } return answer; } // AAA ライブラリは以上に挿入する。 #define INCLUDE_MAIN #include __FILE__ #else // INCLUDE_LIBRARY #ifdef DEBUG #define _GLIBCXX_DEBUG #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE2 ) #define SIGNAL signal( SIGABRT , &AlertAbort ); #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize ( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define SIGNAL #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 ) #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CERR( ... ) #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL #define CERR_A( N , A ) #define COUT_A( N , A ) OUTPUT_ARRAY( cout , N , A ) << ENDL #define CERR_ITR( A ) #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL #endif #ifdef REACTIVE #define ENDL endl #else #define ENDL "\n" #endif #ifdef USE_GETLINE #define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); } #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ ) #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ ) #else #define SET_LL( A ) cin >> A #define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ ) #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); } #define CIN_A( LL , I , N , ... ) VE __VA_ARGS__; SET_A( I , N , __VA_ARGS__ ); #endif #include using namespace std; #define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; CEXPR( int , bound_test_case_num , BOUND ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ CERR( "テストケースの個数を入力してください。" ); SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } } #define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now() #define CURRENT_TIME static_cast( chrono::duration_cast( chrono::system_clock::now() - watch ).count() / 1000.0 ) #define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 ) #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX ) #define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); } #define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX ) #define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( decldecay_t( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( decldecay_t( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( decldecay_t( INITIAL ) VAR = INITIAL ; VAR + 1 > FINAL ; VAR -- ) #define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN() #define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define RUN( VAR , ARRAY ) for( auto&& VAR : ARRAY ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ) #define RETURN( ... ) COUT( __VA_ARGS__ ); return // 型のエイリアス #define decldecay_t( VAR ) decay_t template using ret_t = decltype( declval()( declval()... ) ); template