#include <bits/stdc++.h>

#define debug(...) 42;
#ifdef LOCAL
#include "debug.h"
#endif

using namespace std;
#define V vector
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define F(i, l, r) for (int i = l; i < r; ++i)
#define R(i, l, r) for (int i = r-1; i >= l; --i)
typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
// mt19937_64 rng {chrono::steady_clock::now().time_since_epoch().count()};

/* -------------Main code------------- */
struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int _n) {
        n = _n;
        p.resize(n);
        sz.resize(n, 1);
        iota(all(p), 0);
    }
    int size(int u) {
        return sz[leader(u)];
    }
    int leader(int u) { return u == p[u] ? u : p[u] = leader(p[u]); }
    bool merge(int u, int v) {
        int a = leader(u), b = leader(v);
        if (a != b) {
            if (sz[a] < sz[b]) swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
            return true;
        }
        return false;
    }
};

void solve() {
    int n, m; cin >> n >> m;
    V<V<int>> g(n + 1), g_t(n + 1);
    V<int> d(n + 1), d_t(n + 1);

    DSU dsu(n + 1);
    F(i, 0, m) {
        int u, v; cin >> u >> v;
        dsu.merge(u, v);
        d[v]++;
        d_t[u]++;
        g[u].emplace_back(v);
        g_t[v].emplace_back(u);
    }

    auto has = [&]() {
        V<int> q;
        F(i, 1, n + 1) if (d[i] == 0) q.push_back(i);
        for (int i = 0; i < sz(q); i++) {
            int u = q[i];
            for (int v : g[u]) if (--d[v] == 0) q.push_back(v);
        }
        for (int i = 1; i <= n; i++) if (d[i]) return true;
        return false;
    };

    if (has()) {
        cout << string(n, '0') << '\n';
        return;
    }

    V<int> comp1(n + 1, -1), comp2(n + 1, -1);
    auto dfs1 = [&](auto self, int u) -> int {
        if (comp1[u] != -1) return comp1[u];
        int res = 0;
        for (int v : g[u]) {
            res += self(self, v) + 1;
        }
        return comp1[u] = res;
    };
    auto dfs2 = [&](auto self, int u) -> int {
        if (comp2[u] != -1) return comp2[u];
        int res = 0;
        for (int v : g_t[u]) {
            res += self(self, v) + 1;
        }
        return comp2[u] = res;
    };
    for (int u = 1; u <= n; u++) {
        comp1[u] = dfs1(dfs1, u);
    }
    for (int u = 1; u <= n; u++) {
        comp2[u] = dfs2(dfs2, u);
    }
    // debug(comp1, comp2);
    V<int> w;
    for (int i = 1; i <= n; i++)
        if (i == dsu.leader(i))
            w.emplace_back(dsu.size(i));
    for (int i = 1; i <= n; i++) {
        if (comp1[i] <= n / 2 and comp2[i] <= n / 2) {
            assert(comp1[i] != -1 and comp2[i] != -1);
            V<int> f(n + 1);
            f[0] = 1;
            int id = -1;
            for (int j = 0; j < sz(w); j++)
                if (w[j] == dsu.size(i)) { id = j; break; }
            for (int j = 0; j < sz(w); j++) {
                if (j == id) continue;
                for (int k = n; k >= w[j]; k--)
                    f[k] |= f[k - w[j]];
            }
            if (n / 2 - comp1[i] >= 0 and f[n / 2 - comp1[i]]) {
                cout << 1;
            } else cout << 0;
        } else cout << 0;
    }
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int tt; cin >> tt;
    while (tt--) solve();

    return 0;
}