TLE on #7 #9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[505][505],u[5005],d[5005],l[5005],r[5005];
int c[505],cnt,row[5005],col[5005],ans[505];
int s[505];
void csh(){
	for(int i=0;i<=m;i++)
	{
		u[i]=d[i]=i;
		l[i]=i-1; r[i]=i+1;
	}
	l[0]=m; r[m]=0; cnt=m;
}
void link(int x,int y){
	row[++cnt]=x; col[cnt]=y; s[y]++;
	u[cnt]=y;
	d[cnt]=d[y];
	u[d[y]]=cnt;
	d[y]=cnt;
	if(c[x]==0) c[x]=r[cnt]=l[cnt]=cnt;
	else{
		l[cnt]=c[x];
		r[cnt]=r[c[x]];
		l[r[c[x]]]=cnt;
		r[c[x]]=cnt;
	}
}
void sc(int y){
	r[l[y]]=r[y]; l[r[y]]=l[y];
	for(int i=d[y];i!=y;i=d[i])
		for(int j=r[i];j!=i;j=r[j])
			u[d[j]]=u[j],d[u[j]]=d[j],s[col[j]]--;
}
void hf(int y){
	r[l[y]]=y; l[r[y]]=y;
	for(int i=u[y];i!=y;i=u[i])
		for(int j=l[i];j!=i;j=l[j])
			u[d[j]]=j,d[u[j]]=j,s[col[j]]++;
}
bool dance(int dep){
	if(r[0]==0){
		for(int i=1;i<dep;i++) printf("%d ",ans[i]);
		return 1;
	}
	int y=r[0];
	for(int i=r[0];i;i=r[i]) if(s[i]<s[y])		y=i;
	sc(y);
	for(int i=d[y];i!=y;i=d[i]){
		ans[dep]=row[i];
		for(int j=r[i];j!=i;j=r[j]) sc(col[j]);
		if(dance(dep+1)) return 1;
		for(int j=l[i];j!=i;j=l[j]) hf(col[j]);
	}
	hf(y);
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	csh();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j])
				link(i,j);
	if(!dance(1)) printf("No Solution!") ;
	return 0;
}