QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#27814#1824. Special CycleTimseiAC ✓5ms3836kbC++17.9kb2022-04-10 21:39:122022-04-29 07:44:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 07:44:01]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:3836kb
  • [2022-04-10 21:39:12]
  • 提交

answer

// {{{ y0105w49 template 21N30
// hi mom
#ifndef NULL
// #include <bits/stdc++.h>
#include <bits/extc++.h>
#endif
#include <tr2/dynamic_bitset>
using namespace std;
#ifdef ARST
#define JO 1
#define OJ 0
#else
#define JO 0
#define OJ 1
#endif
#define STR(x) #x
#define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true)
#define Wsave GCCDIAG(push)
#define Wpop GCCDIAG(pop)
#define Wsupp(w) GCCDIAG(ignored "-W" w)
#define Wpush(w) Wsave; Wsupp(w)
#define typeof __typeof__
namespace gbd_ns {
	template<typename C>
	struct is_iterable {
		template<class T> static long check(...);
		template<class T> static char check(int,typename T::const_iterator = C().end());
		enum {
			value = sizeof(check<C>(0)) == sizeof(char),
			neg_value = sizeof(check<C>(0)) != sizeof(char)
		};
	};
	template<class T> struct _gbd3C;
	template<class T> ostream &_gbd3(ostream &os,const T &x) {
		return _gbd3C<T>::call(os,x);
	}
	template<> ostream &_gbd3(ostream &os,const string &x) {
		return os<<'"'<<x<<'"';
	}
	template<> ostream &_gbd3(ostream &os,char *const &x) {
		return os<<'"'<<x<<'"';
	}
	template<class T> ostream &_gbd35(ostream &os,const T &x) {
		return _gbd3(os,x);  // why??
	}
	template<class A,class B>
	ostream &_gbd4(ostream &os,const pair<A,B> &p) {
		_gbd3(os<<'(',p.first);
		_gbd3(os<<',',p.second);
		return os<<')';
	}
	template<class T,size_t N> struct _gbd4_tupleC {
		static void call(ostream &os,const T &t) {
			_gbd4_tupleC<T,N-1>::call(os,t);
			os<<','<<get<N-1>(t);
		}
	};
	template<class T> struct _gbd4_tupleC<T,1> {
		static void call(ostream &os,const T &t) {
			os<<get<0>(t);
		}
	};
	template<typename... Types>
	ostream &_gbd4(ostream &os,const tuple<Types...> &t) {
		os<<'(';
		_gbd4_tupleC<tuple<Types...>,sizeof...(Types)>::call(os,t);
		return os<<')';
	}
	template<>
	ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; }
	template<class T> ostream &_gbd4(ostream &os,const T &x) {
		return os<<x;
	}
	template<class T> struct _gbd3C {
		template<class U=T>
		static ostream &call(ostream &os,enable_if_t<is_iterable<U>::value,const T> &V) {
			os<<"{";
			bool ff=0;
			for(const auto &E:V) _gbd35<decltype(E)>(ff?os<<",":os,E), ff=1;
			return os<<"}";
		}
		template<class U=T>
		static ostream &call(ostream &os,enable_if_t<is_iterable<U>::neg_value,const T> &x) {
			return _gbd4(os,x);
		}
	};
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool,vector<string>::iterator nm,const T &x,Args&&... args);
	ostream &_gbd2(ostream &os,bool,vector<string>::iterator) { return os; }
	template<typename... Args>
	ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const char *x,Args&&... args) {
		return _gbd2(os<<(fi?"":"  ")<<x,0,nm+1,args...);
	}
	template<class T,typename... Args>
	ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const T &x,Args&&... args) {
		return _gbd2(_gbd3<T>(os<<(fi?"":"  ")<<*nm<<"=",x),0,nm+1,args...);
	}
	vector<string> split(string s) {
		vector<string> Z;
		string z="";
		s+=',';
		int dep=0;
		for(char c:s) {
			if(c==',' && !dep) Z.push_back(z),z="";
			else z+=c;
			if(c=='(' || c=='{' || c=='[') ++dep;
			if(c==')' || c=='}' || c==']') --dep;
		}
		return Z;
	}
	template<typename... Args> ostream &_gbd1(ostream &os,const string &nm,Args&&... args) {
		return _gbd2(os,1,split(nm).begin(),args...);
	}
	template<typename... Args> string _gbd1(const string &nm,Args&&... args) {
		ostringstream oss;
		_gbd2(oss,1,split(nm).begin(),args...);
		return oss.str();
	}
}
bool DBG=1,EMACS=0;
#define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"<<endl:cerr)
#define dbgt(...) dbg(fmt_time(),__VA_ARGS__)
#define fmt(...) gbd_ns::_gbd1(#__VA_ARGS__,__VA_ARGS__)
template<class Fun> struct _y_combinator_result {
	Fun _fun;
	template<class T> explicit _y_combinator_result(T &&fun) : _fun(forward<T>(fun)) {}
	template<typename... Args> decltype(auto) operator()(Args &&... args) {
		return _fun(ref(*this),forward<Args>(args)...);
	}
};
template<class Fun> [[nodiscard]] decltype(auto) fix(Fun &&fun) {
	return _y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}
#define nop void()
#define sz(x) (int((x).size()))
#define all(v) begin(v),end(v)
#define sortu(v) (sort(all(v)), (v).resize(unique(all(v))-begin(v)))
#define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k)
#define get(x,i) get<i>(x)
template<class T> bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; }
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
template<class S,class T> using omap=__gnu_pbds::tree<S,T,less<S>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<class T> using oset=omap<T,__gnu_pbds::null_type>;
template<class T> using rope=__gnu_cxx::rope<T>;
using dbitset=tr2::dynamic_bitset<>;
const int e0=1, e1=10, e2=100, e3=1000;
const int e4=10*e3, e5=100*e3, e6=1000*e3;
const int e7=10*e6, e8=100*e6, e9=1000*e6;
const long long e12=1LL*e3*e9, e15=1LL*e6*e9, e18=1LL*e9*e9;
using ulll=__uint128_t;
using lll=__int128_t;
using ull=unsigned long long;
using ll=long long;
unsigned long long START_TIME=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();
inline unsigned long long now_U_03BC_s() { return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; }
const char *fmt_time(unsigned long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; }
#define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0)
int arg1; bool inp; vector<string> args;
unsigned seed=JO&&getenv("sd")?atoi(getenv("sd")):unsigned(OJ?START_TIME:START_TIME%e5);
mt19937 igen(seed<<1),gen(seed<<1|1);
#define irand(...) _rand(igen,__VA_ARGS__)
#define rand(...) _rand(gen,__VA_ARGS__)
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution<T>(l,r)(g); }
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); }
[[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits<int>::max()); }
template<class T> enable_if_t<numeric_limits<T>::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution<T>(l,r)(g); }
bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); }
template<class T> T _rand(mt19937 &g,initializer_list<T> il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); }
template<class T> T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; }
template<class T> T _rand(mt19937 &g,initializer_list<T> il,initializer_list<double> wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution(wt)(g)); }
#define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle")
#define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop))
#define inr(x,...) ine(x,irand(__VA_ARGS__))
#define endl '\n'
string garb;
void exit0() { dbg("finished (early) in",fmt_time()); exit(0); }
#ifndef MAIN
#define MAIN _main
#endif
void MAIN();
int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit);
	arg1=0,args={argv,argv+argc};
	if(sz(args)>1) {
		if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin);
		else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin);
		else arg1=stoi(args[1]);
	}
	inp=!arg1;
	if(JO && getenv("EMACS")) EMACS=1;
	dbgt(arg1,seed,args);
	MAIN();
	dbgt("gg;wp");
}
using flt=double; //CARE
const flt U_03B5_=(flt)1e-8;
const flt U_03C4_=(flt)(2*acosl(-1));
const int inf=e9+99;
const ll linf=1LL*e9*e9+99;
// }}}
const int P=e9+7;//998'244'353;










void _main() { /* CURSOR START */
	const int N=160;
	int n,m,nspc; cin>>n>>m>>nspc;
	assert(inb(n,1,150) && inb(m,1,n*(n-1)/2) && inb(nspc,1,m));
	static bitset<N> spc[N],nrm[N];
	static char A[N][N];
	for(int i=1;i<=m;i++) {
		int u,v; cin>>u>>v;
		assert(1<=u && u<v && v<=n);
		assert(!spc[u][v] && !nrm[u][v]);
		(i<=nspc?spc:nrm)[u][v]=1;
		(i<=nspc?spc:nrm)[v][u]=1;
		A[u][v]=A[v][u]="NS"[i<=nspc];
	}
	assert((cin>>ws).eof());
	auto check=[&](vector<int> Z) -> void {
		dbg("checking",Z);
		int l=sz(Z);
		assert(inb(l,3,n));
		for(int x:Z) assert(inb(x,1,n));
		for(int i=0;i<l;i++) for(int j=0;j<i;j++) assert(Z[i]!=Z[j]);
		int y=Z.back();
		for(int x:Z) assert(A[x][y]=='N' || A[x][y]=='S'), A[x][y]=A[y][x]=0, y=x;
		for(int x:Z) for(y=1;y<=n;y++) assert(A[x][y]==0 || A[x][y]=='N');
	};

	auto dfs=fix([&](auto rec,vector<pair<int,int>> &br,bitset<N> &vis,int u,int d=0,int p=-1) -> int {
		static int dep[N];
		if(vis[u]) return dep[u];
		vis[u]=1, dep[u]=d;
		int z=d;
		forbs(_,v,nrm[u]) if(v!=p) z=min(z,rec(br,vis,(int)v,d+1,u));
		forbs(_,v,spc[u]) if(v!=p) z=min(z,rec(br,vis,(int)v,d+1,u));
		if(z==d && ~p) br.pb({u,p});
		return z;
	});
	auto solve=fix([&](auto rec,bitset<N> V) -> vector<int> {
			forbs(_,u,V) assert(!spc[u][u]);
			forbs(_,u,V) assert(!spc[u][u] && !nrm[u][u]);
			forbs(_,u,V) assert((spc[u]&nrm[u]).none() && !spc[u][u] && !nrm[u][u]);

			if(V.count()<=2) return {};
			forbs(_,u,V) if(spc[u].count()>=3) {
				vector<int> Q={(int)u};
				for(int ii=0;ii<sz(Q);ii++) {
					u=Q[ii];
					V[u]=0;
					forbs(__,v,spc[u]) if(V[v]) Q.pb((int)v);
					forbs(__,v,nrm[u]) nrm[v][u]=0;
				}
				dbg("rec cut 3-spc",Q);
				return rec(V);
			}
			forbs(_,u,V) if(spc[u].count()==2) {
				int x=(int)spc[u]._Find_first();
				int y=(int)spc[u]._Find_next(x);
				assert(spc[u]._Find_next(y)==N);
				assert(x!=y && V[x] && V[y]);
				spc[x][u]=spc[u][x]=0;
				spc[y][u]=spc[u][y]=0;
				if(nrm[x][y] && spc[x].none() && spc[y].none()) { dbg("ssn",x,y,u); return {x,y,(int)u}; };
				if(spc[x][y]) { assert(spc[x].count()==1 && spc[y].count()==1); dbg("sss",x,y,u); return {x,y,(int)u}; }
				spc[x][y]=spc[y][x]=1;
				nrm[x][y]=nrm[y][x]=0;
				forbs(__,v,nrm[u]) nrm[v][u]=0;
				V[u]=0;
				dbg("rec compress 2-spc",u,x,y);
				auto Z=rec(V);
				dbg("ret 2spc",Z);
				forenum(j,int v:Z) if(v==x || v==y) {
					if(Z[j+1]==(x^y^v)) Z.insert(Z.begin()+j+1,(int)u);
					else assert(!j && Z.back()==(x^y^v)), Z.pb((int)u);
					return Z;
				}
				return Z;
			}
			forbs(_,u,V) assert(spc[u].count()<=1);

			vector<pair<int,int>> br;
			bitset<N> vis;
			dfs(br,vis,(int)V._Find_first());
			assert(vis[V._Find_first()]);
			if(vis.count()<V.count()) {
				dbg("rec first dj cc");
				auto Z=rec(vis);
				if(sz(Z)) return Z;
				dbg("rec second dj cc");
				return rec(V&~vis);
			}
			assert(vis.count()==V.count());
			if(sz(br)) {
				dbg(br);
				for(auto [u,v]:br) {
					assert(nrm[u][v]+spc[u][v]==1);
					if(spc[u][v]) {
						forbs(_,w,nrm[u]) nrm[w][u]=0;
						forbs(_,w,nrm[v]) nrm[w][v]=0;
						spc[u][v]=spc[v][u]=0;
						V[u]=V[v]=0;
					} else nrm[u][v]=nrm[v][u]=0;
				}
				dbg("rec killedbr",br);
				return rec(V);
			}

			auto nrmV=V;
			forbs(_,u,V) nrmV&=~spc[u];
			if(nrmV.any()) {
				int u=(int)nrmV._Find_first();
				assert(spc[u].none());

				// forbs(_,v,nrm[u]) forbs(__,w,nrm[u]) {
				// 	if(v!=w && spc[v][w]) { dbg("nns",u,v,w); return {u,(int)v,(int)w}; }
				// 	if(v!=w && nrm[v][w] && nrmV[v] && nrmV[w]) { dbg("nnn"); return {u,(int)v,(int)w}; }
				// }
				forbs(_,v,nrm[u]) if((nrm[u]&spc[v]).any()) {
					int w=(int)(nrm[u]&spc[v])._Find_first();
					dbg("nns",u,v,w);
					return {u,(int)v,(int)w};
				}
				forbs(_,v,nrm[u]) if(nrmV[v] && (nrm[u]&nrm[v]&nrmV).any()) {
					int w=(int)(nrm[u]&nrm[v]&nrmV)._Find_first();
					dbg("nnn",u,v,w);
					return {u,(int)v,(int)w};
				}

				forbs(_,v,nrm[u]) if(nrmV[v]) {
					assert(spc[v].none());
					V[v]=0;
					nrm[u]|=nrm[v];
					forbs(__,w,nrm[v]) if(nrm[w][v]) nrm[w][v]=0, nrm[w][u]=1;
					nrm[u][u]=0;
					dbg("rec compress adj nrm",u,v);
					auto Z=rec(V);
					dbg("ez fixing",Z);
					assert(sz(Z));
					auto it=find(all(Z),u);
					if(it==Z.end()) return Z;
					bool fv=nrm[v][it+1==Z.end()?Z[0]:*(it+1)];
					bool rv=nrm[v][it==Z.begin()?Z.back():*(it-1)];
					if(fv && rv) return *it=(int)v,Z;
					if(fv) Z.insert(it+1,(int)v);
					if(rv) Z.insert(it,(int)v);
					return Z;
				}

				// forbs(_,v,nrm[u]) forbs(__,w,nrm[u]) if(v!=w) assert(!spc[v][w]), nrm[v][w]=nrm[w][v]=1;
				forbs(_,v,nrm[u]) nrm[v]|=nrm[u];
				forbs(_,v,nrm[u]) nrm[v][u]=nrm[v][v]=0;
				V[u]=0;
				dbg("rec compress lone nrm",u);
				auto Z=rec(V);
				assert(sz(Z));
				vector<int> NZ;
				int pr=Z.back();
				for(int v:Z) {
					if(nrm[u][v] && nrm[u][pr]) NZ.pb(u);
					NZ.pb(v);
					pr=v;
				}
				dbg("multi-fixed",NZ);
				rotate(NZ.begin(),find(all(NZ),u),NZ.end());
				NZ.erase(find(NZ.begin()+1,NZ.end(),u),NZ.end());
				dbg("trunc'd",NZ);
				return NZ;
			}

			forbs(_,u,V) assert(spc[u].count()==1 && nrm[u].any());
			static int mat[N];
			forbs(_,u,V) mat[u]=(int)spc[u]._Find_first();

			bitset<N> seen;
			vector<int> cyc1;
			for(int u=(int)V._Find_first();;) {
				if(seen[u]) {
					dbg("found good-cyc",u,mat[u],cyc1);
					reverse(all(cyc1));
					for(;cyc1.back()!=u;) cyc1.pop_back();
					dbg("returning",cyc1);
					return cyc1;
				}
				cyc1.pb(u);
				seen[u]=1;
				u=mat[u];
				if(seen[u]) break;
				cyc1.pb(u);
				u=(int)nrm[u]._Find_first();
			}
			dbg("broke w/ first cyc",cyc1);
			reverse(all(cyc1));
			for(;cyc1.back()!=cyc1[0];) cyc1.pop_back();
			assert(sz(cyc1)>=4 && sz(cyc1)%2==0);
			dbg("nz",cyc1);

			auto cut_cyc=[](vector<int> cyc,int u) -> vector<int> {
				if(u==cyc.back()) return {u};
				int v=mat[u];
				int w=cyc.back(); cyc.pop_back();
				assert(u!=w && v!=w);
				rotate(cyc.begin(),find(all(cyc),u),cyc.end());
				assert(cyc[0]==u);
				if(cyc[1]!=v) reverse(cyc.begin()+1,cyc.end());
				assert(cyc[1]==v);
				for(;cyc.back()!=w;) cyc.pop_back();
				return cyc;
			};

			seen.reset();
			for(int u:cyc1) seen[u]=1;
			seen[cyc1.back()]=0;
			vector<int> cyc2;
			for(int u=cyc1.back();;) {
				if(seen[u]) {
					dbg("found some good-cyc (2)",u,mat[u],cyc1,cyc2);
					auto it=find(all(cyc2),u);
					if(it!=cyc2.end()) {
						cyc2.erase(cyc2.begin(),it);
						dbg("returning",cyc2);
						return cyc2;
					}
					dbg("ret join",cyc1,cyc2);
					assert(cyc2[0]==cyc1.back());
					auto Z=cut_cyc(cyc1,u);
					assert(Z.back()==cyc2[0]); Z.pop_back();
					Z.insert(Z.end(),all(cyc2));
					dbg("joined",Z);
					return Z;
				}
				cyc2.pb(u);
				seen[u]=1;
				u=mat[u];
				if(seen[u]) break;
				cyc2.pb(u);
				u=(int)nrm[u]._Find_first();
			}
			dbg("broke w/ second cyc",cyc2);
			reverse(all(cyc2));
			vector<int> pat;
			for(;cyc2.back()!=cyc2[0];) pat.pb(cyc2.back()), cyc2.pop_back();
			assert(sz(cyc2)>=4 && sz(cyc2)%2==0);
			dbg("nz",cyc2);
			pat.pb(cyc2.back());

			for(;;) {
				dbg("looping w/ state",cyc1,pat,cyc2);
				seen.reset();
				static bitset<N> stop; stop.reset();
				for(int u:cyc1) stop[u]=1;
				for(int u:pat) stop[u]=1;
				// stop[cyc2.back()]=0;
				auto Q=cyc2; Q.pop_back();
				for(int u:Q) seen[u]=1;
				Q[0]=-1;
				static int pr[N]; memset(pr,-1,sizeof pr);
				for(int ii=0;;ii++) {
					assert(ii<sz(Q));
					int u=Q[ii];
					if(!~u) u=cyc2.back();
					else if(stop[u]) {
						u=mat[u];
						dbg("stopped search",u,mat[u],pr[u],pr[mat[u]]);
						vector<int> Z;
						if(find(all(cyc1),u)!=cyc1.end()) {
							dbg("final win CDCP");
							Z=cut_cyc(cyc1,u);
							assert(Z.back()==pat[0]); Z.pop_back();
							for(int v:pat) Z.pb(v);
							finish:;
							assert(Z.back()==cyc2.back());
							reverse(all(Z));
							dbg("half-cyc and pat",Z);
							// for(;~pr[Z.back()];) Z.pb(pr[Z.back()]), Z.pb(mat[Z.back()]);
							for(;~pr[Z.back()] && (mat[Z.back()]!=cyc2.back() || sz(Z)<=2);)
								Z.pb(pr[Z.back()]), Z.pb(mat[Z.back()]);
							dbg("and prs",Z);
							Z.pop_back(); assert(!~pr[Z.back()]);
							auto las=cut_cyc(cyc2,Z.back());
							assert(las[0]==Z.back());
							Z.pop_back();
							Z.insert(Z.end(),all(las));
							assert(Z.back()==Z[0]);
							Z.pop_back();
							dbg("aaand finally",Z);
							return Z;
						}
						auto it=find(all(pat),u);
						assert(it!=pat.begin() && it!=pat.end()-1);
						Z={it,pat.end()};
						if(*(it+1)==mat[u]) {
							dbg("final win CDP. being cute w/",Z);
							goto finish;
						}
						dbg("shortening",sz(pat),"to",it+1-pat.begin());
						reverse(all(Z));
						// for(;~pr[Z.back()];) Z.pb(pr[Z.back()]), Z.pb(mat[Z.back()]);
						for(;~pr[Z.back()] && (mat[Z.back()]!=cyc2.back() || sz(Z)<=2);)
							Z.pb(pr[Z.back()]), Z.pb(mat[Z.back()]);
						dbg("half-pat and back",Z);
						Z.pop_back(); assert(!~pr[Z.back()]);
						cyc2=cut_cyc(cyc2,Z.back());
						assert(cyc2[0]==Z.back());
						assert(cyc2.back()==Z[0]);
						cyc2.pop_back();
						Z.pop_back();
						cyc2.insert(cyc2.begin(),all(Z));
						pat.erase(it+1,pat.end());
						rotate(cyc2.begin(),find(all(cyc2),pat.back()),cyc2.end());
						cyc2.pb(cyc2[0]);
						break;
					}
					static bitset<N> tmp; tmp=nrm[u]&~seen;
					forbs(_,v,tmp) seen[v]=1, pr[v]=u, Q.pb(mat[v]);
				}
			}
		});

	bitset<N> V; for(int i=1;i<=n;i++) V[i]=1;
	auto Z=solve(V);
	if(!sz(Z)) return cout<<-1<<endl,nop;
	check(Z);
	cout<<sz(Z)<<endl;
	forenum(i,int x:Z) cout<<x<<" \n"[i==sz(Z)-1];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

input:

8 10 3
1 2
4 5
7 8
2 3
3 4
1 4
5 6
6 7
5 8
3 8

output:

8
3 2 1 4 5 6 7 8

result:

ok OK

Test #2:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

4 6 3
1 2
1 3
1 4
2 3
3 4
2 4

output:

-1

result:

ok OK: both impossible

Test #3:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

66 88 22
3 4
6 11
9 10
12 17
15 16
18 23
21 22
24 29
27 28
30 35
33 34
36 41
39 40
42 47
45 46
48 53
51 52
54 59
57 58
60 65
63 64
5 66
1 2
2 3
1 3
4 5
5 6
4 6
7 8
8 9
7 9
10 11
11 12
10 12
13 14
14 15
13 15
16 17
17 18
16 18
19 20
20 21
19 21
22 23
23 24
22 24
25 26
26 27
25 27
28 29
29 30
28 30
31...

output:

22
6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 5

result:

ok OK

Test #4:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

57 95 32
44 57
2 7
8 48
4 38
17 48
31 49
43 56
38 50
13 15
23 44
8 27
48 54
5 47
25 47
47 51
23 28
1 5
43 46
5 8
25 28
3 10
35 46
10 34
20 23
2 31
26 32
9 37
19 22
16 52
11 26
23 38
16 42
5 28
40 50
30 56
36 39
28 57
42 44
1 45
5 56
12 45
7 9
12 40
3 50
17 27
12 38
40 46
12 25
9 42
20 21
45 49
11 24...

output:

9
45 13 15 32 26 11 52 16 42

result:

ok OK

Test #5:

score: 0
Accepted
time: 3ms
memory: 3768kb

input:

98 93 36
15 81
19 93
57 65
46 80
34 47
9 25
58 78
13 61
8 18
73 90
2 39
5 82
49 64
4 62
40 85
14 79
47 73
10 83
43 65
30 59
80 81
40 41
95 98
3 92
15 55
4 98
31 37
74 86
46 69
24 27
70 79
21 28
12 83
60 84
52 98
17 96
83 93
6 32
53 96
29 66
50 66
27 71
40 53
81 94
14 18
63 98
10 59
10 22
8 25
19 85
...

output:

15
22 23 42 27 24 82 5 8 18 14 79 70 12 83 10

result:

ok OK

Test #6:

score: 0
Accepted
time: 3ms
memory: 3824kb

input:

146 277 99
43 110
11 123
76 90
60 88
107 129
38 129
23 49
9 56
125 144
89 138
31 88
74 136
46 126
107 122
31 53
8 18
25 42
12 123
3 128
68 121
28 88
35 65
24 52
24 53
74 108
28 79
85 94
64 113
6 77
128 136
111 146
41 136
14 111
88 125
41 83
48 145
13 29
13 33
69 96
46 130
11 92
31 58
65 112
96 104
1...

output:

13
80 1 12 123 11 92 102 116 37 101 44 34 54

result:

ok OK

Test #7:

score: 0
Accepted
time: 3ms
memory: 3700kb

input:

29 41 10
12 20
10 19
1 5
4 21
13 24
6 9
1 12
11 27
12 22
5 14
5 8
6 27
7 21
20 25
1 8
1 2
8 9
2 26
7 15
18 27
6 19
8 24
7 11
20 26
6 15
2 8
16 19
20 29
14 21
1 7
16 21
10 13
11 29
16 17
8 21
18 20
1 3
2 17
2 9
5 24
22 28

output:

7
8 24 13 10 19 6 9

result:

ok OK

Test #8:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

60 97 23
45 52
18 55
1 53
5 35
37 47
25 43
11 55
5 41
36 59
26 40
38 39
21 51
30 32
27 60
46 51
21 50
19 35
20 26
24 31
4 25
8 37
5 33
33 49
33 46
53 59
18 22
21 37
19 41
11 59
25 52
23 54
22 36
31 55
38 45
28 56
41 45
7 27
24 30
21 57
11 56
15 56
6 22
42 56
15 39
48 53
5 29
31 41
2 31
17 27
5 36
7 ...

output:

11
56 9 47 37 8 59 36 22 18 55 11

result:

ok OK

Test #9:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

62 41 13
12 48
6 26
37 57
2 23
11 62
42 45
24 59
50 51
16 55
41 60
23 54
12 45
6 51
5 21
20 51
25 42
13 26
37 62
19 61
5 40
7 42
6 37
22 28
46 49
10 23
16 31
44 62
24 57
21 29
15 18
33 61
29 57
21 41
23 27
40 42
5 49
32 55
11 37
44 46
40 59
34 62

output:

10
29 21 5 49 46 44 62 11 37 57

result:

ok OK

Test #10:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

6 8 1
1 4
3 6
1 6
1 2
3 5
5 6
4 6
3 4

output:

3
3 5 6

result:

ok OK

Test #11:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

8 17 6
4 7
1 5
3 6
5 7
3 5
3 4
2 4
1 6
2 6
2 7
6 7
4 6
3 8
1 2
7 8
1 3
2 8

output:

-1

result:

ok OK: both impossible

Test #12:

score: 0
Accepted
time: 3ms
memory: 3620kb

input:

30 64 31
13 24
17 29
6 10
1 17
12 18
11 26
29 30
3 19
11 17
4 7
4 29
9 25
15 29
12 27
12 16
10 30
4 21
1 23
1 27
8 30
15 18
20 27
15 17
18 25
19 23
21 27
24 25
26 29
6 8
10 25
11 20
9 16
23 24
8 24
2 22
4 17
5 18
17 20
12 28
23 29
13 18
23 30
4 20
7 28
9 23
5 11
15 19
4 11
2 7
1 22
6 14
11 15
8 20
1...

output:

-1

result:

ok OK: both impossible

Test #13:

score: 0
Accepted
time: 3ms
memory: 3732kb

input:

23 14 3
1 20
5 10
21 22
4 23
8 14
11 23
12 14
17 20
10 14
2 13
1 23
1 15
1 9
5 15

output:

-1

result:

ok OK: both impossible

Test #14:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

3 2 1
2 3
1 3

output:

-1

result:

ok OK: both impossible

Test #15:

score: 0
Accepted
time: 3ms
memory: 3788kb

input:

17 84 25
11 14
4 16
5 16
4 8
1 2
11 13
8 12
7 11
11 12
6 12
8 14
1 10
9 16
7 9
13 14
15 16
1 16
3 14
7 14
5 10
3 6
2 14
6 7
15 17
2 11
2 6
16 17
2 13
4 12
1 13
4 11
1 7
12 15
3 17
12 16
9 12
11 15
13 17
10 16
2 4
6 13
6 15
10 14
3 4
1 14
4 7
2 8
5 17
1 12
5 6
10 13
3 16
7 12
9 17
4 13
4 10
9 13
8 16...

output:

-1

result:

ok OK: both impossible

Test #16:

score: 0
Accepted
time: 3ms
memory: 3800kb

input:

28 91 42
10 23
4 23
9 22
3 9
14 17
12 13
4 20
14 24
8 28
23 24
4 6
4 19
3 8
3 4
15 25
4 15
7 23
3 24
4 13
4 28
4 16
9 11
10 13
15 27
11 16
23 27
5 24
16 17
19 25
13 19
7 27
1 12
26 27
4 7
16 22
9 15
13 23
4 8
9 13
2 26
21 24
4 26
18 24
10 27
24 26
19 26
8 18
1 6
2 14
5 12
4 5
5 17
19 20
15 17
14 23
...

output:

-1

result:

ok OK: both impossible

Test #17:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

10 15 5
2 3
6 7
9 10
4 8
1 5
7 8
8 9
3 4
4 5
5 6
1 2
3 10
2 7
1 9
6 10

output:

8
4 8 7 6 5 1 2 3

result:

ok OK

Test #18:

score: 0
Accepted
time: 4ms
memory: 3756kb

input:

150 10783 2
22 139
31 85
18 37
10 73
62 129
14 22
33 68
31 140
88 136
39 58
20 40
26 32
64 77
20 79
72 126
53 146
42 68
16 145
6 76
42 66
68 106
64 134
8 123
110 119
89 124
10 26
100 144
60 80
69 74
52 100
93 118
7 73
11 98
44 148
33 129
140 145
53 115
23 52
23 141
6 48
6 150
3 58
43 97
35 132
38 89...

output:

3
1 22 139

result:

ok OK

Test #19:

score: 0
Accepted
time: 4ms
memory: 3604kb

input:

92 4162 52
2 17
55 84
28 64
16 24
32 71
11 18
56 69
78 88
24 30
15 80
12 28
24 26
5 72
61 81
21 52
30 36
35 55
7 72
35 57
65 73
14 21
6 54
6 9
30 90
51 69
29 76
38 63
51 65
20 82
49 79
61 88
79 82
35 66
51 88
21 36
42 51
33 49
1 9
58 67
43 53
22 83
3 9
5 19
23 42
48 74
39 61
16 70
10 33
49 73
57 84
...

output:

3
12 64 28

result:

ok OK

Test #20:

score: 0
Accepted
time: 5ms
memory: 3816kb

input:

138 8440 10
48 76
49 78
21 97
106 123
55 80
54 127
27 42
50 107
13 27
9 28
61 114
98 131
3 107
57 109
113 135
65 119
13 56
14 32
40 47
75 100
72 123
31 63
46 130
118 119
57 74
52 95
110 132
51 135
43 82
28 48
34 63
11 97
15 47
60 78
25 30
75 111
31 87
61 73
17 51
2 22
25 117
10 95
5 50
66 138
18 100...

output:

3
13 42 27

result:

ok OK

Test #21:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

107 3805 22
87 106
25 94
71 73
20 54
50 85
25 80
7 14
25 37
11 65
50 88
89 98
30 68
39 63
34 100
58 92
1 37
29 103
34 90
3 32
65 80
14 69
17 101
11 13
76 104
16 39
31 41
39 70
71 86
15 25
82 95
19 58
46 55
56 57
54 78
22 50
6 42
2 58
19 78
9 46
38 88
45 93
74 86
19 101
12 74
36 60
60 97
62 82
46 59
...

output:

3
90 100 34

result:

ok OK

Test #22:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

98 4558 31
6 89
28 86
29 97
6 30
5 96
8 87
15 51
38 73
31 35
15 50
15 49
39 70
25 40
20 91
20 56
37 42
22 52
5 20
2 59
2 56
13 50
12 61
45 49
1 87
22 65
27 96
7 24
5 48
1 6
16 95
48 73
53 73
20 62
10 82
79 92
49 58
17 24
79 82
60 80
89 95
9 31
34 95
1 5
36 41
2 39
55 74
17 94
18 46
17 27
29 40
67 82...

output:

3
52 65 22

result:

ok OK

Test #23:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

141 8460 2
35 140
59 115
100 128
22 128
49 120
36 37
60 124
84 102
3 83
26 131
38 129
27 61
1 62
28 73
9 66
8 60
102 106
4 101
44 104
51 77
8 98
23 96
74 92
22 137
113 134
25 138
67 133
35 122
2 121
8 109
36 42
110 118
78 114
88 110
73 76
102 125
26 36
54 141
127 134
50 53
73 77
74 103
66 139
61 89
...

output:

3
1 35 140

result:

ok OK

Test #24:

score: 0
Accepted
time: 4ms
memory: 3820kb

input:

149 7462 69
4 38
29 40
112 137
20 115
38 135
65 81
55 137
4 70
29 87
9 16
44 95
25 120
15 34
121 136
69 104
14 35
2 76
51 78
9 145
3 55
106 136
91 115
11 102
9 119
86 126
38 119
7 119
96 110
30 135
113 132
49 65
8 118
2 25
47 83
9 91
93 101
107 139
96 137
62 119
3 44
39 146
104 110
37 89
101 133
68 ...

output:

3
36 51 78

result:

ok OK

Test #25:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

148 10057 54
17 48
83 85
2 47
139 147
74 77
77 79
35 78
64 77
39 62
23 96
23 40
85 103
18 142
17 63
52 127
7 93
80 101
73 117
30 138
37 122
97 106
43 119
18 48
70 105
34 106
40 57
72 92
48 136
95 100
33 34
37 106
68 80
116 122
21 105
45 69
45 141
43 72
18 47
73 141
44 86
50 65
1 141
31 94
6 8
2 145
...

output:

4
57 96 23 40

result:

ok OK

Test #26:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

136 8924 10
40 127
57 132
1 106
81 132
80 107
106 132
35 74
111 122
18 102
88 123
5 10
23 96
65 90
10 112
81 82
32 74
41 89
105 116
4 11
89 127
99 100
35 49
51 79
56 108
51 60
81 134
10 101
103 130
22 105
65 113
4 33
61 69
7 27
21 112
46 74
9 100
110 111
100 120
42 75
33 66
98 104
45 121
2 17
33 82
...

output:

3
2 18 102

result:

ok OK

Test #27:

score: 0
Accepted
time: 4ms
memory: 3812kb

input:

134 7947 27
24 32
14 132
3 85
18 76
10 82
3 98
34 125
37 88
8 132
23 118
1 57
7 31
6 32
21 58
65 104
117 131
114 118
52 117
70 83
46 55
47 85
15 24
47 60
28 62
51 88
90 98
1 98
40 68
9 69
37 111
28 132
61 72
54 110
21 22
13 39
6 124
55 105
61 125
14 102
96 127
36 58
73 125
64 110
20 130
70 123
61 62...

output:

4
6 15 24 32

result:

ok OK

Test #28:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

10 12 5
1 2
3 4
5 6
7 8
9 10
2 3
2 4
1 5
5 8
6 7
4 9
6 10

output:

4
5 6 7 8

result:

ok OK

Test #29:

score: 0
Accepted
time: 3ms
memory: 3620kb

input:

10 13 5
1 2
3 4
5 6
7 8
9 10
2 3
2 4
1 5
6 7
6 8
8 9
5 10
3 10

output:

10
6 5 1 2 4 3 10 9 8 7

result:

ok OK

Test #30:

score: 0
Accepted
time: 3ms
memory: 3792kb

input:

6 7 3
1 2
3 4
5 6
2 3
3 6
4 5
1 3

output:

4
6 5 4 3

result:

ok OK

Test #31:

score: 0
Accepted
time: 3ms
memory: 3732kb

input:

4 4 2
3 4
1 3
2 4
1 4

output:

3
1 4 3

result:

ok OK

Test #32:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

8 12 4
1 2
3 4
5 6
7 8
2 4
2 6
4 6
1 7
2 3
4 5
6 7
1 8

output:

8
1 2 3 4 5 6 7 8

result:

ok OK

Test #33:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

6 8 3
1 2
1 6
3 6
1 5
3 5
2 4
4 6
4 5

output:

6
5 4 2 1 6 3

result:

ok OK

Test #34:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

10 22 3
4 5
4 7
7 9
3 7
2 5
2 7
5 8
1 9
3 6
3 10
5 9
6 9
1 4
1 3
3 4
4 6
4 8
8 9
9 10
5 6
6 8
1 5

output:

4
5 9 7 4

result:

ok OK

Test #35:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

4 4 2
1 4
3 4
1 3
2 4

output:

3
1 3 4

result:

ok OK

Test #36:

score: 0
Accepted
time: 3ms
memory: 3688kb

input:

101 132 34
28 60
42 56
76 86
67 71
30 41
45 50
35 96
31 48
48 83
62 70
47 82
50 98
5 40
16 54
1 17
31 88
52 80
33 36
75 86
55 83
5 15
21 100
14 31
53 82
93 101
9 71
63 92
82 93
27 39
20 100
46 66
35 82
48 86
14 98
6 85
77 92
8 38
60 84
26 79
55 67
47 55
55 89
86 93
1 64
17 18
33 85
14 46
9 69
5 78
9...

output:

4
97 9 71 67

result:

ok OK

Test #37:

score: 0
Accepted
time: 3ms
memory: 3732kb

input:

18 26 9
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
1 17
2 16
3 15
4 14
5 13
6 12
7 11
8 10
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
1 18

output:

18
7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6

result:

ok OK

Test #38:

score: 0
Accepted
time: 4ms
memory: 3812kb

input:

150 224 75
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 1...

output:

150
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 1 2 3 4 5 6...

result:

ok OK

Test #39:

score: 0
Accepted
time: 3ms
memory: 3800kb

input:

150 224 75
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 1...

output:

150
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 1 2 3 4 5 6...

result:

ok OK

Test #40:

score: 0
Accepted
time: 4ms
memory: 3708kb

input:

150 223 75
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20
21 22
23 24
25 26
27 28
29 30
31 32
33 34
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50
51 52
53 54
55 56
57 58
59 60
61 62
63 64
65 66
67 68
69 70
71 72
73 74
75 76
77 78
79 80
81 82
83 84
85 86
87 88
89 90
91 92
93 94
95 96
97 98
99 1...

output:

-1

result:

ok OK: both impossible

Test #41:

score: 0
Accepted
time: 5ms
memory: 3836kb

input:

150 10933 3
94 134
61 132
60 136
5 69
85 132
14 138
8 16
35 113
53 136
75 115
7 63
14 139
39 54
47 92
45 123
74 139
44 140
39 85
44 100
3 148
33 37
35 137
16 68
113 120
18 129
19 145
22 147
72 135
21 98
37 98
87 141
15 43
93 116
39 52
9 104
33 83
58 150
72 83
73 120
10 68
2 117
133 142
107 122
51 97...

output:

3
1 60 136

result:

ok OK