#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define lowbit(i) ((i)&(-i))
#define pii pair<int,int>
#define endl '\n'
#define mk(x,y) make_pair(x,y)
#define popcount(x) __builtin_popcount(x)
const double pi=3.14159265358979323846;
const double eps=1e-9;
const int inf=1e9;
const long long INF=4e18;
const int mod=1e9+7;
using namespace std;
const int N=1e5+10;

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>>e(n+1),g(n+1);
    bool flag=false;
    vector<int>in(n+1);
    for(int i=1;i<=m;i++){
    	int a,b;
    	cin>>a>>b;
    	e[a].push_back(b);
        in[b]++;
        g[b].push_back(a);
        if(a==b)flag=1;
    }
    if(flag){
        for(int i=1;i<=n;i++){
            cout<<"0";
        }
        cout<<endl;
        return;
    }
    int cnt=n/2;
    vector<int>ans(n+1,1);
    vector<int>pre(n+1),suf(n+1);//前驱结点与后继结点的个数
    vector<bool>vis(n+1,false);
    auto toposort=[&](){
        vector<int>L;
        queue<int>q;
        for(int i=1;i<=n;i++){
            if(in[i]==0)q.push(i);
        }
        while(q.size()){
            int u=q.front();
            q.pop();
            L.push_back(u);
            for(auto v:e[u]){
                if(--in[v]==0){
                    q.push(v);
                }
            }
        }
        if(L.size()==n){
            // for(auto i:L)cout<<i<<" ";
            return L;//无环
        }
        else {
            return L;
        }
    };
    function<void(int,int)> dfs1=[&](int u,int fa){
        if(fa)pre[u]+=pre[fa];
        else pre[u]=1;
        vis[u]=1;
        for(int v:e[u]){
            dfs1(v,u);
        }
    };
    vector<int> L=toposort();
    for(int i:L){
        if(!vis[i])dfs1(i,0),pre[i]=0;
    }
    vis=vector<bool>(n+1,false);
    function<void(int,int)> dfs2=[&](int u,int fa){
        if(fa)suf[u]+=suf[fa];
        else suf[u]=1;
        vis[u]=1;
        for(int v:g[u]){
            // cout<<u<<" "<<v<<endl;
            dfs2(v,u);
        }
    };
    // for(int i:L)cout<<i<<" ";
    cout<<endl;
    for(int i=L.size()-1;i>=0;i--){
        if(!vis[L[i]])dfs2(L[i],0),suf[L[i]]=0;
    }
    for(int i=1;i<=n;i++){
        cout<<pre[i]<<" "<<suf[i]<<endl;
    }
    for(int i=1;i<=n;i++){
        if(suf[i]>n/2||pre[i]>n/2)ans[i]=0;
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i];
    }
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}