#include<bits/extc++.h>
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,O3")
using namespace std;using ll = long long;using ull = unsigned long long;using ul = unsigned;using db = double;using __gnu_pbds::null_type;
#ifdef _debug 
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#define dout(i) 0&&0
#endif
#define eout(i) {cout << (i) << '\n';exit(0);}
#define priority_queue __gnu_pbds::priority_queue
#define unordered_map __gnu_pbds::gp_hash_table
#define rep(a, b) {for(int i = a;i > 0;--i){b;}}
#define multe int T;for(cin >> T;T--;)
pair<long long, long long> ext_gcd(long long a, long long b){if(a % b == 0)return {0ll, 1ll};auto get = ext_gcd(b, a % b);return {get.second, get.first - a / b * get.second};}
long long ext_inv(long long a, long long p){return (ext_gcd(a, p).first + p) % p;}
vector<int> kfunc(string &w){vector<int> k(w.size());for(int q = 0, i = 1;i < w.size();++i){for(;q > 0 and w[i] != w[q];q = k[q-1]);k[i] = (q += w[i] == w[q]);}return k;}
vector<int> zfunc(string &w){vector<int> z(w.size());z[0] = w.size();for(int l = 0, i = 1;i < w.size();++i){z[i] = max(0, min(l+z[l] - i, z[i-l]));for(;i+z[i] < w.size() and w[i+z[i]] == w[z[i]];++z[i])l = i;}return z;}
template<typename T> using rbtree = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T> inline long long pow(long long v, long long t, const T &p){long long res = 1;for(;t;t >>= 1, v = v * v % p)if(t & 1)res = res * v % p;return res;}
template<typename T> inline void floyd_warshall(vector<vector<T>> &dp){for(int i = 0;i < dp.size();++i)for(int j = 0;j < dp.size();++j)for(int k = 0;k < dp.size();++k)dp[i][k] = min(dp[i][k], dp[i][j] + dp[j][k]);}
template<typename T> inline ostream& operator << (ostream &ou, const vector<T> &a){for(auto it = a.begin();it != a.end();++it)ou << (it != a.begin() ? " " : "") << *it;return ou;}
template<typename T> inline vector<vector<T>> operator * (const vector<vector<T>> &a, const vector<vector<T>> &b){assert(a.front().size() == b.size());vector<vector<T>> res(a.size(), vector<T>(b.front().size()));for(int i = 0;i < a.size();++i)for(int j = 0;j < b.front().size();++j)for(int k = 0;k < a.front().size();++k)res[i][j] += a[i][k] * b[k][j];return res;}
template<typename T> inline vector<vector<T>> pow(vector<vector<T>> v, long long t){vector<vector<T>> res;for(;t;t >>= 1, v = v * v)if(t & 1)res = (res.empty() ? v : res * v);return res;}
template<typename T> void read(int n, T *s){while(n--)cin >> *s, ++s;}
template<typename T> void read(int n, vector<T> &v){for(int i = 0;i < n;++i)cin >> v[i];}
template<typename T> void write(int n, T *s){while(n--)cout << *s << " \n"[n==0], ++s;}
template<typename T1, typename T2>inline istream& operator >> (istream &in, pair<T1, T2> &a){return in >> a.first >> a.second;}
template<typename T1, typename T2>inline ostream& operator << (ostream &ou, const pair<T1, T2> &b){return ou << b.first << ' ' << b.second;}
template<typename T1, typename T2>inline pair<T1,T2> operator + (const pair<T1,T2> &a, const pair<T1,T2> &b){return {a.first + b.first, a.second + b.second};}
template<typename T1, typename T2>inline pair<T1,T2> operator - (const pair<T1,T2> &a, const pair<T1,T2> &b){return {a.first - b.first, a.second - b.second};}
template<typename T1, typename T2>inline long long operator ^ (const pair<T1,T2> &a, const pair<T1,T2> &b){return (long long)a.first * b.second - (long long)a.second * b.first;}
const int maxn = 1010;
int n, m;
vector<pair<int,int>> alle;
vector<int> edge[maxn];
vector<vector<int>> dp;
int g[maxn];
void dfs(int now){
	static int low[maxn], d = 0, id = 1, onpath[maxn];
	if(onpath[now])return;
	low[now] = ++d;
	onpath[now] = true;
	for(int &i : edge[now]){
		if(onpath[i] || !low[i]){
			dfs(i), low[now] = min(low[now], low[i]);
			if(low[i] > d)++id;
		}
	}
	g[now] = id; 
	onpath[now] = false;
	--d;
}
string output[2]{"same\n", "diff\n"};
int depen[maxn];
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	alle.reserve(m);
	dp.resize(n+1, vector<int> (n+1, maxn));
	for(int i = 0, a, b;i < m;++i){
		cin >> a >> b;
		edge[a].emplace_back(b);
		alle.emplace_back(a, b);
		dp[a][b] = 1;
	}
	dfs(1);

	floyd_warshall(dp);
	for(int i = 1;i <= n;++i)cout << g[i] << ' ';cout << '\n';

	for(int i = 1;i <= n;++i){
		while(edge[i].size() and g[edge[i].back()] != g[i])edge[i].pop_back();
		for(int j = 0, r = (int)edge[i].size()-1;j < r;++j){
			if(g[i] != g[edge[i][j]])swap(edge[i][j], edge[i][r]), --r;
		}
		while(edge[i].size() and g[edge[i].back()] != g[i])edge[i].pop_back();
		for(int &j : edge[i])++depen[j];
	}
	for(const auto &e : alle){
#define f first
#define s second
		int res = 0;
		if(g[e.f] == g[e.s]){
			// dout(e.f)<<' '<< edge[e.f].size() << '\n';
			res = edge[e.f].size() == 1 || depen[e.s] == 1;
		}	
		else{
			for(int i = 1;i <= n and !res;++i)if(i != e.f and i != e.s and g[i] != g[e.f] and g[i] != g[e.s]){
				if(dp[e.f][i] != dp[e.s][i]+1 and dp[e.f][i] < maxn and dp[i][e.s] < maxn)res = 1;
			}
		}
		cout << output[res];
	}
}