Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 1000010

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

bool v[MAXN];

int ins[MAXN],scc = 0;

int siz[MAXN];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])low[k] = min(low[k],dfn[e[i].to]);

	}

	if(dfn[k] == low[k])

	{

		++scc;

		int t;

		do

		{

			t = s.top();s.pop();

			ins[t] = scc;v[t] = false;

			++siz[scc];

		}while(t != k);

	}

	return;

}

vector<int> g[MAXN];

bool tag = false;

int ind[MAXN];

#define INF 0x3f3f3f3f

bool type[MAXN];

int f[MAXN];

int main()

{

	scanf("%d%d",&n,&m);++n;

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	for(int i = 1;i <= n;++i)

		if(dfn[i] == 0)tarjan(i);

	for(int i = 1;i <= scc;++i)

	{

		if(siz[i] > 1)type[i] = true;

		else type[i] = false;

	}

	for(int k = 1;k <= n;++k)

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(ins[k] != ins[e[i].to])

			{

				g[ins[e[i].to]].push_back(ins[k]);

				++ind[ins[k]];

			}

			else if(k == e[i].to)type[ins[k]] = true;

		}

	}

	f[ins[n]] = 1;

	queue<int> q;

	for(int i = 1;i <= scc;++i)

	{

		if(ind[i] == 0)q.push(i);

	}

	while(!q.empty())

	{

		int k = q.front();q.pop();tag |= type[k];

		for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

		{

			--ind[*it];

			type[*it] |= type[k];

			f[*it] = min(36501,f[*it] + f[k]);

			if(ind[*it] == 0)q.push(*it);

		}

	}

	if(tag)

	{

		cout << "zawsze" << endl;

		int ans = 0;

		for(int i = 1;i <= n - 1;++i)

			if((type[ins[i]] && f[ins[i]] != 0) || f[ins[i]] > 36500)++ans;

		cout << ans << endl;

		for(int i = 1;i <= n - 1;++i)

			if((type[ins[i]] && f[ins[i]] != 0) || f[ins[i]] > 36500)printf("%d ",i);

		cout << endl;

	}

	else

	{

		int maxf = 0;

		for(int i = 1;i <= scc;++i)maxf = max(maxf,f[i]);

		if(maxf > 36500)

		{

			cout << "zawsze" << endl;

			int ans = 0;

			for(int i = 1;i <= n - 1;++i)

				if(f[ins[i]] > 36500)++ans;

			cout << ans << endl;

			for(int i = 1;i <= n - 1;++i)

				if(f[ins[i]] > 36500)printf("%d ",i);

			cout << endl;

		}

		else

		{

			cout << maxf << endl;

			int ans = 0;

			for(int i = 1;i <= n - 1;++i)

				if(maxf == f[ins[i]])++ans;

			cout << ans << endl;

			for(int i = 1;i <= n - 1;++i)

				if(maxf == f[ins[i]])printf("%d ",i);

			cout << endl;

		}

	}

	return 0;

}