Submission #1870965

---

Source Code Expand

#pragma GCC optimize ("O3")
//#pragma GCC target ("avx")
//#include <emmintrin.h>
#include <bits/stdc++.h>
#include <sys/time.h>
 
//-----------------------------------------------------------------------//
// Hokkaido Univ.& Hitachi 2nd 
// https://beta.atcoder.jp/contests/hokudai-hitachi2017-2/
// 
//-----------------------------------------------------------------------//
//
//
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
#define cauto(x, v) for(const auto& x: (v))
 
using namespace std;
typedef int64_t ll;
typedef uint64_t ull;
typedef double DBL;
 
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<int, VI> PIV;
typedef array<int, 8> A8;
 
#ifdef LOCAL_HERE
#define _P(...) (void)fprintf(stderr, __VA_ARGS__)
	const double cycles_ini = 2300000.0;
	const double TLMT_ini = 9810.0 ;
	void dbg(){ cerr << "\n"; }  
	template <typename T1,typename ...T2>
	void dbg(const T1& p1, const T2&...pr){ cerr << p1 << ": "; dbg(pr...);}
#else
#define _P(...)
	const double cycles_ini = 2800000.0;
	const double TLMT_ini = 29800.0;
	void dbg(...){  }  
#endif
 
class Timer{
private:
	double get_sec()
	{
		ull crdt = rdtsc();
		double rtn = (double)(crdt - s_rdtsc)/ cycles_per_sec;
		if(rtn > tadj  ){ adjf(); tadj *= 2; }
		return rtn;
	}
	ull s_rdtsc, tadj = 2000;
	double ms_stim, cycles_per_sec;
	ull rdtsc(){
#if defined(_MSC_VER)
		return __rdtsc();
#elif defined(__amd64)
		ull a, d;
		__asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); 
		return (d<<32) | a;
#else
		ull x;
		__asm__ volatile ("rdtsc" : "=A" (x)); 
		return x;
#endif
	}
	double get_ms(){
#ifdef _MSC_VER
		return (double)GetTickCount(); 
#else
		struct timeval t; gettimeofday(&t, NULL);
		return  (double)t.tv_sec * 1000 + (double)t.tv_usec / 1000;
#endif
	}
	void adjf(){
		double ctim = get_ms();
		cycles_per_sec = (double)(rdtsc() - s_rdtsc)/ (ctim - ms_stim);
	}
 
public:
	//Timer() { start();}
	void start() {
		cycles_per_sec = cycles_ini;
		ms_stim = get_ms();
		s_rdtsc = rdtsc();
	}
	double get_elapsed() { return  get_sec(); }
	double get_cyc(){ return cycles_per_sec; }
};
 
 
class xorshift{
public:
	xorshift(){ xorshift(88675123U);}
	xorshift(uint32_t Seed){
		w=1812433253U * (Seed ^ (Seed >> 30));
		for(int i=0;i<23;i++) next();
	}
	uint32_t  next(){
		uint32_t t = (x ^ (x << 11));
		x = y; y = z; z = w;
		return  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}
	int  next(int Min, int Max){ return (int)(next()% (Max - Min + 1)) + Min; }
private:
	uint32_t x =123456789U , y= 362436069U, z= 521288629U, w = 88675123U;
};
 
//mt19937 mran(20171128);
//int xran(int su){ return mran()%su;};
xorshift xorran(20171115);//(uint32_t)time(nullptr));//(20171128)
int xran(int su){ return xorran.next() % su;}

// ---------------------------------------------------------------------------
Timer tm01;
const DBL TLMT = TLMT_ini;
DBL CTM;
int V, E, VC, EC;
vector<int> G[512];
//vector<vector<bool>> GE;
bool GE[3605][3605];
vector<int> GR[3605];
VI  CVE;
int VSQ, CHG;
int C[5]={};
PIV BST;
PIV NBST;
int8_t  VMP[512][512];
int16_t DVN[4000];
vector<array<int16_t,2>> NEE;
// ---------------------------------------------------------------------------
 
 
 
 
struct Sts{
	int pt=0;
	VI vv;
	bool operator<(const Sts& b)  const { return  pt > b.pt; }
	bool operator==(const Sts& b) const { return  vv == b.vv; }
};

inline int ptct0(VI& iv){
	int rtn =0;
	for(auto& x: NEE){
		if(GE[iv[x[0]]][iv[x[1]]]) rtn += 1; //x[2];
	}
	return rtn;
}
 
 
 
inline int dr8w(int ns, A8& ary){
	const int dr[]={0,1,0,-1,1,1,-1,-1,0};
	int rtn =0;
	int yy = DVN[ns], xx = ns - (yy * VSQ);
	//int yy = ns / VSQ, xx = ns - (yy * VSQ);
	rep(i, 8){
		int ny = yy + dr[i],  nx = xx + dr[i+1];
		if(ny <0 || ny >=VSQ || nx <0 || nx >=VSQ ) continue;
		int ads = ny * VSQ + nx;
		ary[rtn] = ads;
		rtn++;
	}
	return rtn;
}
void mkjun(VI& vio, VI& wsq){
	
	vector<VI> dt(V);
	
	rep(i, V){
		int ct=0, pt=0, mx =0;
		for(auto& cr: G[i]){
			ct++;
			pt += 1; //cr.second;
			mx = max(mx, 1); //cr.second);
		}
		dt[i] = VI{i, ct, pt, mx};
	}
	sort(all(dt), [&](VI a, VI b){ return a[1] > b[1];});
	
	vio.assign(V, -1);
	int er=0;
	rep(i,V) if(dt[i][1] > 1) vio[er++] = dt[i][0];
	rep(i,V) if(dt[i][1] <=1) vio[er++] = dt[i][0];
	//cauto(z, vio) cerr<<z <<" "; cerr<<"\n";
	
	int cry = VSQ >>1, crx=VSQ >>1;
	
	const int ds[] = { 0, 1, 0, -1,0};
	VI seq ={cry*VSQ + crx};
	
	int crd = 0, pmx =1;
	rep2(i, 1, VSQ+1){
		rep(j, 2){
			rep(k, i){
				cry += ds[crd]; crx += ds[crd +1];
				//_P("%d:%d:%d ",cry, crx,crd);
				if(cry <0 || crx<0 || cry>=VSQ || crx >= VSQ) goto wends;
				seq.push_back(cry*VSQ + crx);
				if(cry*VSQ + crx > VSQ*VSQ) goto wends;
			}
			crd = (crd+1)%4;
		}
	}
	wends:;
	//cauto(z, seq) cerr<<z <<" "; cerr<<"\n";
	VI wq(VC);
	wsq.clear();
	for(auto z: seq) if(z<VC && wq[z] ==0 && CVE[z] > 2){
		wq[z] = 1;
		wsq.push_back(z);
	}
	rep(i, VC) if(wq[i] ==0) wsq.push_back(i);
	//cauto(z, wsq) cerr<<z <<" "; cerr<<"\n";
}
 
VI mkdt0(){
	VI vv(V, -1), zve(VC, -1);
	VI xcv, xcve;
 
	mkjun(xcv, xcve);
 
	
	
	rep(i, V){
		int bk = i, k;
		rep(bk, VC){
			k = xcve[bk];
			if( vv[bk] >=0 || zve[k] >=0) continue;
			else break;
		}
		//cnd2.push_back(k);
		vv[bk] = k;
		zve[k] = i;
	}
	//for(auto x :vv) _P("%d, ",x); _P("\n");
	return vv;
}
 
 
PIV updt30(const PIV& inv){
 
	auto rv = inv.second;
	VI zve(VC, -1);
	rep(q, V) if(rv[q] >=0) zve[rv[q]] = q;
	
	rep(q1, V){
		if((CTM = tm01.get_elapsed()) > TLMT -20) break;
		rep2(q2, q1+1, V){
			int t1= rv[q1], sm1 = 0;
			int t2 =rv[q2], sm2 = 0;
			//A8 av1, av2;
			
			for(auto a1: GR[t1]){
				sm1 += VMP[zve[t1]][zve[a1]];
				sm2 += VMP[zve[t2]][zve[a1]];
			}
			for(auto a2: GR[t2]){
				sm1 += VMP[zve[t2]][zve[a2]];
				sm2 += VMP[zve[t1]][zve[a2]];
			}

			if(GE[t1][t2]) sm1 -= VMP[zve[t1]][zve[t2]];
			if(GE[t1][t2]) sm2 += VMP[zve[t1]][zve[t2]]; //補填!!
			//if(sm2>sm1) dbg(t1,t2,sm1,sm2);
			if(sm2 > sm1){
				rv[zve[t2]] = t1;
				rv[zve[t1]] = t2;
				swap(zve[t1], zve[t2]);
				//break;
			}
		}
	
	}
	int cpt = ptct0(rv);
	PIV rtn;
	rtn.first = cpt;
	rtn.second = move(rv);
	return rtn;
}


PIV updt40(const PIV& inv){
 
	auto rv = inv.second;
	VI zve(VC, -1);
	//static array<int,3605> zve;
	//zve.fill(-1);
	//static int zve[3605];
	//memset(zve, -1, sizeof zve);
	rep(q, V) if(rv[q] >=0) zve[rv[q]] = q;
	
	int q1 = xran(V), q2=-1;
	
	if(xran(100) <25){
		VI cdd;
		for(auto& e1: GR[rv[q1]]){
			if(zve[e1] >=0) cdd.push_back(e1);
		}
		int q2zv = cdd[xran(sz(cdd))];
		q2 = zve[q2zv];
	}else{
		q2 = xran(V);
	}
	
	int t1= rv[q1], sm1 = 0;
	int t2 =rv[q2], sm2 = 0;
	
	for(auto& a1: GR[t1]) sm1 += VMP[zve[t1]][zve[a1]];
	for(auto& a2: GR[t2]) sm1 += VMP[zve[t2]][zve[a2]];
	rv[zve[t2]] = t1;
	rv[zve[t1]] = t2;
	swap(zve[t1], zve[t2]);

	for(auto& a1: GR[t1]) sm2 += VMP[zve[t1]][zve[a1]];
	for(auto& a2: GR[t2]) sm2 += VMP[zve[t2]][zve[a2]];
	PIV rtn;
	rtn.first = inv.first + sm2 - sm1;
	rtn.second = move(rv);
	return rtn;
}
 
 
void updt00(const PIV ivi){
	int sct=0, uct=0;
	PIV rtn = ivi;
	for(; (CTM = tm01.get_elapsed()) < TLMT - 50; sct++){
		auto rc = updt30(rtn);
		if(rc.first > rtn.first){
			rtn = rc; uct++;
		}else break;
	}
	if(rtn.first>NBST.first) NBST = rtn;
	
}

void updt15(const PIV ivi){
	int sct=0, uct=0;
	int rtpt = ivi.first, svpt = ivi.first;
	auto rv = ivi.second;
	dbg("sta",rtpt,svpt);
	static int zve[3605];
	memset(zve, -1, sizeof zve);
	rep(q, V) if(rv[q] >=0) zve[rv[q]] = q;
	
	//VI vmx(V);
	//int svq1, svq2;
	//rep(i, V){
	//	int t = rv[i];
	//	for(auto& aa: GR[t]) vmx[i] += VMP[zve[t]][zve[aa]];
	//}

	for(; sct%10 !=9 || (CTM = tm01.get_elapsed()) < TLMT - 80 ; sct++){
		int q1, q2;
		svpt = rtpt;
		//auto svrv = rv;
		
			
		q1 = xran(V), q2=-1;
		
		if(xran(100) <25){
			VI cdd;
			for(auto& e1: GR[rv[q1]]){
				if(zve[e1] >=0) cdd.push_back(e1);
			}
			int q2zv = cdd[xran(sz(cdd))];
			q2 = zve[q2zv];
		}else{
			q2 = xran(V);
		}
		
		
		int t1= rv[q1], sm1 = 0;
		int t2 =rv[q2], sm2 = 0;
		
		for(auto& a1: GR[t1]) sm1 += VMP[zve[t1]][zve[a1]];
		for(auto& a2: GR[t2]) sm1 += VMP[zve[t2]][zve[a2]];
		swap(rv[q1], rv[q2]);
		zve[rv[q1]] = q1;
		zve[rv[q2]] = q2;
		//vmx[q1]=0; vmx[q2]=0;
		
		t1 = rv[q1]; t2 = rv[q2];
		for(auto& a1: GR[t1]) sm2 += VMP[zve[t1]][zve[a1]];
		for(auto& a2: GR[t2]) sm2 += VMP[zve[t2]][zve[a2]];
		rtpt = svpt + sm2 - sm1;
		
		//if(sct < 1000) dbg(sct,rtpt,svpt,NBST.first,sm1,sm2);
		if(rtpt >NBST.first){
			NBST = PIV(rtpt, rv);
			uct++;
			//_P("%d ",sct);
		}
		const DBL znj = (TLMT-CTM)/TLMT ;
		const int dif = svpt - rtpt;
		const int rsu = 500000;
		if(rtpt > svpt){
		}else if( xran(rsu) < rsu * exp(-dif /(  znj*znj))){
			//rtn = move(rc);
			//swap(rtn.second[q1], rtn.second[q2]);

		}else{
			//rv = svrv;
			swap(rv[q1], rv[q2]);
			zve[rv[q1]] = q1;
			zve[rv[q2]] = q2;
			rtpt = svpt;
			
		}
		//if(sct < 1000) dbg(sct,rtpt,svpt,NBST.first,sm1,sm2);
		
	}
	_P("[updt10] sct=%d uct=%d\n", sct, uct);
}

void updt15SSv(const PIV ivi){
	int sct=0, uct=0;
	PIV rtn = ivi, rc;
	static int zve[3605];
	memset(zve, -1, sizeof zve);
	rep(q, V) if(rtn.second[q] >=0) zve[rtn.second[q]] = q;
	PII svzve;
	for(; sct%10 !=9 || (CTM = tm01.get_elapsed()) < TLMT - 80 ; sct++){
		//rep(i, kz-1) swap(rtn.second[rt[i]],rtn.second[rt[(i+1)%V]]);
		//rc = updt40(rtn);
		int q1, q2;
		int svpt = rtn.first;
		{
			auto rv = rtn.second;
			
			q1 = xran(V), q2=-1;
			
			if(xran(100) <25){
				VI cdd;
				for(auto& e1: GR[rv[q1]]){
					if(zve[e1] >=0) cdd.push_back(e1);
				}
				int q2zv = cdd[xran(sz(cdd))];
				q2 = zve[q2zv];
			}else{
				q2 = xran(V);
			}
			
			
			
			int t1= rv[q1], sm1 = 0;
			int t2 =rv[q2], sm2 = 0;
			
			for(auto& a1: GR[t1]) sm1 += VMP[zve[t1]][zve[a1]];
			for(auto& a2: GR[t2]) sm1 += VMP[zve[t2]][zve[a2]];
			rv[zve[t2]] = t1;
			rv[zve[t1]] = t2;
			svzve = PII(t1,t2);
			swap(zve[t1], zve[t2]);

			t1 = rv[q1]; t2 = rv[q2];
			for(auto& a1: GR[t1]) sm2 += VMP[zve[t1]][zve[a1]];
			for(auto& a2: GR[t2]) sm2 += VMP[zve[t2]][zve[a2]];
			//PIV rtn;
			rc.first = rtn.first + sm2 - sm1;
			rc.second = move(rv);
			//rtn.first += sm2 -sm1;
		}
		
		if(rc.first >NBST.first){
			NBST = rc;
			uct++;
			//_P("%d ",sct);
		}
		if(rc.first >= rtn.first){
			rtn = move(rc);
		}else{
			const DBL znj = (TLMT-CTM)/TLMT ;
			//const int dif = rtn.first - rc.first;
			const int rsu = 500000;
			if(xran(rsu) < rsu * exp(-2 /( znj * znj))){
			//_P("e ");	
				rtn = move(rc);
				//swap(rtn.second[q1], rtn.second[q2]);
			}else{
				swap(zve[svzve.first], zve[svzve.second]);
				//rtn.second[zve[svzve.first]] = svzve.first;
				//rtn.second[zve[svzve.second]] = svzve.second;
			}
		}
		
	}
	_P("[updt10] sct=%d uct=%d\n", sct, uct);
}
void updt15Sv(const PIV ivi){
	int sct=0, uct=0;
	PIV rtn = ivi, rc;
	for(; sct%10 !=9 || (CTM = tm01.get_elapsed()) < TLMT - 80 ; sct++){
		//rep(i, kz-1) swap(rtn.second[rt[i]],rtn.second[rt[(i+1)%V]]);
		rc = updt40(rtn);
		
		if(rc.first >= rtn.first) rtn = rc; 
		if(rc.first >NBST.first){
			NBST = rc;
			uct++;
			//_P("%d ",sct);
		}else{
			const DBL znj = (TLMT-CTM)/TLMT ;
			//const int dif = rtn.first - rc.first;
			const int rsu = 500000;
			if(xran(rsu) < rsu * exp(-2 /( znj * znj))){
			//_P("e ");	
				rtn = rc;
			};
			//rtn.second = NBST.second;
		}
		
	}
	_P("[updt10] sct=%d uct=%d\n", sct, uct);
}

void updt10(const PIV ivi){
	int sct=0, uct=0, kz=0;
	PIV rtn = ivi, rc;
	for(; (CTM = tm01.get_elapsed()) < TLMT - 50 ; sct++){
		kz = kz<7? kz +1: 2;
		if(CTM > 6000) kz=2;
	//auto svcr = rtn.second;
		VI  rt(kz), old(kz); //, nw(kz);
		rep(i, kz){
			rt[i] = xran(V);
			old[i] = rtn.second[rt[i]];
		}
		rep(i, kz-1) swap(rtn.second[rt[i]],rtn.second[rt[(i+1)%V]]);
		for(;;){
			rc = updt30(rtn);
			if(rc.first > rtn.first) rtn = rc; 
			else break;
		}
		if(rtn.first >NBST.first){
			NBST = rtn;
			uct++;
			//_P("%d ",sct);
		}else{
			rep(k, kz) rtn.second[rt[k]] = old[k];
			//rtn.second = NBST.second;
		}
		//if(sct >10000){
			//auto rz  = updt38(NBST);
			//if(rz.first >NBST.first) NBST = rz;
		//}
	}
	_P("[updt10] sct=%d uct=%d\n", sct, uct);
}	


void bfstr(int sta2, const VI& rv,  VI& zve, const VI& cnd, vector<VI>& rv2){
	const int dr[]={-1,1,1,-1,-1,0,1,0,-1};
	set<int> st;
	for(auto z: cnd) st.insert(rv[z]);
	const int inf = 1<<28;
	int start = rv[sta2];
	VI dd(VC, inf), bf(VC, -1);
	queue< int > que;
	que.push(start); dd[start]=0;bf[start] =-9;
	while(!que.empty()){
		int cr = que.front();
		int cy =cr/VSQ, cx = cr%VSQ;
		que.pop();
		rep(i,8){
			int ny=cy+dr[i], nx=cx+dr[i+1];
			if(ny<0 || ny>=VSQ || nx<0 || nx>=VSQ) continue;
			if(zve[ny * VSQ + nx] <0  && dd[ny * VSQ + nx] == inf){
				que.push( ny * VSQ + nx );
				dd[ny * VSQ + nx] = dd[cy * VSQ + cx] + 1;
				bf[ny * VSQ + nx] = cy * VSQ + cx;
			}else if(dd[ny * VSQ + nx] == inf && st.count(ny * VSQ + nx)){
				dd[ny * VSQ + nx] = dd[cy * VSQ + cx] + 1;
				bf[ny * VSQ + nx] = cy * VSQ + cx;
			}
		}
	}
	//for(auto x :dd) _P("%d ",x); _P("  <--dd\n");
	//for(auto x :zve) _P("%d ",x); _P("  <--zve\n");

	VI rtn;
	for(auto z: cnd){
		int zz = rv[z];
		
		
		if(dd[zz] > 90000) continue;
		int j = bf[zz];
		for(; bf[j] !=-9;j =bf[j]){
			rtn.push_back(j);
		}
	}
	sort(all(rtn)); rtn.erase(unique(all(rtn)), rtn.end());	
	VI rt2;
	for(auto x :rtn) if(zve[x] <0) rt2.push_back(x);
	//for(auto x :rtn) _P("%d ",x); _P("  <--rtn\n");
	
	for(auto x :rt2){
		zve[x] = sta2;
		rv2[sta2].push_back(x);
	}

}



vector<VI> endup00(){
	auto rv= NBST.second;
	VI zve(VC, -1);
	rep(q, V) if(rv[q] >=0) zve[rv[q]] = q;
	
	vector<vector<bool>> atr(V, vector<bool>(V));
	for(auto& x: NEE) if(GE[rv[x[0]]][rv[x[1]]]){
		 atr[x[0]][x[1]] =1;  atr[x[1]][x[0]] =1;
	}

	vector<VI> hlz(VSQ), vtc(VSQ);

	rep(i,VSQ){
		int mn=99999, mx=0;
		rep(j,VSQ) if(zve[i*VSQ+j] >=0){
			mn = min(mn, i*VSQ + j);
			mx = max(mx, i*VSQ + j);
		}
		if(mn !=99999 ) hlz[i] = VI{mn,mx};
	}
	
	rep(i,VSQ){
		int mn=99999, mx=0;
		rep(j,VSQ) if(zve[j*VSQ+i] >=0){
			mn = min(mn, j*VSQ + i);
			mx = max(mx, j*VSQ + i);
		}
		if(mn !=99999 ) vtc[i] = {mn, mx};
	}
	
	VI vno;
	rep(i,VSQ){
		if(sz(hlz[i])>1){
			vno.push_back(zve[hlz[i][0]]);
			vno.push_back(zve[hlz[i][1]]);
		}
		if(sz(vtc[i])>1){
			vno.push_back(zve[vtc[i][0]]);
			vno.push_back(zve[vtc[i][1]]);
		}
	}
	sort(all(vno));
	vno.erase(unique(all(vno)), vno.end());
	//for(auto x :vno) _P("%d, ",x); _P("\n");
	int nz=sz(vno);
	VI ctsu(V);
	rep(i,nz) rep(j,nz){
		if(VMP[vno[i]][vno[j]] && !atr[vno[i]][vno[j]]){
			//if(i<j) _P("%d:%d  ",vno[i],vno[j]);
			ctsu[vno[i]]++;
		}
	}

	vector<VI> rv2(V);
	rep(i, V) rv2[i] = VI{rv[i]};

	//for(auto x :ctsu) _P("%d, ",x); _P("\n");
	rep(i,100){ //if(3 > 9){
		if((CTM = tm01.get_elapsed()) > TLMT -10) break;
		int ano = max_element(all(ctsu)) - ctsu.begin();
		if(ctsu[ano] <=0) break;
		VI cnd;
		rep(i, nz) if(VMP[ano][vno[i]] && !atr[ano][vno[i]]) cnd.push_back(vno[i]);
		bfstr(ano, rv, zve, cnd, rv2);
		ctsu[ano] = 0;
	}
	return rv2;
}

void zuru(){
	/*
	if(V==7 && E==14 && VC==25 && EC==72){
		vector<string> ans{
			"5 7 8 9 11 15","4 17 23 24 20","1 19",
			"1 18","1 14","1 12","1 13"
		};
		vector<VI> dt{
			{1, 2},{1, 3},{1, 6},{1, 7},{2, 4},{2, 5},{2, 6},{2, 7},
			{3, 5},{3, 7},{4, 5},{4, 6},{4, 7},{5, 7}
		};
		bool ck=true;
		for(auto x: dt) if(VMP[x[0]-1][x[1]-1] ==false ) ck=false;
		if(ck){
			rep(i,7) printf("%s\n", ans[i].c_str());
			exit(0);
		}
	}
	*/
}

void m_init(){
	int rsf;
	rsf =scanf("%d %d",&V, &E);
	//CV.assign(V,0);
	NEE.resize(E);
	rep(i, E){
		int u, v;
		rsf =scanf("%d %d", &u, &v);
		G[u-1].emplace_back(v-1);
		G[v-1].emplace_back(u-1);
		//CV[u-1] += w; CV[v-1] +=w;
		VMP[u-1][v-1] = VMP[v-1][u-1] = 1;
		NEE[i] = array<int16_t,2>{(int16_t)(u-1), (int16_t)(v-1)};
	}
	rsf =scanf("%d %d", &VC, &EC);
	//GE.assign(VC+4, vector<bool>(VC+4, false));
	CVE.assign(VC,0);
	rep(i, EC){
		int a, b;
		rsf =scanf("%d %d", &a, &b);
		GE[(a-1)][(b-1)] = 1;
		GE[(b-1)][(a-1)] = 1;
		GR[(a-1)].push_back(b-1);
		GR[(b-1)].push_back(a-1);
		CVE[a-1]++; CVE[b-1]++;
	}
 
	rep(i, V) sort(all(G[i]));
	VSQ = (int)sqrt(VC);
	CHG = V<300 && E<15000? 450: 300;
	VI wv(V); iota(all(wv),0);
	BST = PIV(0, wv);
	//dssf.init();
	rep(i,4000) DVN[i] = i / VSQ;
	//zuru();
}
	
int main() {
	tm01.start();
	m_init();
	auto rc = mkdt0();
	int wp = ptct0(rc);
	if(BST.first < wp) BST = PIV( wp, rc);
	_P("mkdt end  tim=%.2f, pt=%d\n",CTM, BST.first);
	NBST = move(BST);
	
	updt00(NBST);
	_P("up00 end  tim=%.2f, pt=%d\n",CTM, NBST.first);
 
	updt15(NBST);
	
	auto rvv = endup00();
	rep(i, V){
		//printf("%d %d\n", 1, NBST.second[i] +1);
		printf("%d", sz(rvv[i]));
		cauto(z, rvv[i]) printf(" %d", z+1);
		printf("\n");
	}
	dbg("test", V);
	_P("time=%.2f cycle=%.4f\n",tm01.get_elapsed(),tm01.get_cyc());
	_P("V:E:VC:EC=%d:%d:%d:%d\n",V, E, VC, EC);
	_P("Score=%d\n", NBST.first);
	
	return 0;
}

Submission Info

Judge Result