P1022

#include <bits/stdc++.h>

typedef std::pair<int, int> PII;
const int N = 410, M = (N * N);
int t, n, m, k;
std::vector<int> adj[N];
PII edges[M];
int col[N][N];
int have[N][N];
bool vis[N];
struct Fan {
    int cen; // centre;
    std::vector<int> sat; // satellite

    void init(void) {
        cen = 0;
        sat.clear();
        sat.shrink_to_fit();
        return;
    }
};

void add(int u, int v) {
    adj[u].push_back(v);
    return;
}
void biadd(int u, int v) {
    add(u, v), add(v, u);
    return;
}
void get_fan(int u, int v, Fan &f) {
    f.cen = u;
    f.sat.push_back(v);
    for (int i = 1; i <= n; ++ i) {
        vis[i] = false;
    }
    vis[v] = true;
    bool notmax = true;
    while (notmax) {
        notmax = false;
        for (int i = 0, lim = adj[u].size(); i < lim; ++ i) {
            int w = adj[u][i];
            if (!vis[w] && col[u][w] != 0 && have[v][col[u][w]] == 0) {
                f.sat.push_back(w);
                vis[w] = true;
                v = w;
                notmax = true;
            }
        }
    }
    return;
}
int mexcol(int x) {
    int c = 1;
    for ( ; c <= k && have[x][c] != 0; ++ c);
    return c;
}
void go_path(int u, int v, int cl, int cu, std::vector<int> &path) {
    path.push_back(u), path.push_back(v);
    int now = v, c = cu;
    while (have[now][c] != 0) {
        path.push_back(have[now][c]);
        now = have[now][c];
        c = cl + cu - c;
    }
    return;
}
void color(int u, int v, int c) {
    col[u][v] = col[v][u] = c;
    if (c != 0) {
        have[u][c] = v;
        have[v][c] = u;
    }
    return;
}
void rotate_and_color(Fan &f, int w, int cl) {
    int pos = 0;
    for (int i = 0, lim = f.sat.size(); i < lim; ++ i) {
        int c = col[f.cen][f.sat[i]];
        if (c != 0) {
            have[f.cen][c] = have[f.sat[i]][c] = 0; 
        }
        if (f.sat[i] == w) {
            pos = i;
            break;
        }
    }
    for (int i = 1; i <= pos; ++ i) {
        color(f.cen, f.sat[i - 1], col[f.cen][f.sat[i]]);
    }
    color(f.cen, w, cl);
    return;
}
Fan f;
std::vector<int> path;
void misra_gries(void) {
    for (int i = 1; i <= m; ++ i) {
        int u = edges[i].first;
        int v = edges[i].second;
        f.init();
        get_fan(u, v, f);
        int cl = mexcol(f.sat[f.sat.size() - 1]);
        int cu = mexcol(u);
        int w = 0;
        for (int i = 0, limi = f.sat.size() - 1; i < limi; ++ i) {
            if (col[u][f.sat[i]] == cl) {
                path.clear();
                path.shrink_to_fit();
                go_path(u, f.sat[i], cl, cu, path);
                for (int j = 0, limj = path.size(); j < limj - 1; ++ j) {
                    int c = col[path[j]][path[j + 1]];
                    have[path[j]][c] = have[path[j + 1]][c] = 0;
                }
                for (int j = 0, limj = path.size(); j < limj - 1; ++ j) {
                    color(path[j], path[j + 1], cl + cu - col[path[j]][path[j + 1]]);
                }
                for (int j = 0, limj = path.size(); j < limj; ++ j) {
                    if (path[j] == f.sat[i - 1]) {
                        w = f.sat[f.sat.size() - 1];
                        break;
                    }
                }
                if (w == 0) {
                    w = f.sat[i - 1];
                }
                break;
            }
        }
        if (w == 0) {
            w = f.sat[f.sat.size() - 1];
        }
        rotate_and_color(f, w, cl);
    }
    return;
}

int main(void) {
    scanf("%d", &t);
    while (t --) {
        scanf("%d%d", &n, &m);
        for (int i = 1, inpx, inpy; i <= m; ++ i) {
            scanf("%d%d", &inpx, &inpy);
            biadd(inpx, inpy);
            edges[i] = std::make_pair(inpx, inpy);
        }
        k = 0;
        for (int i = 1; i <= n; ++ i) {
            k = std::max(k, int(adj[i].size()));
        }
        misra_gries();
        for (int i = 1; i <= m; ++ i) {
            printf("%d ", col[edges[i].first][edges[i].second]);
        }
        puts("");
        for (int i = 1; i <= n; ++ i) {
            adj[i].clear();
            adj[i].shrink_to_fit();
            for (int j = 1; j <= n; ++ j) {
                col[i][j] = have[i][j] = 0;
            }
        }
    }
    return 0;
}