#line 1 "/home/yuruhiya/programming/library/template_mini.cpp" #include #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/template_mini.cpp" #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;using VVB=std::vector;using VI=std::vector;u\ sing VVI=std::vector;using VL=std::vector;using VVL=std::vector;using VS=std::vector;using VD=s\ td::vector;using PII=std::pair;using VP=std::vector;using PLL=std::pair;using VPL=std::vector;templateusing PQ=std::priority_queue;templateusing PQS=std::priority_queue,std\ ::greater>;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; #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #define fwrite_unlocked fwrite #define fflush_unlocked fflush #endif class Scanner{templatestruct has_scan:std::false_type{};templatestruct has_scan().template scan())>>: std::true_type{};public:static int gc(){return getchar_unlock\ ed();}static char next_char(){char c;scan(c);return c;}templatestatic void scan(T&v){if(has_scan::value){v.t\ emplate scan();}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::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=nex\ t_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=g\ c();}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_ch\ ar();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;}templatestatic void scan(std::pair&v){scan(v.fi\ rst);scan(v.second);}template,std::nullptr_t> =nullptr>static void scan\ (std::vector&v){for(auto&e:v)scan(e);}template,std::nullptr_t> =nullp\ tr>static void scan(std::vector&v){for(auto e:v)scan(e);}private:templatestatic void scan_tu\ ple_impl(T&v){if constexpr(N){scan(std::get(v));scan_tuple_impl(v);}}public:templatestatic void scan(std::tuple&v){scan_tuple_impl(v);}private:struct Read2DVectorHelper{std::size_t h,w;Read2DVe\ ctorHelper(std::size_t _h,std::size_t _w): h(_h),w(_w){}templateoperator std::vector>(){std::vec\ tor vector(h,std::vector(w));scan(vector);return vector;}};struct ReadVectorHelper{std::size_t n;ReadVectorHelper(std\ ::size_t _n): n(_n){}templateoperator std::vector(){std::vectorvector(n);scan(vector);return vector;}auto\ operator[](std::size_t m){return Read2DVectorHelper(n,m);}};public:templateT read()const{T result;scan(result)\ ;return result;}templateauto read(std::size_t n)const{std::vectorresult(n);scan(result);return result;}templ\ ateauto read(std::size_t h,std::size_t w)const{std::vector result(h,std::vector(w));scan(result);return resu\ lt;}std::string read_line()const{std::string v;for(char c=gc();c!='\n'&&c!='\0';c=gc())v+=c;return v;}templateo\ perator T()const{return read();}int operator--(int)const{return read()-1;}auto operator[](std::size_t n)const{re\ turn ReadVectorHelper(n);}auto operator[](const std::pair&nm)const{return Read2DVectorHelper(nm\ .first,nm.second);}void operator()()const{}templatevoid operator()(H&&h,T&&... t)const{scan(h);opera\ tor()(std::forward(t)...);}private:templateclass,class...>struct Column;templateclass V,class Head,class... Tail>struct Column{templateusing vec=V,Arg\ s...>;using type=typename Column::type;};templateclass V>struct Column{using type=V<>\ ;};templateusing column_t=typename Column::type;templatevoid colum\ n_impl(T&t)const{if constexpr(N){auto&vec=std::get(t);using V=typename std::remove_reference_t::value_type;vec.push_back(read());column_impl(t);}}public:templateauto column(std::siz\ e_t h)const{column_tresult;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__) 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};Sepa\ rator separator{space};private:templatestruct has_print:std::false_type{};templatestruct ha\ s_print().print(std::declval()))>>: std::true_type{};public:void print(i\ nt v)const{char buf[12]{};if(auto [ptr,e]=std::to_chars(std::begin(buf),std::end(buf),v);e==std::errc{}){print(std::stri\ ng_view(buf,ptr-buf));}else{assert(false);}}void print(long long v)const{char buf[21]{};if(auto [ptr,e]=std::to_chars(st\ d::begin(buf),std::end(buf),v);e==std::errc{}){print(std::string_view(buf,ptr-buf));}else{assert(false);}}void print(boo\ l v)const{print(v?bool_str.t:bool_str.f);}void print(std::vector::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)co\ nst{std::printf("%.20Lf",v);}template::value,std::nullptr_t> =nullptr>void print(c\ onst T&v)const{v.print(*this);}template::value,std::nullptr_t> =nullptr>void prin\ t(const T&v)const{std::cout<void print(const std::pair&v)const{print(v.first);print(se\ parator.div);print(v.second);}templatevoid print(const std::optional&v)const{print(*v);}templatevoid print_range(const InputIterater&begin,const InputIterater&end)const{for(InputIterater i=begin;i!=end;++i){\ if(i!=begin)print(separator.sep);print(*i);}}templatevoid print(const std::vector&v)const{print_range(v.begi\ n(),v.end());}templatevoid print(const std::array&v)const{print_range(v.begin(),v.end());}te\ mplatevoid print(const std::vector>&v)const{for(std::size_t i=0;iPrinter&operat\ or()(Head&&head){print(head);print(separator.last);return*this;}templatePrinter&operator()(Hea\ d&&head,Tail&&... tail){print(head);print(separator.sep);return operator()(std::forward(tail)...);}templatePrinter&flag(bool f,Args&&... args){if(f){return operator()(std::forward(args)...);}else{return*this;}}tem\ platePrinter&range(const InputIterator&begin,const InputIterator&end){print_range(begin,end);print(\ separator.last);return*this;}templatePrinter&range(const Container&a){range(a.begin(),a.end());return*t\ his;}templatevoid exit(T&&... t){operator()(std::forward(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_s\ tr=BoolString(t,f);return*this;}}out;templateclass step_iterator{public:using value_type=T;using difference_typ\ e=T;using iterator_category=std::random_access_iterator_tag;using reference=T&;using pointer=T*;private:value_type start\ _m,size_m,step_m,index_m;public:constexpr step_iterator(): start_m(value_type()),size_m(value_type()),step_m(value_type(\ )),index_m(0){}constexpr step_iterator(value_type _start,value_type _size,value_type _step): start_m(_start),size_m(_siz\ e),step_m(_step),index_m(0){}value_type operator*()const noexcept{return value();}step_iterator&operator++()noexcept{++i\ ndex_m;return*this;}step_iterator&operator++(int)noexcept{auto tmp=*this;++*this;return tmp;}step_iterator&operator--()n\ oexcept{--index_m;return*this;}step_iterator&operator--(int)noexcept{auto tmp=*this;--*this;return tmp;}step_iterator&op\ erator+=(difference_type n){index_m+=n;return*this;}step_iterator operator+(difference_type n)const{return step_iterator\ (*this)+=n;}friend step_iterator operator+(difference_type n,step_iterator i){return i+n;}step_iterator&operator-=(diffe\ rence_type n){index_m-=n;return*this;}step_iterator operator-(difference_type n)const{return step_iterator(*this)-=n;}fr\ iend step_iterator operator-(difference_type n,step_iterator i){return i-n;}difference_type operator-(const step_iterato\ r&other)const{assert(start_m==other.start_m);assert(size_m==other.size_m);assert(step_m==other.step_m);return index_m-ot\ her.index_m;}bool operator==(const step_iterator&other)const noexcept{return value()==other.value();}bool operator!=(con\ st step_iterator&other)const noexcept{return value()!=other.value();}bool operator<(const step_iterator&other)const noex\ cept{return value()(const step_iterator&other)const noexcept{return value()>other.value();}bool operator>=(const step_iter\ ator&other)const noexcept{return value()>=other.value();}constexpr value_type value()const noexcept{return start_m+step_\ m*index_m;}};templateclass Step{public:using value_type=T;using iterator=step_iterator;private:valu\ e_type start_m,size_m,step_m;public:constexpr Step(value_type _start,value_type _size,value_type _step): start_m(_start)\ ,size_m(std::max(0,_size)),step_m(_step){}constexpr iterator begin()const{return iterator(start_m,size_m,ste\ p_m);}constexpr iterator end()const{return iterator(start_m,size_m,step_m)+size_m;}constexpr value_type start()const{ret\ urn start_m;}constexpr value_type size()const{return size_m;}constexpr value_type step()const{return step_m;}constexpr v\ alue_type sum()const{return start()*size()+step()*(size()*(size()-1)/2);}operator std::vector()const{return \ to_a();}auto to_a()const{std::vectorresult;result.reserve(size());for(auto i :*this){result.push_back(i);}re\ turn result;}};templateconstexpr auto upto(T from,T to,bool exclusive=true){return Step(from,to-from+exclusi\ ve,1);}templateconstexpr auto downto(T from,T to,bool exclusive=true){return Step(from,from-to+exclusive,-1)\ ;}templateconstexpr auto times(T n,bool exclusive=false){return Step(0,n+static_cast(exclusive),1);}templ\ atestruct Callable{F func;Callable(const F&f): func(f){}};templateauto operator|(const T&v,con\ st Callable&c){return c.func(v);}struct Sort_impl{templateauto operator()(F&&f){return Callable([&](auto v){\ std::sort(std::begin(v),std::end(v),f);return v;});}templatefriend auto operator|(T v,[[maybe_unused]] const So\ rt_impl&c){std::sort(std::begin(v),std::end(v));return v;}}Sort;struct SortBy_impl{templateauto operator()(F&&f\ ){return Callable([&](auto v){std::sort(std::begin(v),std::end(v),[&](const auto&i,const auto&j){return f(i)auto operator()(F&&f){return Callable([&](auto v){std::sort(rbegin(\ v),rend(v),f);return v;});}templatefriend auto operator|(T v,[[maybe_unused]] const RSort_impl&c){std::sort(rbe\ gin(v),rend(v));return v;}}RSort;struct RSortBy_impl{templateauto operator()(F&&f){return Callable([&](auto v){\ std::sort(std::begin(v),std::end(v),[&](const auto&i,const auto&j){return f(i)>f(j);});return v;});}}RSortBy;struct Reve\ rse_impl{templatefriend auto operator|(T v,const Reverse_impl&c){std::reverse(std::begin(v),std::end(v));return\ v;}}Reverse;struct Unique_impl{templatefriend auto operator|(T v,const Unique_impl&c){v.erase(std::unique(std:\ :begin(v),std::end(v),std::end(v)));return v;}templateauto operator()(F&&f){return Callable([&](auto v)\ {v.erase(std::unique(std::begin(v),std::end(v),f),std::end(v));return v;});}}Unique;struct Uniq_impl{templatefr\ iend auto operator|(T v,const Uniq_impl&c){std::sort(std::begin(v),std::end(v));v.erase(std::unique(std::begin(v),std::e\ nd(v)),std::end(v));return v;}}Uniq;struct Rotate_impl{auto operator()(int&&left){return Callable([&](auto v){int s=stat\ ic_cast(std::size(v));assert(-s<=left&&left<=s);if(0<=left){std::rotate(std::begin(v),std::begin(v)+left,std::end(v\ ));}else{std::rotate(std::begin(v),std::end(v)+left,std::end(v));}return v;});}}Rotate;struct Max_impl{template\ auto operator()(F&&f){return Callable([&](auto v){return*std::max_element(std::begin(v),std::end(v),f);});}templatefriend auto operator|(T v,const Max_impl&c){return*std::max_element(std::begin(v),std::end(v));}}Max;struct Min_impl\ {templateauto operator()(F&&f){return Callable([&](auto v){return*std::min_element(std::begin(v),std::end(v),f)\ ;});}templatefriend auto operator|(T v,const Min_impl&c){return*std::min_element(std::begin(v),std::end(v));}}M\ in;struct MaxPos_impl{templatefriend auto operator|(T v,const MaxPos_impl&c){return std::max_element(std::begin\ (v),std::end(v))-std::begin(v);}}MaxPos;struct MinPos_impl{templatefriend auto operator|(T v,const MinPos_impl&\ c){return std::min_element(std::begin(v),std::end(v))-std::begin(v);}}MinPos;struct MaxBy_impl{templateauto ope\ rator()(F&&f){return Callable([&](auto v){auto max_it=std::begin(v);auto max_val=f(*max_it);for(auto it=std::next(std::b\ egin(v));it!=std::end(v);++it){if(auto val=f(*it);max_valauto operator()(F&&f){return Callable([&](auto v){auto min_it=std::begin(v);auto min_val=f(*m\ in_it);for(auto it=std::next(std::begin(v));it!=std::end(v);++it){if(auto val=f(*it);min_val>val){min_it=it;min_val=val;\ }}return*min_it;});}}MinBy;struct MaxOf_impl{templateauto operator()(F&&f){return Callable([&](auto v){auto max\ _val=f(*std::begin(v));for(auto it=std::next(std::begin(v));it!=std::end(v);++it){if(auto val=f(*it);max_valauto operator()(F&&f){return Callable([&](auto v){a\ uto min_val=f(*std::begin(v));for(auto it=std::next(std::begin(v));it!=std::end(v);++it){if(auto val=f(*it);min_val>val)\ {min_val=val;}}return min_val;});}}MinOf;struct Count_impl{templateauto operator()(const V&val){return Callable\ ([&](auto v){return std::count(std::begin(v),std::end(v),val);});}}Count;struct CountIf_impl{templateauto opera\ tor()(const F&f){return Callable([&](auto v){return std::count_if(std::begin(v),std::end(v),f);});}}CountIf;struct Index\ _impl{templateauto operator()(const V&val){return Callable([&](auto v)->std::optional{auto result=std::fin\ d(std::begin(v),std::end(v),val);return result!=std::end(v)? std::optional(result-std::begin(v)): std::nullopt;});}templ\ ateauto operator()(const V&val,std::size_t i){return Callable([&](auto v)->std::optional{auto result=std::\ find(std::next(std::begin(v),i),std::end(v),val);return result!=std::end(v)? std::optional(result-std::begin(v)): std::n\ ullopt;});}}Index;struct IndexIf_impl{templateauto operator()(const F&f){return Callable([&](auto v)->std::opti\ onal{auto result=std::find_if(std::begin(v),std::end(v),f);return result!=std::end(v)? std::optional(result-std::be\ gin(v)): std::nullopt;});}}IndexIf;struct FindIf_impl{templateauto operator()(const F&f){return Callable([&](au\ to v)->std::optional{auto result=std::find_if(std::begin(v),std::end(v),f);return resu\ lt!=std::end(v)? std::optional(*result): std::nullopt;});}}FindIf;struct Sum_impl{templateauto operator()(F&&f)\ {return Callable([&](auto v){return std::accumulate(std::next(std::begin(v)),std::end(v),f(*std::begin(v)),[&](const aut\ o&a,const auto&b){return a+f(b);});});}templatefriend auto operator|(T v,[[maybe_unused]] const Sum_impl&c){ret\ urn std::accumulate(std::begin(v),std::end(v),typename T::value_type{});}}Sum;struct Includes{templateauto oper\ ator()(const V&val){return Callable([&](auto v){return std::find(std::begin(v),std::end(v),val)!=std::end(v);});}}Includ\ es;struct IncludesIf_impl{templateauto operator()(const F&f){return Callable([&](auto v){return std::find_if(st\ d::begin(v),std::end(v),f)!=std::end(v);});}}IncludesIf;struct RemoveIf_impl{templateauto operator()(const F&f)\ {return Callable([&](auto v){v.erase(std::remove_if(std::begin(v),std::end(v),f),std::end(v));return v;});}}RemoveIf;str\ uct Each_impl{templateauto operator()(F&&f){return Callable([&](auto v){for(const auto&i:v){f(i);}});}}Each;str\ uct EachConsPair_impl{templatefriend auto operator|(const T&v,EachConsP\ air_impl&c){std::vector>result;if(std::size(v)>=2){result.reserve(std::size(v)-1);for(s\ td::size_t i=0;iauto operator()(F&&f){return Callable([&](auto v){using value_type=typename decltype(v)::value_type;std\ ::vectorresult;for(const auto&i:v){if(f(i))result.push_back(i);}return result;});}}Select;struct Map_impl{te\ mplateauto operator()(F&&f){return Callable([&](auto v){using result_type=std::invoke_result_t;std::vectorresult;result.reserve(std::size(v));for(const auto&i:v){result.push_back(f(i\ ));}return result;});}}Map;struct Indexed_impl{templatefriend auto operator|(const T&v,Indexed_impl&c){using va\ lue_type=typename T::value_type;std::vector>result;result.reserve(std::size(v));int index=0;fo\ r(const auto&i:v){result.emplace_back(i,index++);}return result;}}Indexed;struct AllOf_impl{templateauto operat\ or()(F&&f){return Callable([&](auto v){for(const auto&i:v){if(!f(i))return false;}return true;});}}AllOf;struct AnyOf_im\ pl{templateauto operator()(F&&f){return Callable([&](auto v){for(const auto&i:v){if(f(i))return true;}return fa\ lse;});}}AnyOf;struct NoneOf_impl{templateauto operator()(F&&f){return Callable([&](auto v){for(const auto&i:v)\ {if(f(i))return false;}return true;});}}NoneOf;struct Tally_impl{auto operator()(std::size_t max_val){return Callable([&\ ](auto v){std::vectorresult(max_val);for(const auto&i:v){result[static_cast(i)]++;}return resu\ lt;});}templatefriend auto operator|(const T&v,Tally_impl&c){std::mapresult;for(const auto&i:v){result[i]++;}return result;}}Tally;struct Reduce_impl{templateauto operator()(T memo,F f){return Callable([memo,f](auto v){auto acc=memo;for(auto i:v){acc=f(acc,i);}return ac\ c;});}}Reduce;struct Join_impl{auto operator()(std::string separater){return Callable([&](auto v){std::string result;boo\ l first=true;for(const auto&i:v){if(!std::exchange(first,false)){result+=separater;}result+=std::to_string(i);}return re\ sult;});}templatefriend auto operator|(const T&v,Join_impl&c){return v|c("");}}Join;struct At_impl{auto operato\ r()(std::size_t l,std::size_t r){return Callable([l,r](auto v){return decltype(v)(std::begin(v)+l,std::begin(v)+r);});}}\ At;struct Slice_impl{auto operator()(std::size_t i,std::size_t cnt){return Callable([i,cnt](auto v){return decltype(v)(s\ td::begin(v)+i,std::begin(v)+i+cnt);});}}Slice;struct Transpose_impl{templatefriend auto operator|(const std::v\ ector>&v,Transpose_impl&c){std::size_t h=v.size(),w=v.front().size();std::vector result(w,std::vector(\ h));for(std::size_t i=0;iauto operator*(const std::vector&a,std::size_t n){T result;for(std::size_t i=0;istr\ uct has_push_back:std::false_type{};templatestruct has_push_back().push_back(std::declval()))>>: std::true_type{};}template::value,std::nullptr_t> =nullptr>auto&operator<<(Container&continer,const T&val){continer.push_bac\ k(val);return continer;}template::value,st\ d::nullptr_t> =nullptr>auto operator+(Container continer,const T&val){continer<constexpr T TEN(std::size_t n){T result=1;for(std::size_t i=0;i&&std::is_integral_v,std::nullptr_t> =nullptr>constexpr auto div_ceil(\ T n,U m){return(n+m-1)/m;}templateconstexpr auto div_ceil2(T n,U m){return div_ceil(n,m)*m;}templateconstexpr T triangle(T n){return(n&1)?(n+1)/2*n:n/2*(n+1);}templateconstexpr T nC2(T n){return(n&1)?(n-1)\ /2*n:n/2*(n-1);}templateconstexpr auto middle(const T&l,const U&r){return l+(r-l)/2;}templateconstexpr bool in_range(const T&v,const U&lower,const V&upper){return lower<=v&&v,std::nullptr_t> =nullptr>constexpr bool is_square(T n){T s=std::sqrt(n);return s\ *s==n||(s+1)*(s+1)==n;}templateconstexpr T BIT(int b){return T(1)<constexpr int \ BIT(T x,int i){return(x&(T(1)<constexpr int Sgn(T x){return(0x);}templateboo\ l is_leap(T year){return!(year%4)&&(year%100||!(year%400));}template,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,std::nullptr_t> =nullptr>conste\ xpr 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;}templatebool chmax(T&a,const T&b){return aboo\ l chmin(T&a,const T&b){return a>b?a=b,true:false;}templateint sz(const T&v){return v.size();}templateint lower_index(const T&a,const U&v){return std::lower_bound(a.begin(),a.end(),v)-a.begin();}templateint lower_index(const T&a,const U&v,const F&f){return std::lower_bound(a.begin(),a.end(),v,f)-a.begin();}te\ mplateint upper_index(const T&a,const U&v){return std::upper_bound(a.begin(),a.end(),v)-a.begin();}temp\ lateint upper_index(const T&a,const U&v,const F&f){return std::upper_bound(a.begin(),a.end(),v,\ f)-a.begin();}templateU Gcdv(const T&v){return std::accumulate(std::next(v.begin\ ()),v.end(),U(*v.begin()),std::gcd);}templateU Lcmv(const T&v){return std::\ accumulate(std::next(v.begin()),v.end(),U(*v.begin()),std::lcm);}templateT&Concat(T&v,const T&vec){v.inser\ t(v.end(),vec.begin(),vec.end());return v;}namespace internal{templateauto make_vector(std::vecto\ r&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(sizes,init));}}}templateauto make_vector(const int(\ &sizes)[N],const T&init=T()){std::vector s(std::rbegin(sizes),std::rend(sizes));return internal::make_vector(s,init\ );}templatestruct rec_lambda{F f;rec_lambda(F&&f_): f(std::forward(f_)){}templateauto operato\ r()(Args&&... args)const{return f(*this,std::forward(args)...);}};namespace lambda{auto char_to_int=[](char c){ret\ urn 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){retur\ n n.second;};templateauto cast(){return [](const auto&n){return static_cast(n);};};templateauto equ\ al_to(const T&x){return [x](auto y){return x==y;};}templateauto get(){return [](const auto&n){return std:\ :get(n);};}templateauto cmp(F&&f){return [f](const auto&a,const auto&b){return f(a)) #define LOCAL #include #else #define dump(...)((void)0) #define dump2(...)((void)0) #endif templateconstexpr T oj_local(const T&oj,const T&local){ #ifndef LOCAL return oj; #else return local; #endif } #line 2 "a.cpp" using namespace std; int main() { int n = in, m = in; VVI g(n); VP edges(m); rep(i, m) { int a = in--, b = in--; g[a].push_back(b); g[b].push_back(a); edges[i] = pair(a, b); } const int MAX_N = oj_local(20001, 10); vector> flag(n); rep(v, n) { int s = g[v].size(); rep(i, s) rep(j, s) { if (i == j) continue; if (g[v][i] == 0) { flag[g[v][j]].set(v); } } } out.set(Printer::YES); for (auto [u, v] : edges) { if (flag[u].any() && flag[v].any() && (flag[u] | flag[v]).count() != 1) { out.exit(true); } } out(false); }