#include<bits/stdc++.h>
using namespace std;
int x[200005],y[200005];
vector<int> order;
vector<vector<int>> adj,adjr;
bool vis[400005];
int str[400005];
int n,a,b,m;
int cnt=0;
void dfs1(int u){
vis[u]=1;
for(int v:adj[u]) if(!vis[v]) dfs1(v);
order.push_back(u);
}
void dfs2(int u){
str[u]=cnt;
for(int v:adjr[u]) if(str[v]==-1) dfs2(v);
}
int sccount(){
adjr.assign(n+1,{});
for(int u=1;u<=n;u++){
for(int v:adj[u]) adjr[v].push_back(u);
}
order.clear();
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
for(int i=1;i<=n;i++) str[i]=-1;
cnt=0;
for(int i=order.size()-1;i>=0;i--){
int u=order[i];
if(str[u]==-1){
dfs2(u);
cnt++;
}
}
return cnt;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("ROAI.inp","r",stdin);
// freopen("ROAI.out","w",stdout);
cin>>a>>b>>m;
for(int i=1;i<=m;i++) cin>>x[i]>>y[i];
n=a+b;
int bscc=1e9,bmask=0;
for(int mask=0;mask<(1<<m);mask++){
adj.assign(n+1,{});
for(int i=1;i<a;i++) adj[i].push_back(i+1);
for(int i=a+1;i<n;i++) adj[i].push_back(i+1);
for(int i=1;i<=m;i++){
if(mask&(1<<(i-1))) adj[a+y[i]].push_back(x[i]);
else adj[x[i]].push_back(a+y[i]);
}
int scc=sccount();
if(scc<bscc){
bmask=mask;
bscc=scc;
}
}
cout<<bscc<<'\n';
for(int i=0;i<m;i++) cout<<((bmask>>i)&1)<<" ";
cout<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |