#include<iostream>
#include<cstring>
#define maxn 50005
using namespace std;

int n,m,head[maxn],cnt;
int dfn[maxn],low[maxn],index1;
int st[maxn],top; // 模拟栈的思想 
int vis[maxn]; // 是否入栈 
int s; // 牛群个数 
int f[maxn],siz[maxn];
// f 就像分块中的 block，f[i]表示第 i 个元素属于第几个强联通分量 
// siz ：每一个强联通分量的大小 
int num[maxn]; // num[i] : i 号牛群的出度 
struct Edge{
	int v,next;
}edge[maxn];

void add(int u,int v){
	edge[++cnt]=(Edge){v,head[u]};
	head[u]=cnt;
}

inline int read(){
	int ans=0;char cc=getchar();
	while ('0'>cc||cc>'9') cc=getchar();
	while ('0'<=cc&&cc<='9'){
		ans=(ans<<3)+(ans<<1)+cc-'0';
		cc=getchar();
	}
	return ans;
}

void tarjan(int u){
	dfn[u]=low[u]=++index1; // 时间戳 
	st[++top]=u; // 入栈 
	vis[u]=1;
	int v;
	for (int i=head[u];i;i=edge[i].next){
		v=edge[i].v;
		if (dfn[v]==0){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if (vis[v]){ // 有可能是一个强联通分量 
			low[u]=min(low[u],dfn[v]);
		}
		
	}
	int t; // 对出栈的元素进行缓存 
	if (low[u]==dfn[u]){ 
		s++;
		do {
			// 进行出栈操作 
			t=st[top];
			top--;
			// t=st[top--]; 
			f[t]=s;
			siz[s]++;
			vis[t]=0;
		}while (u!=t);
	} 
}

int main(){
//	cin>>n>>m;
	n=read(),m=read();
	int u,v;
	for (int i=1;i<=m;i++){
		u=read(),v=read();
		add(u,v);
	}
	for (int i=1;i<=n;i++){
		if (dfn[i]==0){
			tarjan(i);
		}
	}
	
	for (int i=1;i<=n;i++){
		cout<<f[i]<<' ';
	}
	cout<<endl;
	
	// 统计牛群的出度 
	for (int i=1;i<=s;i++){ // 这里存疑 
		for (int j=head[i];j;j=edge[i].next){
			// 一条边的起点和终点不在一个强联通分量中，则这个强联通分量的出度++ 
			if (f[i]!=f[edge[j].v]){
				num[f[i]]++;
			}
		}
	} 
	int ans=0;
	/* ans: 目前出度为 0 的群体（只有它被喜欢的可能）*/ 
	for (int i=1;i<=s;i++){
		if (!num[i]){ 
		// 如果这群牛不喜欢其他的牛，则只有被别的牛喜欢的可能 
			if (ans==0){
				ans=i;
			}
			else {
				// 如果另一个团体的出度也为 0，则这群牛就不可能被所有牛喜欢，另一群牛也是如此，故无解 
				cout<<0<<endl;
				return 0;
			}
		}
	}
	cout<<siz[ans];
	return 0;
} 

评测记录