#include <cstdio>
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

const int N = 1E5+5;
int n, k;

queue<int> a[N]; //left bound positive, right bound negative
unordered_set<int> effect[N]; //numbers limited by each pairs
unordered_set<int> b[N]; //limited numbers
unordered_set<int> activated; //activated pairs
int main(){
    int t;
    cin>>t;
    for(int o = 0; o<t; o++){
        cin>>k>>n;
        for(int i=0;i<=k || i<=n;i++){
            while(!a[i].empty()) a[i].pop();
            effect[i].clear();
            b[i].clear();
        }
        activated.clear();
        for(int i = 1; i<=n; i++){
            int x,y;
            cin>>x>>y;
            a[x].push(i); // a[1]={1}, a[2]={2}
            a[y].push(-i);// a[3]={-1},a[4]={-2}
        }
        int num = 1;
        for(int i = 1; i<=k; i++){
            queue<int> closing;
            while(!a[i].empty()){
                int x = a[i].front();
                a[i].pop();
                if(x>0){
                    activated.insert(x); // activated={}
                }
                else{
                    closing.push(-x); // closing={}
                }
            }
            // 1 2 3...,1000,1,1001,2,1002,3,1003,4,1004
            while(!b[num].empty()) num++; // n/4*n/2=n^2/8
            cout<<num; // num=1, 2, 3, 1
            if(i < k) cout<<' ';
            for(int j : activated){
                effect[j].insert(num); // effect[1]={1,2,3} effect[2]={2,3,1}
                b[num].insert(j); // b[1]={} b[2]={} b[3]={}
            }
            while(!closing.empty()){
                int x = closing.front(); // x=2
                closing.pop();
                activated.erase(x);
                for(int j : effect[x]){ //
                    b[j].erase(x); // 
                    num = min(num, j); // num=1
                }
            }
        }
        cout<<endl;
    }
}