QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#725785	#8555. Dress to Impress	TheZone	AC ✓	278ms	54544kb	C++20	17.4kb	2024-11-08 20:02:18	2024-11-08 20:02:18

Judging History

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

[2024-11-08 20:02:18]
评测

测评结果：AC
用时：278ms
内存：54544kb

查看

[2024-11-08 20:02:18]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 rng(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int inf=0x20202020;
typedef int flowt;
namespace flow {
	const int M=100000,N=1000;
	int y[M],nxt[M],gap[N],fst[N],c[N],pre[N],q[N],dis[N];
	flowt f[M];
	int S,T,tot,Tn;
	void init(int s,int t,int tn) {
		tot=1; assert(tn<N);
		rep(i,0,tn) fst[i]=0;
		S=s;T=t;Tn=tn;
	}
	void add(int u,int v,flowt c1,flowt c2=0) {
		tot++;y[tot]=v;f[tot]=c1;nxt[tot]=fst[u];fst[u]=tot;
		tot++;y[tot]=u;f[tot]=c2;nxt[tot]=fst[v];fst[v]=tot;
	}
	flowt sap() {
		int u=S,t=1;flowt flow=0;
		rep(i,0,Tn) c[i]=fst[i],dis[i]=Tn,gap[i]=0;
		q[0]=T;dis[T]=0;pre[S]=0;
		rep(i,0,t) {
			int u=q[i];
			for (int j=fst[u];j;j=nxt[j]) if (dis[y[j]]>dis[u]+1&&f[j^1]) 
				q[t++]=y[j],dis[y[j]]=dis[u]+1;
		}
		rep(i,0,Tn) gap[dis[i]]++;
		while (dis[S]<=Tn) {
			while (c[u]&&(!f[c[u]]||dis[y[c[u]]]+1!=dis[u])) c[u]=nxt[c[u]];
			if (c[u]) {
				pre[y[c[u]]]=c[u]^1;
				u=y[c[u]];
				if (u==T) {
					flowt minf=inf;
					for (int p=pre[T];p;p=pre[y[p]]) minf=min(minf,f[p^1]);
					for (int p=pre[T];p;p=pre[y[p]]) f[p^1]-=minf,f[p]+=minf;
					flow+=minf;u=S;
				}
			} else {
				if (!(--gap[dis[u]])) break;
				int mind=Tn;
				c[u]=fst[u];
				for (int j=fst[u];j;j=nxt[j]) if (f[j]&&dis[y[j]]<mind) 
					mind=dis[y[j]],c[u]=j;
				dis[u]=mind+1;
				gap[dis[u]]++;
				if (u!=S) u=y[pre[u]];
			}
		}
		return flow;
	}
};

const int N=5010;
VI used[N];
vector<VI> res;
bool mark[N*100];
void coloring(vector<vector<int>> edge) {
    int n=SZ(edge);
    int d=SZ(edge[0]);
    if (d==1) {
        VI pr;
        rep(i,0,n) pr.pb(edge[i][0]);
        res.pb(pr);
    } else if (d%2==0) {
        vector<vector<PII>> G(2*n);
        vector<int> cir;
        int tot=0;
        rep(i,0,n) rep(j,0,d) {
            int v=i,w=edge[i][j]+n;
            G[v].pb(mp(w,tot)); G[w].pb(mp(v,tot));
            ++tot;
        }
        vector<bool> vis1(2*n, false), vis2(tot, false);
        vector<PII> stk;
        for (int s = 0; s < 2*n; s++) if (!vis1[s]) {
            stk.clear();
            stk.emplace_back(s, -1);
            while (!stk.empty()) {
                int v, w, e; tie (v, e) = stk.back(); vis1[v] = true;
                if (G[v].empty()) { cir.emplace_back(e); stk.pop_back(); }
                else {
                    tie (w, e) = G[v].back(); G[v].pop_back();
                    if (!vis2[e]) { vis2[e] = true; stk.emplace_back(w, e); }
                }
            }
            cir.pop_back();
        }
        vector<VI> e1(n),e2(n);
        assert(SZ(cir)==n*d);
        rep(i,0,n*d) {
            int u=cir[i]/d;
            if (i%2==0) e1[u].pb(edge[u][cir[i]%d]);
            else e2[u].pb(edge[u][cir[i]%d]);
        }
        coloring(e1);
        coloring(e2);
    } else {
        vector<int> P(n),L(n,-1),R(n,0);
        rep(i,0,n) P[i]=i;
        shuffle(P.begin(),P.end(),rng);
        for(auto p0:P) {
            int p=p0;
            VI S;
            while (p!=-1) {
                int q=-1;
                do q=edge[p][rng()%d]; while(L[q]==p);
                while(mark[q]) mark[S.back()]=false,S.pop_back();
                p=L[q],mark[q]=true,S.pb(q);
            }
            p=p0;
            for(auto s:S)mark[s]=false,swap(p,L[s]);
        }
        VI pr;
        rep(i,0,n) R[L[i]]=i;
        rep(i,0,n) pr.pb(R[i]);
        rep(i,0,n) edge[i].erase(find(all(edge[i]),R[i]));
        res.pb(pr);
        coloring(edge);
    }
}

int n,m,c,k,id[N];
PII E[N];
vector<int> wt[222][222];
int main() {
	scanf("%d%d%d%d",&n,&m,&c,&k);
	rep(i,0,c) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u; --v;
		E[i]=mp(u,v);
	}
	int l=0,r=c+1;
	auto check=[&](int x) {
		flow::init(n+m,n+m+1,n+m+2);
		rep(i,0,n) flow::add(n+m,i,x);
		rep(i,0,m) flow::add(i+n,n+m+1,x);
		rep(i,0,c) {
			id[i]=flow::tot+1;
			flow::add(E[i].fi,E[i].se+n,1);
		}
		int w=flow::sap();
		if (w<k*x) return false;
		rep(i,0,m) flow::add(i+n,n+m+1,inf);
		int w2=flow::sap();
		if (w+w2<n*x) return false;
		return true;
	};
	while (l+1<r) {
		int md=(l+r)>>1;
		if (check(md)) l=md; else r=md;
	}
	int x=l;
	printf("%d\n",x);
	if (x==0) {
		return 0;
	}
	check(x);
	rep(i,0,c) if (flow::f[id[i]]==0) {
		used[E[i].se].pb(i);
	}
	vector<VI> eg(n+m);
	int tl=n,tr=m,dg=0;
	rep(i,0,m) if (SZ(used[i])<x) {
		//printf("? %d\n",i);
		for (auto y:used[i]) {
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,0,x-SZ(used[i])) {
			if (SZ(eg[tl])==x) tl++;
			eg[tl].pb(i);
		}
	} else {
		rep(j,0,x) {
			int y=used[i][j];
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,x,SZ(used[i])) {
			if (dg==x) tr++,dg=0;
			int z=tr;
			int y=used[i][j];
			eg[E[y].fi].pb(z);
			wt[E[y].fi][z].pb(y);
			dg++;
		}
	}
	//printf("? %d %d\n",tl,tr);
	if (SZ(eg[tl])>0) {
		while (SZ(eg[tl])<x) {
			eg[tl].pb(tr),dg++;
		}
	}
	if (dg==x) tr++,dg=0;
	if (SZ(eg[tl])==x) ++tl;
	//printf("? %d %d %d\n",tl,tr,dg);
	assert(tl==tr&&dg==0);
	eg.resize(tl);
	coloring(eg);
	rep(i,0,x) {
		rep(u,0,n) {
			int v=res[i][u];
			assert(!wt[u][v].empty());
			printf("%d ",wt[u][v].back()+1); wt[u][v].pop_back();
		}
		puts("");
	}
}
/*#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 rng(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int inf=0x20202020;
typedef int flowt;
namespace flow {
	const int M=100000,N=1000;
	int y[M],nxt[M],gap[N],fst[N],c[N],pre[N],q[N],dis[N];
	flowt f[M];
	int S,T,tot,Tn;
	void init(int s,int t,int tn) {
		tot=1; assert(tn<N);
		rep(i,0,tn) fst[i]=0;
		S=s;T=t;Tn=tn;
	}
	void add(int u,int v,flowt c1,flowt c2=0) {
		tot++;y[tot]=v;f[tot]=c1;nxt[tot]=fst[u];fst[u]=tot;
		tot++;y[tot]=u;f[tot]=c2;nxt[tot]=fst[v];fst[v]=tot;
	}
	flowt sap() {
		int u=S,t=1;flowt flow=0;
		rep(i,0,Tn) c[i]=fst[i],dis[i]=Tn,gap[i]=0;
		q[0]=T;dis[T]=0;pre[S]=0;
		rep(i,0,t) {
			int u=q[i];
			for (int j=fst[u];j;j=nxt[j]) if (dis[y[j]]>dis[u]+1&&f[j^1]) 
				q[t++]=y[j],dis[y[j]]=dis[u]+1;
		}
		rep(i,0,Tn) gap[dis[i]]++;
		while (dis[S]<=Tn) {
			while (c[u]&&(!f[c[u]]||dis[y[c[u]]]+1!=dis[u])) c[u]=nxt[c[u]];
			if (c[u]) {
				pre[y[c[u]]]=c[u]^1;
				u=y[c[u]];
				if (u==T) {
					flowt minf=inf;
					for (int p=pre[T];p;p=pre[y[p]]) minf=min(minf,f[p^1]);
					for (int p=pre[T];p;p=pre[y[p]]) f[p^1]-=minf,f[p]+=minf;
					flow+=minf;u=S;
				}
			} else {
				if (!(--gap[dis[u]])) break;
				int mind=Tn;
				c[u]=fst[u];
				for (int j=fst[u];j;j=nxt[j]) if (f[j]&&dis[y[j]]<mind) 
					mind=dis[y[j]],c[u]=j;
				dis[u]=mind+1;
				gap[dis[u]]++;
				if (u!=S) u=y[pre[u]];
			}
		}
		return flow;
	}
};

const int N=5010;
VI used[N];
vector<VI> res;
bool mark[N*100];
void coloring(vector<vector<int>> edge) {
    int n=SZ(edge);
    int d=SZ(edge[0]);
    if (d==1) {
        VI pr;
        rep(i,0,n) pr.pb(edge[i][0]);
        res.pb(pr);
    } else if (d%2==0) {
        vector<vector<PII>> G(2*n);
        vector<int> cir;
        int tot=0;
        rep(i,0,n) rep(j,0,d) {
            int v=i,w=edge[i][j]+n;
            G[v].pb(mp(w,tot)); G[w].pb(mp(v,tot));
            ++tot;
        }
        vector<bool> vis1(2*n, false), vis2(tot, false);
        vector<PII> stk;
        for (int s = 0; s < 2*n; s++) if (!vis1[s]) {
            stk.clear();
            stk.emplace_back(s, -1);
            while (!stk.empty()) {
                int v, w, e; tie (v, e) = stk.back(); vis1[v] = true;
                if (G[v].empty()) { cir.emplace_back(e); stk.pop_back(); }
                else {
                    tie (w, e) = G[v].back(); G[v].pop_back();
                    if (!vis2[e]) { vis2[e] = true; stk.emplace_back(w, e); }
                }
            }
            cir.pop_back();
        }
        vector<VI> e1(n),e2(n);
        assert(SZ(cir)==n*d);
        rep(i,0,n*d) {
            int u=cir[i]/d;
            if (i%2==0) e1[u].pb(edge[u][cir[i]%d]);
            else e2[u].pb(edge[u][cir[i]%d]);
        }
        coloring(e1);
        coloring(e2);
    } else {
        vector<int> P(n),L(n,-1),R(n,0);
        rep(i,0,n) P[i]=i;
        shuffle(P.begin(),P.end(),rng);
        for(auto p0:P) {
            int p=p0;
            VI S;
            while (p!=-1) {
                int q=-1;
                do q=edge[p][rng()%d]; while(L[q]==p);
                while(mark[q]) mark[S.back()]=false,S.pop_back();
                p=L[q],mark[q]=true,S.pb(q);
            }
            p=p0;
            for(auto s:S)mark[s]=false,swap(p,L[s]);
        }
        VI pr;
        rep(i,0,n) R[L[i]]=i;
        rep(i,0,n) pr.pb(R[i]);
        rep(i,0,n) edge[i].erase(find(all(edge[i]),R[i]));
        res.pb(pr);
        coloring(edge);
    }
}

int n,m,c,k,id[N];
PII E[N];
vector<int> wt[222][222];
int main() {
	scanf("%d%d%d%d",&n,&m,&c,&k);
	rep(i,0,c) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u; --v;
		E[i]=mp(u,v);
	}
	int l=0,r=c+1;
	auto check=[&](int x) {
		flow::init(n+m,n+m+1,n+m+2);
		rep(i,0,n) flow::add(n+m,i,x);
		rep(i,0,m) flow::add(i+n,n+m+1,x);
		rep(i,0,c) {
			id[i]=flow::tot+1;
			flow::add(E[i].fi,E[i].se+n,1);
		}
		int w=flow::sap();
		if (w<k*x) return false;
		rep(i,0,m) flow::add(i+n,n+m+1,inf);
		int w2=flow::sap();
		if (w+w2<n*x) return false;
		return true;
	};
	while (l+1<r) {
		int md=(l+r)>>1;
		if (check(md)) l=md; else r=md;
	}
	int x=l;
	printf("%d\n",x);
	if (x==0) {
		return 0;
	}
	check(x);
	rep(i,0,c) if (flow::f[id[i]]==0) {
		used[E[i].se].pb(i);
	}
	vector<VI> eg(n+m);
	int tl=n,tr=m,dg=0;
	rep(i,0,m) if (SZ(used[i])<x) {
		//printf("? %d\n",i);
		for (auto y:used[i]) {
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,0,x-SZ(used[i])) {
			if (SZ(eg[tl])==x) tl++;
			eg[tl].pb(i);
		}
	} else {
		rep(j,0,x) {
			int y=used[i][j];
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,x,SZ(used[i])) {
			if (dg==x) tr++,dg=0;
			int z=tr;
			int y=used[i][j];
			eg[E[y].fi].pb(z);
			wt[E[y].fi][z].pb(y);
			dg++;
		}
	}
	//printf("? %d %d\n",tl,tr);
	if (SZ(eg[tl])>0) {
		while (SZ(eg[tl])<x) {
			eg[tl].pb(tr),dg++;
		}
	}
	if (dg==x) tr++,dg=0;
	if (SZ(eg[tl])==x) ++tl;
	//printf("? %d %d %d\n",tl,tr,dg);
	assert(tl==tr&&dg==0);
	eg.resize(tl);
	coloring(eg);
	rep(i,0,x) {
		rep(u,0,n) {
			int v=res[i][u];
			assert(!wt[u][v].empty());
			printf("%d ",wt[u][v].back()+1); wt[u][v].pop_back();
		}
		puts("");
	}
}#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 rng(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int inf=0x20202020;
typedef int flowt;
namespace flow {
	const int M=100000,N=1000;
	int y[M],nxt[M],gap[N],fst[N],c[N],pre[N],q[N],dis[N];
	flowt f[M];
	int S,T,tot,Tn;
	void init(int s,int t,int tn) {
		tot=1; assert(tn<N);
		rep(i,0,tn) fst[i]=0;
		S=s;T=t;Tn=tn;
	}
	void add(int u,int v,flowt c1,flowt c2=0) {
		tot++;y[tot]=v;f[tot]=c1;nxt[tot]=fst[u];fst[u]=tot;
		tot++;y[tot]=u;f[tot]=c2;nxt[tot]=fst[v];fst[v]=tot;
	}
	flowt sap() {
		int u=S,t=1;flowt flow=0;
		rep(i,0,Tn) c[i]=fst[i],dis[i]=Tn,gap[i]=0;
		q[0]=T;dis[T]=0;pre[S]=0;
		rep(i,0,t) {
			int u=q[i];
			for (int j=fst[u];j;j=nxt[j]) if (dis[y[j]]>dis[u]+1&&f[j^1]) 
				q[t++]=y[j],dis[y[j]]=dis[u]+1;
		}
		rep(i,0,Tn) gap[dis[i]]++;
		while (dis[S]<=Tn) {
			while (c[u]&&(!f[c[u]]||dis[y[c[u]]]+1!=dis[u])) c[u]=nxt[c[u]];
			if (c[u]) {
				pre[y[c[u]]]=c[u]^1;
				u=y[c[u]];
				if (u==T) {
					flowt minf=inf;
					for (int p=pre[T];p;p=pre[y[p]]) minf=min(minf,f[p^1]);
					for (int p=pre[T];p;p=pre[y[p]]) f[p^1]-=minf,f[p]+=minf;
					flow+=minf;u=S;
				}
			} else {
				if (!(--gap[dis[u]])) break;
				int mind=Tn;
				c[u]=fst[u];
				for (int j=fst[u];j;j=nxt[j]) if (f[j]&&dis[y[j]]<mind) 
					mind=dis[y[j]],c[u]=j;
				dis[u]=mind+1;
				gap[dis[u]]++;
				if (u!=S) u=y[pre[u]];
			}
		}
		return flow;
	}
};

const int N=5010;
VI used[N];
vector<VI> res;
bool mark[N*100];
void coloring(vector<vector<int>> edge) {
    int n=SZ(edge);
    int d=SZ(edge[0]);
    if (d==1) {
        VI pr;
        rep(i,0,n) pr.pb(edge[i][0]);
        res.pb(pr);
    } else if (d%2==0) {
        vector<vector<PII>> G(2*n);
        vector<int> cir;
        int tot=0;
        rep(i,0,n) rep(j,0,d) {
            int v=i,w=edge[i][j]+n;
            G[v].pb(mp(w,tot)); G[w].pb(mp(v,tot));
            ++tot;
        }
        vector<bool> vis1(2*n, false), vis2(tot, false);
        vector<PII> stk;
        for (int s = 0; s < 2*n; s++) if (!vis1[s]) {
            stk.clear();
            stk.emplace_back(s, -1);
            while (!stk.empty()) {
                int v, w, e; tie (v, e) = stk.back(); vis1[v] = true;
                if (G[v].empty()) { cir.emplace_back(e); stk.pop_back(); }
                else {
                    tie (w, e) = G[v].back(); G[v].pop_back();
                    if (!vis2[e]) { vis2[e] = true; stk.emplace_back(w, e); }
                }
            }
            cir.pop_back();
        }
        vector<VI> e1(n),e2(n);
        assert(SZ(cir)==n*d);
        rep(i,0,n*d) {
            int u=cir[i]/d;
            if (i%2==0) e1[u].pb(edge[u][cir[i]%d]);
            else e2[u].pb(edge[u][cir[i]%d]);
        }
        coloring(e1);
        coloring(e2);
    } else {
        vector<int> P(n),L(n,-1),R(n,0);
        rep(i,0,n) P[i]=i;
        shuffle(P.begin(),P.end(),rng);
        for(auto p0:P) {
            int p=p0;
            VI S;
            while (p!=-1) {
                int q=-1;
                do q=edge[p][rng()%d]; while(L[q]==p);
                while(mark[q]) mark[S.back()]=false,S.pop_back();
                p=L[q],mark[q]=true,S.pb(q);
            }
            p=p0;
            for(auto s:S)mark[s]=false,swap(p,L[s]);
        }
        VI pr;
        rep(i,0,n) R[L[i]]=i;
        rep(i,0,n) pr.pb(R[i]);
        rep(i,0,n) edge[i].erase(find(all(edge[i]),R[i]));
        res.pb(pr);
        coloring(edge);
    }
}

int n,m,c,k,id[N];
PII E[N];
vector<int> wt[222][222];
int main() {
	scanf("%d%d%d%d",&n,&m,&c,&k);
	rep(i,0,c) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u; --v;
		E[i]=mp(u,v);
	}
	int l=0,r=c+1;
	auto check=[&](int x) {
		flow::init(n+m,n+m+1,n+m+2);
		rep(i,0,n) flow::add(n+m,i,x);
		rep(i,0,m) flow::add(i+n,n+m+1,x);
		rep(i,0,c) {
			id[i]=flow::tot+1;
			flow::add(E[i].fi,E[i].se+n,1);
		}
		int w=flow::sap();
		if (w<k*x) return false;
		rep(i,0,m) flow::add(i+n,n+m+1,inf);
		int w2=flow::sap();
		if (w+w2<n*x) return false;
		return true;
	};
	while (l+1<r) {
		int md=(l+r)>>1;
		if (check(md)) l=md; else r=md;
	}
	int x=l;
	printf("%d\n",x);
	if (x==0) {
		return 0;
	}
	check(x);
	rep(i,0,c) if (flow::f[id[i]]==0) {
		used[E[i].se].pb(i);
	}
	vector<VI> eg(n+m);
	int tl=n,tr=m,dg=0;
	rep(i,0,m) if (SZ(used[i])<x) {
		//printf("? %d\n",i);
		for (auto y:used[i]) {
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,0,x-SZ(used[i])) {
			if (SZ(eg[tl])==x) tl++;
			eg[tl].pb(i);
		}
	} else {
		rep(j,0,x) {
			int y=used[i][j];
			eg[E[y].fi].pb(i);
			wt[E[y].fi][i].pb(y);
		}
		rep(j,x,SZ(used[i])) {
			if (dg==x) tr++,dg=0;
			int z=tr;
			int y=used[i][j];
			eg[E[y].fi].pb(z);
			wt[E[y].fi][z].pb(y);
			dg++;
		}
	}
	//printf("? %d %d\n",tl,tr);
	if (SZ(eg[tl])>0) {
		while (SZ(eg[tl])<x) {
			eg[tl].pb(tr),dg++;
		}
	}
	if (dg==x) tr++,dg=0;
	if (SZ(eg[tl])==x) ++tl;
	//printf("? %d %d %d\n",tl,tr,dg);
	assert(tl==tr&&dg==0);
	eg.resize(tl);
	coloring(eg);
	rep(i,0,x) {
		rep(u,0,n) {
			int v=res[i][u];
			assert(!wt[u][v].empty());
			printf("%d ",wt[u][v].back()+1); wt[u][v].pop_back();
		}
		puts("");
	}
}*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5984kb

input:

output:

2
10 8 3 
9 6 1

result:

ok

Test #2:

score: 0

Accepted

time: 1ms

memory: 5868kb

input:

output:

result:

ok

Test #3:

score: 0

Accepted

time: 1ms

memory: 4120kb

input:

output:

2
16 20 12 6 11 
9 13 4 18 17

result:

ok

Test #4:

score: 0

Accepted

time: 1ms

memory: 5924kb

input:

10 10 100 9
5 4
4 8
4 5
7 10
5 3
6 6
5 7
1 8
6 8
5 3
1 2
3 6
9 5
6 3
6 9
10 1
7 10
8 8
2 7
9 3
8 7
2 2
5 7
3 9
4 1
1 2
7 2
7 2
4 3
10 4
4 2
5 3
3 4
5 4
10 6
8 5
9 5
3 3
3 8
1 7
3 8
4 7
8 4
4 7
4 5
6 7
6 7
6 9
8 1
4 5
10 10
4 10
4 3
8 9
7 6
8 2
8 8
4 4
9 10
1 7
9 1
10 4
8 8
9 2
3 6
3 8
8 5
10 4
5 6
5...

output:

5
60 98 90 88 70 71 28 63 80 79 
81 100 66 44 34 94 99 85 92 51 
91 22 74 82 23 48 55 57 87 68 
77 19 41 25 69 15 17 89 84 62 
8 96 65 52 32 47 27 67 75 16

result:

ok

Test #5:

score: 0

Accepted

time: 5ms

memory: 5272kb

input:

10 100 1000 8
10 95
4 22
8 55
7 11
7 62
2 39
5 17
7 33
7 69
2 49
9 13
1 43
7 87
3 58
8 38
3 25
6 19
7 10
1 94
5 59
3 81
5 55
7 13
8 79
7 73
1 11
7 70
4 73
2 47
9 26
7 48
10 62
4 16
3 55
5 12
9 75
2 27
10 77
1 43
1 72
2 86
4 14
1 43
7 49
2 29
10 54
6 26
10 86
6 38
9 25
10 27
7 44
9 60
10 22
2 39
4 64...

output:

84
277 568 841 275 797 846 241 767 164 497 
669 935 607 688 889 621 825 890 311 403 
813 808 762 555 776 892 960 880 413 629 
950 398 476 285 928 706 971 907 339 837 
485 783 869 624 819 985 949 829 773 787 
866 891 865 644 902 638 836 707 991 999 
698 821 537 690 792 957 896 901 931 934 
861 619 97...

result:

ok

Test #6:

score: 0

Accepted

time: 1ms

memory: 6216kb

input:

output:

1
47 43 44 32 42 50 49 33 20 45 7 29 9 19 22 16 40 41 24 39

result:

ok

Test #7:

score: 0

Accepted

time: 1ms

memory: 4300kb

input:

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

output:

15
281 424 384 450 57 355 434 234 367 301 461 385 464 35 353 493 324 225 427 428 
347 133 418 267 489 405 423 186 283 147 271 468 462 166 287 229 217 406 394 476 
420 444 395 392 341 376 378 389 397 286 245 311 344 264 455 454 415 490 414 467 
176 83 481 48 314 153 480 400 442 381 458 441 495 483 43...

result:

ok

Test #8:

score: 0

Accepted

time: 2ms

memory: 6056kb

input:

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

output:

32
973 989 896 726 755 642 936 909 756 891 977 917 108 928 680 922 707 624 976 672 
552 494 725 983 767 874 877 893 585 881 884 813 762 252 786 961 988 839 1000 418 
952 543 947 951 727 782 811 855 573 795 959 886 386 875 863 787 827 860 778 887 
883 320 754 567 527 796 900 945 674 889 507 751 690 4...

result:

ok

Test #9:

score: 0

Accepted

time: 6ms

memory: 7092kb

input:

100 100 5000 100
40 31
92 15
79 46
81 57
32 96
100 54
93 54
12 89
50 33
89 32
50 90
45 3
26 2
27 9
49 22
44 28
16 9
51 69
9 18
89 93
89 13
46 99
39 13
10 68
54 58
48 32
5 68
25 100
65 40
94 74
41 31
27 49
18 54
71 73
83 35
84 23
55 51
8 13
40 24
2 15
67 80
85 87
26 11
68 58
40 73
12 50
4 88
79 87
34...

output:

36
4086 3972 328 503 3777 2887 3302 4398 1990 465 1956 4827 209 4404 2402 1474 4912 4841 2514 3179 1617 3129 3073 2187 1813 4342 4511 1375 4044 4656 4510 4191 3365 2181 4161 1076 3142 1959 1339 1953 4027 3048 2519 2160 4683 2543 4890 3790 2860 2052 4143 3816 2140 4110 2564 4204 2602 3576 3149 4059 1...

result:

ok

Test #10:

score: 0

Accepted

time: 3ms

memory: 7096kb

input:

100 100 5000 99
61 63
13 12
30 42
99 63
27 61
91 39
73 89
61 2
78 39
67 45
83 41
49 1
99 46
69 3
48 39
88 84
35 25
28 40
53 72
18 71
42 53
69 21
12 28
93 78
86 100
90 79
42 35
63 97
33 42
6 4
66 47
75 33
54 45
72 42
99 69
47 20
73 56
67 61
33 28
95 67
54 10
35 3
96 87
48 65
77 38
35 18
3 67
45 86
80...

output:

28
3707 2674 3638 3232 4035 1397 268 349 4448 3472 2932 3427 3820 2258 4598 4645 1246 4633 4643 2968 4610 2642 1673 4625 4591 3141 3640 2496 4155 2436 2917 3345 1971 2643 941 1798 4216 2933 3663 3101 4255 1993 4366 4068 3816 2767 2765 4942 3581 2031 2663 3777 2186 4258 2861 4463 4958 3012 3657 2883 ...

result:

ok

Test #11:

score: 0

Accepted

time: 7ms

memory: 5204kb

input:

100 100 5000 90
6 35
87 21
10 67
82 86
31 55
47 81
61 66
4 66
38 31
90 22
19 94
65 59
66 42
44 34
54 16
97 20
43 78
41 18
18 16
100 6
68 21
53 9
44 46
97 53
68 49
7 57
43 85
24 53
27 14
63 42
37 93
21 47
60 13
33 7
32 22
29 96
34 51
64 98
10 76
81 2
28 97
67 94
14 100
43 94
97 51
47 82
31 1
32 78
8 ...

output:

38
1182 3692 3292 2755 4990 3437 3993 614 4696 3517 3965 1756 2298 4176 2411 1679 2396 4478 202 4844 1824 2305 1289 4609 3844 4737 2351 1923 3316 2753 2279 2066 4638 1093 3104 388 2993 2431 1115 2552 2861 3402 865 2929 2035 4446 151 2864 4462 4629 3209 2355 4615 2585 4067 3862 2580 1540 4982 2879 47...

result:

ok

Test #12:

score: 0

Accepted

time: 6ms

memory: 6796kb

input:

100 100 5000 50
44 20
77 81
42 12
83 24
60 27
73 2
31 62
68 29
56 63
93 86
47 25
70 71
5 79
34 35
96 63
100 88
65 86
62 72
40 32
39 53
31 49
14 5
21 52
17 63
85 10
13 22
69 62
35 33
54 29
68 14
74 80
67 11
63 65
9 88
36 77
98 20
65 6
18 21
93 68
63 29
32 39
86 86
38 30
51 3
57 41
93 91
76 46
83 38
2...

output:

36
2530 3797 2793 4579 4241 4730 2060 3865 3069 4257 1508 2736 2862 188 2581 2861 2151 4692 508 4901 1513 419 3437 3919 3768 2009 3505 3872 4288 3161 3196 4990 4322 3493 4265 4467 3363 4767 3151 2396 546 3512 2284 4452 4009 998 4250 3192 4030 3073 4028 3647 1431 4344 261 3145 1999 4064 2268 3400 802...

result:

ok

Test #13:

score: 0

Accepted

time: 278ms

memory: 54544kb

input:

1 100 5000 1
1 60
1 46
1 43
1 42
1 53
1 69
1 15
1 42
1 6
1 18
1 50
1 97
1 8
1 68
1 76
1 79
1 27
1 72
1 4
1 64
1 96
1 26
1 14
1 51
1 10
1 68
1 20
1 52
1 41
1 76
1 18
1 50
1 57
1 8
1 35
1 9
1 84
1 62
1 93
1 40
1 63
1 91
1 11
1 38
1 96
1 79
1 43
1 43
1 83
1 78
1 60
1 25
1 55
1 43
1 10
1 45
1 97
1 11
1 ...

output:

result:

ok

Test #14:

score: 0

Accepted

time: 6ms

memory: 5208kb

input:

100 1 5000 1
78 1
44 1
1 1
7 1
1 1
47 1
52 1
49 1
95 1
87 1
11 1
16 1
90 1
9 1
15 1
16 1
56 1
79 1
94 1
30 1
57 1
56 1
45 1
89 1
16 1
22 1
20 1
75 1
47 1
32 1
51 1
80 1
83 1
34 1
21 1
96 1
17 1
88 1
99 1
30 1
41 1
14 1
82 1
25 1
58 1
78 1
72 1
78 1
81 1
37 1
86 1
28 1
99 1
8 1
48 1
64 1
51 1
85 1
63...

output:

36
2786 1780 2870 1921 4071 4226 3478 4715 4375 2902 2989 4301 1937 3294 3674 887 2396 2627 3518 4675 1524 4450 2053 4592 3722 1180 3072 3329 3807 1605 1244 4161 2469 4258 2677 4184 2980 1877 3237 3837 3348 2254 4964 4790 4108 2752 1090 3906 4391 1797 4838 2698 3869 4974 3964 4474 3650 1678 3999 200...

result:

ok

Test #15:

score: 0

Accepted

time: 75ms

memory: 16668kb

input:

2 50 5000 2
1 10
2 19
1 22
1 19
1 8
2 21
1 2
2 14
1 38
2 36
1 23
2 41
2 40
1 44
2 24
1 50
2 30
2 3
2 22
1 26
1 9
2 13
1 16
2 48
1 17
2 18
1 5
1 12
1 1
2 26
1 27
1 50
2 27
1 12
1 35
2 23
1 4
1 26
1 36
2 31
2 32
1 21
2 49
1 37
2 46
2 42
1 22
1 13
2 35
2 49
2 16
1 27
2 18
2 37
2 42
2 34
1 15
2 2
1 21
1...

output:

2466
4949 4963 
4990 4754 
4925 4986 
4967 4964 
4912 4970 
4940 4951 
4788 4937 
4930 4898 
4932 4957 
4989 4959 
4987 4836 
4969 4982 
4686 4961 
4928 4793 
4874 4952 
4834 4810 
4977 4935 
4574 4995 
4825 4955 
4948 4901 
4985 4975 
4640 4752 
4996 4879 
4907 4936 
4931 4786 
4897 4971 
4968 4991...

result:

ok

Test #16:

score: 0

Accepted

time: 7ms

memory: 5168kb

input:

100 100 5000 1
28 34
13 11
4 95
1 40
45 67
91 36
6 89
36 33
1 32
27 76
55 84
3 78
61 99
67 85
45 8
5 61
50 50
93 39
26 77
54 60
73 67
33 71
66 15
96 32
45 73
100 68
36 100
8 68
63 10
74 4
94 60
54 75
85 60
78 19
33 14
59 90
79 100
86 60
2 93
64 19
52 61
80 36
31 45
12 73
7 83
98 83
82 16
18 31
68 20...

output:

37
2718 2554 3412 2443 604 4982 4930 2938 4297 3392 2542 4072 192 3750 4277 4368 4431 1907 853 2269 3388 4300 3630 2995 3229 4127 4308 2187 2148 3624 3972 1565 2357 1438 1004 3225 622 2506 4280 2593 3402 4114 3463 3200 817 1615 4006 3777 4776 3882 4958 4232 1381 2491 4102 3585 3653 1200 4867 2348 31...

result:

ok

Test #17:

score: 0

Accepted

time: 0ms

memory: 5312kb

input:

100 100 5000 11
32 86
20 28
34 65
50 82
14 73
37 70
93 64
69 27
20 78
75 22
23 9
33 4
31 87
98 84
21 63
38 24
69 68
18 31
94 69
45 42
44 86
64 33
21 7
50 60
32 94
27 88
94 30
46 58
62 27
19 31
57 11
77 68
45 93
67 87
75 71
94 57
31 37
2 59
53 15
18 46
16 98
32 50
68 52
53 87
81 7
23 89
6 23
98 3
17 ...

output:

32
1944 3693 3176 4951 4798 2836 1912 4841 1321 942 3157 842 4829 3439 3471 4635 3336 3684 2278 4835 4767 3897 1478 4499 4063 2592 4744 4814 2445 4433 2608 1079 1931 3735 1924 3031 2796 1983 2635 1572 3359 3800 4455 2355 2120 4511 2267 4615 1402 4014 3164 1598 4670 4474 2826 4602 4875 3898 3941 2489...

result:

ok

Test #18:

score: 0

Accepted

time: 2ms

memory: 4080kb

input:

10 10 1000 10
7 10
7 4
2 6
6 2
2 5
4 6
9 2
9 5
4 2
8 5
3 9
3 3
6 5
1 5
6 8
5 8
5 9
4 3
7 5
7 7
5 3
4 2
4 9
9 3
3 3
10 9
6 10
8 4
10 3
8 10
8 7
2 1
6 8
10 3
3 4
2 5
6 2
3 1
1 3
3 5
1 6
2 4
2 2
3 2
1 2
3 2
1 7
1 5
4 3
5 9
9 6
5 2
3 2
8 2
8 6
4 1
6 10
5 9
3 3
8 7
7 9
1 6
2 10
5 3
9 3
6 5
3 3
7 10
8 2
7...

output:

81
992 980 547 953 969 971 890 956 794 948 
981 864 920 937 827 729 802 830 746 922 
929 984 910 934 822 955 972 941 898 977 
863 940 960 905 847 944 862 846 880 951 
819 748 758 949 939 970 931 938 883 889 
962 932 912 861 961 959 875 853 924 950 
946 952 332 842 923 804 907 891 869 831 
908 945 98...

result:

ok

Test #19:

score: 0

Accepted

time: 0ms

memory: 5232kb

input:

100 50 5000 45
85 20
87 4
95 42
56 45
56 15
37 5
72 4
62 39
58 38
38 14
10 22
15 29
33 39
55 41
23 40
66 25
24 18
74 7
83 17
77 46
77 15
32 14
14 6
2 50
6 40
57 42
100 14
3 44
27 44
72 7
35 48
86 15
88 13
45 9
37 34
74 29
75 42
80 27
14 29
85 4
93 39
68 49
59 22
17 49
19 28
99 36
73 20
54 21
74 22
4...

output:

35
4887 4035 1328 2696 3618 2937 1640 4911 2957 1728 2477 2865 2216 3917 3571 1578 1897 4478 2230 2099 1348 2438 4879 3062 1972 3963 2789 4099 4638 2122 3588 4806 3841 4792 3328 4343 2552 775 3439 4576 4923 3520 3161 4445 4993 4496 3738 3858 3247 4066 3646 2985 2131 1893 4770 3685 1569 2428 1278 297...

result:

ok

Test #20:

score: 0

Accepted

time: 9ms

memory: 5588kb

input:

50 100 5000 38
13 100
25 90
37 14
43 47
22 63
29 90
46 97
46 5
37 8
31 64
13 8
34 10
2 96
50 56
8 74
25 43
15 50
38 9
38 52
44 55
11 83
6 64
8 58
31 23
27 68
48 46
37 35
26 84
30 18
21 80
8 66
9 69
36 89
12 30
23 53
8 15
48 71
31 78
4 35
25 31
20 75
12 73
21 17
21 63
12 7
32 87
9 84
6 87
40 24
40 90...

output:

85
3531 4278 2065 3759 2042 3641 4746 4370 3680 3966 2669 3458 1600 3291 2980 3750 3926 4646 2702 4321 1322 3279 4645 4804 2736 4807 567 4457 4916 4622 4069 2229 1468 4793 2917 4261 4736 1812 2704 1395 4869 1579 1326 1059 4005 3167 2018 3858 4532 3274 
3377 1413 1007 3053 4640 2481 1899 1834 3010 26...

result:

ok

Test #21:

score: 0

Accepted

time: 9ms

memory: 7464kb

input:

50 100 5000 38
13 7
39 44
19 86
37 39
19 69
10 40
50 24
17 99
18 53
2 81
12 21
21 45
17 7
11 76
21 71
28 3
35 10
38 55
19 84
28 78
17 41
18 61
9 15
40 64
36 47
4 92
11 70
40 30
23 84
41 28
20 50
4 14
30 76
13 56
28 39
30 50
18 32
17 59
10 1
25 75
46 27
32 65
21 11
47 86
6 27
2 47
41 97
47 89
36 94
2...

output:

85
3134 1318 3885 4524 1722 4398 4494 2330 2975 3216 1260 3794 4960 2833 1642 1813 2169 4684 3505 4660 1929 4220 1946 3403 2947 2999 2679 2464 4753 3838 4103 4181 4425 2729 2110 3221 2575 3341 3444 471 3425 4693 1592 3843 4133 4529 4708 4435 4154 3400 
2216 3878 2599 4971 1217 4899 705 4593 1458 457...

result:

ok

Test #22:

score: 0

Accepted

time: 7ms

memory: 7052kb

input:

100 100 5000 99
54 45
51 32
60 55
12 73
80 37
9 10
1 68
52 54
79 58
81 36
25 13
41 57
38 16
45 40
76 60
31 71
56 95
54 96
32 59
87 70
98 64
75 36
42 40
15 46
59 13
11 26
100 77
73 94
40 87
73 46
47 5
42 54
92 41
13 75
82 70
93 7
11 89
35 94
99 65
19 46
1 43
60 80
10 12
83 66
33 25
80 63
20 31
10 80
...

output:

41
4914 3680 4309 2279 4416 615 2815 2371 700 2796 2606 4102 1313 3612 1836 4334 1777 3883 4576 4255 2433 4133 1434 1849 4428 3692 4458 2376 4057 1753 2012 2602 4785 2535 3657 2141 3308 4776 600 1994 4815 4210 3987 3373 2877 3395 3141 3386 4359 1772 2352 2645 3546 1447 1022 3227 4880 4906 4342 4317 ...

result:

ok

Test #23:

score: 0

Accepted

time: 7ms

memory: 7092kb

input:

100 100 5000 100
6 10
52 38
9 2
98 87
88 37
26 83
68 48
54 1
30 43
95 42
2 21
97 91
11 52
91 17
24 70
56 22
58 87
50 34
3 40
8 96
30 26
88 6
41 56
67 51
34 23
71 11
28 87
29 41
12 18
26 80
54 77
58 38
12 21
83 66
70 7
79 64
33 24
92 50
21 43
90 52
35 49
97 82
78 89
30 16
54 16
19 5
21 54
17 13
85 80...

output:

50
2077 4602 1938 4805 2282 4638 3192 3376 4017 91 2599 4997 3682 1787 643 4180 3770 4708 4191 4048 2461 4554 4251 4814 2178 4916 4930 3253 2986 1681 1317 1360 4418 946 4967 4012 4230 1552 498 2995 2548 3048 895 2197 4353 3494 2262 2824 2367 3063 1112 1075 1803 4473 2828 3171 1380 2222 4339 993 3885...

result:

ok

Test #24:

score: 0

Accepted

time: 7ms

memory: 6888kb

input:

70 70 4900 70
56 25
68 11
2 37
53 36
36 10
19 63
69 21
60 18
2 34
59 30
54 34
2 42
26 52
35 17
5 4
53 36
2 64
20 60
45 22
55 66
63 54
19 33
35 10
43 38
12 30
7 69
7 47
54 25
44 56
50 20
49 51
20 67
14 59
26 37
31 3
22 7
20 63
52 60
35 31
17 37
47 17
26 38
35 8
58 70
28 62
35 32
3 3
54 46
57 24
42 52...

output:

70
4404 3 4171 739 4890 847 4199 4575 4533 2478 4272 4844 2541 4497 4419 3522 563 1237 3188 4563 3518 662 3012 4492 2477 2432 3023 4064 4165 3450 4387 2961 3124 4786 3176 1615 4899 3890 2625 2934 3889 1834 4063 1164 2197 4187 3447 2408 195 3110 2940 4555 3799 4782 4041 4329 2426 2761 726 4346 3916 3...

result:

ok

Test #25:

score: 0

Accepted

time: 8ms

memory: 5360kb

input:

100 100 5000 91
68 22
30 32
31 49
71 39
67 20
55 48
77 31
100 71
22 39
10 37
80 70
68 63
30 68
29 7
11 19
47 5
19 16
37 10
29 17
17 52
17 98
90 42
62 54
55 50
57 100
50 23
40 41
51 89
34 42
71 97
94 79
86 52
67 23
48 47
72 51
70 31
39 90
74 50
82 52
21 2
38 68
81 81
79 1
92 79
34 23
6 84
40 25
39 39...

output:

50
3242 3506 3574 2343 4813 2273 2299 3990 1201 2098 4961 2697 2266 2512 2248 2400 4449 3372 2696 3937 2151 2887 1086 4767 4033 3760 2482 300 609 3181 4180 4230 4112 45 3683 3609 4937 4926 3403 3246 4575 2213 1009 3034 313 2066 3814 3245 2002 2776 1001 649 1155 3623 472 4992 3679 3432 2734 3121 949 ...

result:

ok

Test #26:

score: 0

Accepted

time: 7ms

memory: 7224kb

input:

100 100 5000 92
32 84
38 56
14 83
50 30
90 33
81 7
52 8
56 45
5 90
9 15
88 16
37 29
17 82
68 55
30 31
77 17
44 97
11 47
81 78
80 2
10 88
89 91
40 59
54 4
53 70
91 59
20 68
24 54
7 90
18 30
100 65
27 58
83 26
81 41
74 52
41 43
60 68
61 97
15 13
37 3
37 12
34 70
91 45
26 44
97 66
81 58
94 51
23 18
93 ...

output:

50
4835 1199 2728 3760 3956 739 3153 3882 4980 4957 2720 884 2185 4752 3953 4653 1308 3827 1420 2152 1747 847 1442 4105 3394 2678 4907 3897 2140 2236 4829 2668 2224 4538 954 4934 2544 4584 1251 1828 2290 4386 3173 17 1958 1207 3629 3287 118 364 4736 1724 3246 824 3658 2315 4469 2061 1266 4978 3868 3...

result:

ok

Test #27:

score: 0

Accepted

time: 0ms

memory: 5448kb

input:

100 100 5000 93
42 13
62 29
95 84
79 95
47 72
71 10
1 21
73 69
47 92
51 83
82 48
63 19
37 11
76 40
7 73
71 51
56 17
82 68
80 75
92 87
96 41
19 77
42 81
13 92
83 88
14 20
88 59
11 77
93 19
31 35
64 32
87 50
15 94
53 45
24 50
46 2
37 26
81 62
19 63
72 56
18 64
61 61
66 88
82 72
61 90
21 100
61 68
57 1...

output:

50
1546 3544 669 483 4716 2596 3143 2250 4684 2823 4940 2327 4222 1596 1419 840 498 3139 2506 1765 1468 890 2408 2282 3641 612 2180 4615 2325 4174 2762 4618 4530 3523 272 4623 3707 3674 4151 115 4233 3056 330 3983 2264 4895 2521 4950 4625 4242 3623 2323 2042 834 3400 4542 783 1120 4554 2023 1984 130...

result:

ok

Test #28:

score: 0

Accepted

time: 7ms

memory: 6888kb

input:

100 100 5000 94
58 53
98 44
20 38
42 97
99 30
66 99
41 88
9 7
39 85
71 68
4 18
34 92
20 62
16 90
50 62
97 89
44 49
53 86
36 91
65 32
65 2
18 10
20 22
36 87
75 70
23 96
22 57
63 87
99 19
51 15
72 58
6 100
76 92
14 73
82 46
83 72
73 4
82 75
80 9
43 18
94 52
22 34
88 4
55 79
53 63
96 86
37 55
69 21
6 2...

output:

50
3695 4084 2625 3346 3732 3834 4438 1771 2087 3255 4475 3771 1243 1829 610 3360 641 4631 3682 4731 4664 693 2926 4558 286 4203 4455 1437 2302 4392 4982 3114 3544 764 3375 3945 1521 374 3812 2114 1072 4647 2298 3056 3752 2379 2033 3477 4543 4735 3513 4643 634 4044 2578 3084 4590 2189 2425 3369 2085...

result:

ok

Test #29:

score: 0

Accepted

time: 0ms

memory: 5364kb

input:

100 100 5000 95
39 29
44 51
75 34
7 45
21 95
1 89
34 98
34 69
26 69
98 47
74 38
36 100
22 28
53 3
50 10
51 83
12 19
75 29
50 80
65 44
17 22
79 74
83 7
71 48
90 41
71 70
57 54
25 8
34 41
17 3
50 99
59 84
65 86
49 21
28 61
43 79
89 84
62 54
69 74
48 92
88 47
42 13
1 78
37 40
20 39
53 17
76 6
62 83
21 ...

output:

49
3819 2276 4001 1064 4507 3305 2554 3245 4575 4585 4770 2153 4157 268 3366 428 4127 2553 1693 4854 1318 2389 3646 166 2936 1617 811 747 153 982 2814 3393 2176 1441 3111 2163 858 2024 1425 4425 4582 3421 1264 165 1103 4730 2350 3932 4583 4899 3053 1155 1667 3210 4218 2079 584 4159 4212 3627 2645 71...

result:

ok

Test #30:

score: 0

Accepted

time: 0ms

memory: 5564kb

input:

100 100 5000 96
35 80
66 94
41 34
12 23
92 72
31 15
95 12
43 75
3 32
14 64
9 66
77 8
17 72
61 23
20 39
12 100
36 15
77 15
35 68
1 86
39 97
85 79
35 42
45 95
96 60
44 96
16 87
60 61
75 93
100 60
93 23
27 7
77 14
2 76
52 73
70 22
17 35
29 79
68 99
79 86
84 90
49 24
25 78
29 47
10 53
36 88
57 91
25 97
...

output:

48
120 2243 3908 888 2237 3985 1018 586 4425 2072 2684 2021 1211 3471 4338 2533 3319 2976 3723 4872 2707 1717 4956 4319 2722 4566 1345 2682 2370 1663 3357 4686 3117 2776 4272 1925 4060 155 1317 4102 3683 3392 2390 3131 2844 1333 3405 1743 3182 3491 4288 2117 2153 2696 2872 1761 4776 2336 4048 3187 3...

result:

ok

Test #31:

score: 0

Accepted

time: 7ms

memory: 5444kb

input:

100 100 5000 97
92 21
82 19
52 85
59 50
42 17
36 29
38 16
93 12
51 92
38 81
53 21
60 7
93 82
70 24
95 2
82 95
94 73
74 11
73 9
23 42
95 24
37 42
67 64
76 98
78 25
95 80
61 100
18 20
65 73
37 93
49 44
63 61
20 95
97 77
15 77
16 90
74 67
49 10
96 61
77 45
87 95
40 11
95 17
3 46
76 13
72 26
56 59
10 69...

output:

47
2950 3836 3002 3611 3722 4526 2135 4005 315 4983 4686 1921 938 3516 2591 2607 3671 1785 1872 4875 4321 2872 3723 798 4332 3199 4610 3147 605 3491 1168 1389 3640 4067 3574 1324 4029 10 1562 4254 3819 4966 1325 2494 4142 2789 2366 4314 1096 2462 2267 3427 3165 3992 3755 3795 1060 4274 3621 2282 165...

result:

ok

Test #32:

score: 0

Accepted

time: 6ms

memory: 7236kb

input:

100 100 5000 98
14 78
71 9
52 11
3 95
61 24
39 37
3 96
43 96
26 54
1 53
23 17
19 95
52 41
89 93
23 31
74 25
13 19
67 28
58 17
20 8
36 33
97 99
80 25
3 27
33 50
87 62
80 13
67 33
51 73
28 84
60 89
42 79
18 45
4 64
45 26
72 73
77 97
94 80
53 93
66 55
52 43
49 94
57 47
69 29
58 61
23 76
22 4
4 63
3 41
...

output:

44
4303 4011 4071 2545 3296 2493 2474 3577 4884 100 3180 2197 1714 1480 555 842 1150 4611 2729 4755 387 1034 2046 3870 2800 2461 4862 1543 4135 3980 4089 2482 2366 1105 4574 1665 4882 4196 3329 3967 4571 763 3351 4411 1834 904 4451 1093 3154 2734 3483 4259 4589 2539 1935 1550 4365 4523 4467 4316 372...

result:

ok

Test #33:

score: 0

Accepted

time: 6ms

memory: 5516kb

input:

100 100 5000 99
42 95
99 49
41 34
49 49
8 33
24 41
42 66
21 83
36 18
39 79
49 52
29 94
33 38
40 10
57 82
85 39
94 40
70 12
48 91
10 39
27 86
5 87
45 91
100 25
49 37
75 45
81 47
57 46
31 24
16 96
38 92
6 19
6 36
23 33
53 67
4 82
38 20
63 94
98 75
19 84
93 45
37 63
81 88
41 48
66 92
53 69
66 43
87 90
...

output:

41
3028 3589 3752 2594 3918 3971 1722 2049 1872 4030 1419 3358 3174 2808 2844 4851 4616 4308 2298 4988 2432 492 2553 4867 2027 3021 4165 3723 3785 1836 4828 3810 1372 836 3848 4032 1295 2525 2575 1985 170 3214 4468 1208 1054 2730 2996 3138 4889 4553 3112 1628 1712 1131 2883 2315 1656 4849 2401 3377 ...

result:

ok

Test #34:

score: 0

Accepted

time: 6ms

memory: 5260kb

input:

100 100 5000 100
67 51
40 33
69 34
47 41
66 57
40 1
4 84
7 50
67 38
4 75
59 36
86 70
8 66
66 3
15 93
9 3
42 5
64 61
94 84
33 39
95 48
28 87
50 71
32 63
18 61
20 91
78 75
7 74
88 90
49 31
62 32
5 37
64 52
99 43
30 3
9 96
85 10
36 54
2 42
54 82
73 98
67 58
19 33
68 34
84 65
45 88
44 78
17 86
77 81
55 ...

output:

35
3853 2823 4717 4447 4294 4491 1778 1328 4896 1785 4642 3572 3515 1441 1362 3943 4334 3919 1960 3128 2445 4035 601 1300 1195 2644 3514 2440 4255 4636 4994 1906 4404 3888 4257 1323 4938 4778 3581 3771 4001 4427 4456 2046 4815 1790 3912 2638 4340 3712 2278 4012 3965 3872 2246 2264 2912 4218 2861 373...

result:

ok

Test #35:

score: 0

Accepted

time: 7ms

memory: 7104kb

input:

100 100 5000 10
45 60
44 26
42 7
29 63
91 9
61 49
99 73
89 27
46 5
28 6
35 89
93 40
54 17
11 11
28 87
1 23
39 5
61 45
33 77
86 100
86 82
44 40
24 52
30 38
81 58
61 39
75 13
36 44
87 49
7 25
56 4
95 48
35 39
37 31
69 51
19 23
78 19
81 62
15 34
84 41
45 71
48 26
91 63
69 52
32 37
73 69
4 12
59 13
99 6...

output:

49
4385 2793 4431 1054 2977 4539 3946 3864 3212 3147 4530 4411 4263 117 635 3710 2899 4572 3095 802 2964 3491 3515 2797 2723 2222 1523 4161 4233 1646 3743 2046 191 4828 3324 4268 242 312 3183 3010 4710 1824 2607 4862 4636 3931 1468 2819 968 4355 400 1552 4290 4196 474 4648 3657 3423 4221 4958 26 478...

result:

ok

Test #36:

score: 0

Accepted

time: 7ms

memory: 5612kb

input:

100 100 5000 20
6 42
51 70
43 66
61 1
64 22
79 35
7 26
72 65
98 57
55 3
3 66
43 90
39 91
57 60
27 98
32 84
20 37
36 90
13 18
70 72
66 42
82 60
95 9
2 81
55 15
94 36
32 72
56 25
13 27
74 96
25 15
4 72
35 72
97 7
60 84
1 4
62 88
23 46
29 41
55 12
23 63
82 11
89 15
30 6
95 79
71 74
4 77
33 61
18 45
45 ...

output:

49
4185 4360 4753 3776 1065 1990 1452 550 4997 2956 3517 4305 3919 3981 2554 4556 3899 884 3895 3978 2551 3825 87 4483 4558 1735 2369 1496 3162 1921 4210 2552 4759 668 2603 1184 4116 2143 2222 4567 3766 4645 3465 4290 1045 2547 343 3313 227 4292 4166 4312 896 4827 4511 1349 3848 3372 2276 1818 1495 ...

result:

ok

Test #37:

score: 0

Accepted

time: 7ms

memory: 7188kb

input:

100 100 5000 30
3 78
94 86
57 55
40 92
100 95
16 30
94 69
80 28
20 77
14 80
34 63
92 8
82 17
21 94
64 71
3 59
84 26
67 91
23 97
81 57
61 66
89 44
99 83
65 27
7 12
50 62
85 28
41 4
22 6
76 57
39 48
90 16
49 5
43 53
84 74
67 10
14 35
76 33
61 58
74 46
55 32
28 15
23 14
9 63
43 2
86 25
92 91
17 36
82 3...

output:

49
4147 744 3667 72 4332 3068 400 3849 3472 3818 4876 3909 1526 37 2264 4483 623 833 4486 4400 1030 3385 917 4441 1233 4743 1728 4103 1153 1111 2819 2245 1176 3173 4137 3913 4473 980 4567 4211 2642 4605 4845 3001 2975 926 3671 3758 4671 2777 2523 4416 4155 509 3334 3972 2635 4450 1815 4552 3598 1991...

result:

ok

Test #38:

score: 0

Accepted

time: 8ms

memory: 7412kb

input:

100 100 5000 40
37 40
45 19
5 38
35 66
86 39
32 38
60 66
80 83
33 87
69 100
3 98
61 18
64 69
87 5
40 22
47 36
56 16
5 67
40 63
53 35
33 58
16 23
78 82
11 70
7 57
40 50
96 27
85 78
68 53
85 98
13 58
18 41
82 17
29 99
82 36
94 68
68 50
32 4
18 96
42 96
11 38
92 30
76 75
45 99
84 54
29 45
79 45
99 79
7...

output:

49
4658 886 2440 3055 2335 3272 4062 2958 708 82 2542 2432 4652 616 1894 3268 2664 367 1754 3628 3371 897 4554 3846 2175 4199 3767 3031 3557 4172 1528 1382 9 3160 2620 3351 4179 3807 3015 260 259 1446 1818 2194 3330 1547 3854 3343 3498 2014 3247 3616 1847 2268 1757 17 2185 512 4836 2356 1516 1508 46...

result:

ok

Test #39:

score: 0

Accepted

time: 7ms

memory: 7176kb

input:

100 100 5000 50
3 74
92 15
36 55
4 9
73 88
90 7
12 51
43 8
14 95
34 26
38 79
27 17
55 82
48 83
47 42
20 14
22 31
57 11
3 56
7 27
47 19
74 23
56 29
59 29
96 78
8 90
6 99
66 77
96 89
78 79
85 11
51 60
66 75
84 20
99 13
81 18
15 63
80 66
95 32
50 88
48 71
66 89
62 13
96 39
47 26
33 97
98 32
22 4
58 15
...

output:

49
1937 3729 2682 3774 1868 2830 3265 3362 3052 3556 627 3815 3971 1686 912 3772 1019 1500 914 851 1998 3002 2325 326 4394 4797 3991 2516 4021 4823 4116 686 3863 2129 3207 175 3031 4752 4199 680 3200 356 1529 2647 3348 4602 2170 2055 1991 648 3291 721 2703 4011 4899 2528 1043 1073 4247 4369 2258 456...

result:

ok

Test #40:

score: 0

Accepted

time: 7ms

memory: 5652kb

input:

100 100 5000 60
44 37
13 58
82 16
1 9
88 35
13 94
33 14
89 71
23 30
76 85
47 84
47 75
36 17
59 32
5 62
100 37
72 51
42 84
98 24
43 67
51 63
45 28
92 71
83 5
97 72
72 73
33 59
19 71
51 9
4 15
23 95
24 90
86 34
83 93
4 80
100 82
75 7
89 98
76 93
16 9
55 79
94 35
69 51
3 14
82 97
78 46
3 12
60 59
97 48...

output:

49
4481 3987 3954 4699 4601 1471 4027 591 4806 2434 3254 4341 650 1157 4939 3507 4641 2131 1587 4505 4132 4307 89 2965 2349 4855 2725 245 647 2174 1966 2822 2072 1155 4233 1889 2634 527 3732 774 1988 3567 376 3957 3557 849 4407 4229 4094 3750 4046 3577 4580 4560 4948 3762 3558 2504 4865 3943 2626 59...

result:

ok

Test #41:

score: 0

Accepted

time: 7ms

memory: 7300kb

input:

100 100 5000 70
49 28
63 1
87 78
24 82
14 13
32 42
45 39
10 55
19 53
16 57
89 67
29 8
10 23
59 2
13 26
29 28
1 24
36 48
70 83
51 65
75 52
30 48
43 98
32 14
14 41
40 87
61 4
85 75
10 3
56 15
78 4
100 28
32 53
11 71
69 25
13 12
60 88
8 64
62 64
58 56
14 6
82 74
55 25
2 35
24 35
71 84
94 21
37 5
92 100...

output:

49
3869 1741 3520 1173 2537 3033 4076 3148 3481 4809 80 4602 1385 4384 2043 2561 2718 3029 4768 4740 330 4158 2168 2349 3121 3914 4789 642 413 3810 4748 2145 2773 4332 1310 915 4745 606 4565 4919 303 4754 1800 2155 3420 274 3410 3349 906 4404 1945 4633 2596 3072 542 2997 2967 3146 3234 1809 4173 237...

result:

ok

Test #42:

score: 0

Accepted

time: 7ms

memory: 7376kb

input:

100 100 5000 80
19 4
18 66
23 25
72 37
20 94
28 40
26 79
5 95
27 78
50 76
82 21
16 20
45 78
27 91
39 79
89 56
27 46
59 14
69 27
17 84
17 37
26 38
59 93
38 20
96 96
38 70
77 86
29 40
39 50
57 54
46 35
94 42
92 62
82 89
54 76
17 94
14 6
93 88
99 59
31 38
73 44
73 52
1 38
68 66
7 7
18 81
30 45
18 4
52 ...

output:

49
228 2565 3701 3435 4089 966 1106 4579 4978 4503 2420 4873 1416 4496 1392 2275 4634 2337 2371 4171 4217 3606 2912 3450 4489 4042 4341 1199 3580 2969 4227 2658 774 4434 2266 4606 2010 3315 3577 535 3490 204 3496 1448 1890 1372 3963 4464 3359 415 3003 1232 408 2138 3353 4708 231 908 3240 303 4088 10...

result:

ok

Test #43:

score: 0

Accepted

time: 7ms

memory: 5376kb

input:

100 100 5000 90
87 64
68 39
50 72
74 64
7 87
33 57
36 14
94 98
80 58
8 83
70 38
31 7
80 93
43 58
65 89
41 20
72 32
16 52
37 95
31 55
2 64
77 94
95 1
57 75
50 19
75 61
90 9
51 91
11 77
81 11
31 7
57 11
85 3
81 71
18 64
61 66
73 68
23 98
51 7
16 25
10 87
63 14
86 38
81 62
7 63
54 14
69 96
58 55
49 89
...

output:

49
4449 3802 4774 4221 1424 3104 54 4886 3350 3144 1334 2055 226 1164 2579 3914 4188 4292 1061 4601 2967 4489 418 1476 4966 1794 4022 2212 3064 2524 1457 3338 3416 2949 343 3367 1047 3027 3038 3111 979 3319 4924 1574 4469 537 4923 2481 1580 3305 446 2258 142 1218 2201 1805 4535 1934 2953 3021 2837 8...

result:

ok

Test #44:

score: 0

Accepted

time: 4ms

memory: 5868kb

input:

100 100 5000 100
97 97
96 59
97 98
57 100
98 97
97 54
97 97
99 98
99 98
96 98
100 35
99 98
100 98
98 11
98 96
98 97
98 96
97 99
98 99
13 96
98 96
100 97
98 96
96 96
67 99
44 98
89 97
69 84
97 99
96 99
96 99
100 30
31 100
96 98
97 100
96 97
98 99
99 96
96 100
96 100
87 99
86 97
98 99
53 96
55 82
98 9...

output:

result:

ok

Test #45:

score: 0

Accepted

time: 2ms

memory: 6208kb

input:

100 100 5000 97
100 90
96 100
96 99
96 100
70 100
96 16
99 98
100 96
98 100
100 99
50 24
96 11
98 96
72 96
99 96
87 99
98 97
99 99
84 99
9 16
50 97
96 99
43 73
96 100
100 98
67 97
97 44
99 82
97 15
81 100
100 97
97 98
96 96
98 97
98 96
99 99
100 99
96 39
97 100
98 99
98 96
98 62
99 5
97 99
99 45
97 ...

output:

1
2593 2089 3922 3169 2429 3962 2239 2528 20 4862 986 2627 4881 1271 370 1638 272 751 983 732 3160 3246 1444 329 3495 2893 1799 4519 3474 752 4141 2151 687 4405 510 4397 3854 2389 3347 4937 3662 1068 23 1262 73 1617 568 85 3606 1667 427 381 1300 1652 4948 4207 3125 2329 1378 4801 1202 4268 2350 4822...

result:

ok

Test #46:

score: 0

Accepted

time: 4ms

memory: 4684kb

input:

100 100 5000 74
99 27
96 96
89 97
96 100
99 100
73 98
96 99
63 98
96 96
67 97
96 57
41 99
97 100
81 97
97 63
97 99
96 97
98 24
78 17
97 96
98 100
97 97
97 100
96 100
97 98
100 99
100 100
97 99
100 99
99 62
98 97
99 100
98 100
98 52
100 98
99 97
27 97
99 98
96 98
97 54
96 98
99 96
55 45
98 98
100 88
...

output:

3
3907 2244 3948 140 2559 3086 4658 3021 4264 1890 3888 1209 3401 4285 3834 3451 4836 965 4748 4352 274 4199 4710 2679 4876 521 4792 3421 639 1743 2250 578 3223 1118 828 4966 4516 4626 4131 461 4213 4435 4229 2121 4639 622 4894 4738 3715 3942 4843 2049 3972 4644 4561 4879 1732 1554 3965 3923 4142 44...

result:

ok

Test #47:

score: 0

Accepted

time: 4ms

memory: 4704kb

input:

100 100 5000 37
76 99
98 96
97 97
98 98
97 100
96 97
97 98
19 22
97 99
100 97
99 97
16 99
100 96
97 96
97 100
52 99
97 97
100 51
99 100
97 97
99 96
98 97
100 97
64 96
92 98
98 98
97 99
96 100
99 99
100 99
98 98
92 99
100 97
100 96
93 98
97 100
99 96
99 87
12 98
61 98
100 99
98 96
100 96
100 99
63 97...

output:

6
1064 4434 3439 3345 4606 2500 1522 375 4288 2583 3871 3097 3614 1922 2664 4807 3236 2672 8 2364 856 528 3792 4475 1427 1215 4665 2203 2395 3570 4110 3566 3796 3860 4102 3861 4712 783 3134 2484 2713 4893 4994 3071 2673 1863 3618 3542 4932 4152 1015 3935 3738 4242 472 1421 3179 3433 4318 2703 4838 2...

result:

ok

Test #48:

score: 0

Accepted

time: 4ms

memory: 4816kb

input:

100 100 5000 13
96 97
96 96
99 99
100 34
97 60
97 96
97 97
97 96
97 100
95 100
98 99
97 98
99 47
97 96
99 99
100 100
100 25
98 96
99 96
98 60
98 99
96 96
36 97
98 100
97 96
97 98
99 99
96 97
100 96
96 40
97 96
43 89
96 99
99 100
98 99
98 97
98 98
10 97
39 23
99 29
100 99
100 100
96 100
100 59
100 97...

output:

6
4201 2071 3144 2362 3735 4121 1323 3896 2933 2537 4307 3831 4864 1439 1503 3462 4502 1734 1278 2899 3540 4364 4885 4577 4516 4642 2870 2686 3990 2785 1382 2402 4294 3431 3432 2002 3568 2987 2848 2363 3702 238 2953 4237 3564 1100 4463 118 1431 1107 2303 1371 3091 4347 4427 4837 2308 1962 4941 4373 ...

result:

ok