exodus

#include <iostream>
#include <vector>

using namespace std;

bool Valid(int * pointers, bool *GlobalExclude, bool *excludeR, bool *excludeG, vector<int> *recieve, vector<int> *give, int pos){

	if(excludeR[pointers[pos]] == true || excludeG[pointers[pos]] == true || GlobalExclude[pointers[pos]] == true)
	return false;

	for(int i = 0; i < give[pointers[pos]].size(); i++){
		if(excludeG[give[pointers[pos]].at(i)] == true)
		return false;
	}

	for(int i = 0; i < recieve[pointers[pos]].size(); i++){
		if(excludeR[recieve[pointers[pos]].at(i)] == true)
		return false;
	}

	return true;
}

void Exclude (int *pointers, bool *GlobalExclude, bool *excludeR, bool *excludeG, vector<int> *recieve, vector<int> *give, int pos){

	GlobalExclude[pos] = true;

	for(int i = 0; i < recieve[pos].size(); i++){
		excludeG[pointers[recieve[pos].at(i)]] = true;
		//cout << "excluding G " << pointers[recieve[pos].at(i)] << endl;
	}
	for(int i = 0; i < give[pos].size(); i++){
		excludeR[pointers[give[pos].at(i)]] = true;
		//cout << "excluding R " << pointers[give[pos].at(i)] << endl;
	}
}

int main(){
	int t, n, m;
	int temp1, temp2;
	int assigned, hero;
	cin >> t;
	while(t--){
		assigned = 0;

		cin >> n >> m;

		char *heroes = new char[n+1];
		vector<int>* recieve = new vector<int>[n+1];
		vector<int>* give = new vector<int>[n+1];

		bool *excludeR = new bool[n+1];
		bool *excludeG = new bool[n+1];
		bool *GlobalExclude = new bool [n+1];

		int *pointers = new int [n+1]; //so pointery pointers that intigers, trust me it works that way, If they would be more pointy they would be floating point numbers

		for(int i = 1; i <= n; i++){
			GlobalExclude[i] = false;
			pointers[i] = i;
		}

		for(int i = 0; i < m; i++){
			cin >> temp1 >> temp2;
			recieve[temp1].push_back(temp2);
			give[temp2].push_back(temp1);
		}

		/*for(int i = 1; i <= n; i++){
			for(int j = 0; j < recieve[i].size(); j++){
				cout << recieve[i].at(j) << " ";
			}
			cout << endl;
		}*/

		for(char j = 1; j < 8 && assigned < n; j++){ // petla dla kazdego bohatera
		//cout << "hero " << j << endl;
			hero = 0;
			for(char k = 1; k <=n; k++){
				excludeG[k] = false;
				excludeR[k] = false;
			}
			for(int i = j; i <= n; i++){ // petla dla kazdej tozsamosci

				//cout << "identity " << i << endl;

				if(Valid(pointers, GlobalExclude, excludeR, excludeG, recieve, give, i)){
					heroes[i] = j;
					Exclude(pointers, GlobalExclude, excludeR, excludeG, recieve, give, i);

					/*cout << "excluded ";
					for(int exc = 1; exc <= n; exc++){
						if(excludeG[exc] || excludeR[exc] || GlobalExclude[exc])
						cout << exc << ' ';
					}
					cout << endl;*/

					assigned++;

					if(hero){
						recieve[hero].insert( recieve[hero].end(), recieve[i].begin(), recieve[i].end() );
						give[hero].insert( give[hero].end(), recieve[i].begin(), recieve[i].end() );
						pointers[i] = hero;

						if(recieve[i].empty())
						recieve[i].~vector<int>();
						if(give[i].empty())
						give[i].~vector<int>();

						/*cout << "pointers ";
						for(int whatever = 1; whatever <= n; whatever++)
						cout << pointers[whatever] << ' ';
						cout << endl;*/
					}
					else{
						hero = i;
					}

				}
			}
		}

		for(int i = 1; i <= n; i++){
			cout << int(heroes[i]) << ' ';
		}
		cout << endl;

		delete[] heroes;
		delete[] recieve;
		delete[] give;

		delete[] GlobalExclude;
		delete[] excludeR;
		delete[] excludeG;

		delete[] pointers;
	}
}

/*
Załozenie jes takie, że przydzielam pierwszemu superbohaterowi pierwszą rożsamosć (i tak ktoś musi ją mieć) a następnie przydzielam mu takie tożsamości które spełniają warunki:
n-ta tożsamość
1) nie poznaje tożsamości przydzielonych dla bohatera 1
2) tożsamości bohatera 1 nie poznają n-tej tożsamości
3) tozsamości bohatera nie poznają tożsamości które poznają n-tą tożsamość
4) tożsamoś nie poznaje tożsamości które poznają którąś z tożsamości bohatera

mam za tam liste wszystkich tożsamości i 3 listy wykluczeń
excludeR wskazuje na tożsamości które otrzymują informacje o jednej z tozsamości bohatera
excludeG wskazuje na tozsamości które o których informache ma bohater
GlobalExclude zawiera tożsamosci które są już przypisane do któregos z bohaterów

jako że tożsamości nie są przydzielane pokolei mam tablice heroes która każdej tożsamości przypisuje bohatera który ją posiada
heroes[n+1]

są dwie tablice wektorów
recieve[n+1] która każdej z tożsamości przypisuje tożsamości od których odrzymuje dane
give[n+1] która każdej tożsamości przypisuje tożsamości którym przekazuje swoje dane

int assigned zapamiętuje ile tożsamości było już przydzielonych żeby zakończyć pracę programu jak wszystkie zostana przydzielone

int pointers[n+1] unifikuje wszystkie tożesamości bohatera, pierwsza tożsamosć jaką dostaje bohater staje sie dominująca i wszyskie relacje pozostałych tożsamosci są
przerzucone do dominującej, a przy sprawdzaniu poprawności pola i zaznaczaniu zakazanych pól młodsze tożsamości bohatera (te które zostały później dodane) są maskowan główną tożsamością

funkcja Valid sprawdza czy dana tożsamość może być przydzielona do danego bohatera

funkcja Exclude wyklucza tożsamości ktore nie mogę być przydzielone danemu bohaterowi



proste sprawdzenia:
5
3 2
1 2
1 3
5 5
1 2
2 3
3 4
4 5
5 1
7 10
1 2
2 3
1 4
2 4
3 4
4 5
4 6
4 7
5 6
6 7
9 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 1
4 2
2 3
4 1


odpowiedzi
1 2 2
1 2 3 4 5
1 2 3 4 5 6 7
1 2 3 1 2 3 1 2 3
1 1 2 3

*/