#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int minv = 1e9+1;
		int maxv = -1;
		int mini;
		int maxi;
		for(int i=0; i < n; ++i) {
			int a;
			cin >> a;
			if(a > maxv) {
				maxi = i+1;
				maxv = a;
			}
			if(a < minv) {
				mini = i+1;
				minv =  a;
			}
		}
		cout << mini << " " << maxi << endl;
	}
 
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, a;
    	cin >> n >> a;
    	vector<int> v(n);
    	for(int& x : v) cin >> x;
    	bool ans = false;
    	if(n == 1) ans = (v[0] == a);
    	else {
    		sort(v.begin(), v.end());
    		int i = 0;
    		int j = 1;
    		while(j < n and i < n) {
    			if(v[i] + abs(a) == v[j]) {
    				ans = true;
    				break;
    			}
    			else if(v[i] + abs(a) < v[j]) ++i;
    			else ++j;
    		}
    	}
    	cout << (ans? "YES" : "NO") << '\n';   
    }
}

#include<bits/stdc++.h>
 
using namespace std;
 
typedef vector<int> vi;
 
 
int main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		vi a(n);
		for(int i=0; i < n; ++i) cin >> a[i];
		sort(a.begin(), a.end());
		bool one = false;
		bool consec = false;
		for(int i=0; i < n; ++i) {
			if(a[i] == 1) one = true;
			if(i < n-1 && a[i]+1 == a[i+1]) consec = true;
		}
 
		cout << ((one && consec) ? "NO" : "YES") << endl;
	}
 
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
 
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--) {
		ll n;
		cin >> n;
		ll x = n;
		while(x % 2 == 0) x /= 2;
		if(x == 1) {
			cout << -1 << endl;
		}
		else if(x <= 2e9 && (x*(x+1))/2 <= n) {
			cout << x << endl;
		}
		else {
			cout << 2*(n/x) << endl;
		}
	}
}

#include<bits/stdc++.h>
 
using namespace std;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
 
vvi al;
vi ans;
 
void dfs(int u, int p, int c) {
	ans[u] = ((int)al[u].size())*c;
	for(int v : al[u]) {
		if(v != p) {
			dfs(v, u, -c);
		}
	}
}
 
int main() {
	int T;
	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		al = vvi(n);
		for(int i=0; i < n-1; ++i) {
			int u, v;
			cin >> u >> v;
			u--;
			v--;
			al[u].push_back(v);
			al[v].push_back(u);
		}
		ans = vi(n);
		dfs(0, -1, 1);
		for(int i=0; i < n; ++i) {
			cout << ans[i];
			if(i < n-1) cout << " ";
		}
		cout << endl;
	}
}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;

int main() {
	int T;
	cin >> T;
	while(T--) {
		ll n;
		cin >> n;
		vi a(n);
		ll tsum = 0;
		for(int i=0; i < n; ++i) {
			cin >> a[i];
			tsum += a[i];
		}
		sort(a.begin(), a.end());
		if(a[n-1]*(n-2) + tsum < 0 || a[0]*(n-2) + tsum > 0) {
			cout << "INF" << endl;
			continue;
		}

		ll cslope = a[n-1]*(n-2) + tsum;
		ll cvalue = -(n-1)*a[n-1]*a[n-1];
		

		ll ans = cvalue;
		for(ll i=1; i < n; ++i) {
			ll d = a[n-i]-a[n-i-1];
			cvalue += cslope*d;
			ans = max(cvalue, ans);

			cslope += a[0]-a[n-1];


		}
		cout << ans << endl;
	}
}

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

vi obtain_p_permutation(const vi& a) {
	int n = a.size();
	vi pp(n, -1);
	vi p(n);
	int cp = 0;
	vi cnt(n);
	for(int i=0; i < n; ++i) {
		cnt[a[i]]++;
	}
	for(int i=0; i < n; ++i) {
		if(pp[a[i]] == -1) {
			if(cnt[a[i]] == 1) {
				p[i] = n/2;
			}
			else {
				p[i] = cp;
				pp[a[i]] = n-cp-1;
				cp++;
				cnt[a[i]]--;
			}
		}
		else {
			p[i] = pp[a[i]];
			pp[a[i]] = -1;
			cnt[a[i]]--;
		}
	}
	return p;
}

vvi find_cycles(vi p, vi& in_cyc) {
	int n = p.size();
	vi vis = vi(n);
	vvi cycles;
	for(int i=0; i < n; ++i) {
		if(!vis[i]) {
			vi cyc;
			int v = i;
			while(!vis[v]) {
				cyc.push_back(v);
				in_cyc[v] = cycles.size();
				vis[v] = true;
				v = p[v];
			}
			cycles.push_back(cyc);
		}
	}
	return cycles;
}

int find_set(vi& dsu, int x) {
	if(dsu[x] == x) return x;
	return dsu[x] = find_set(dsu, dsu[x]);
}

void solve() {
	int n;
	cin >> n;
	vi a(n);
	vi cnt(n);
	for(int i=0; i < n; ++i) {
		cin >> a[i];
		a[i]--;
		cnt[a[i]]++;
	}
	int odd_i = -1;
	for(int i=0; i < n; ++i) {
		if(cnt[i]%2 == 1) {
			if(odd_i == -1) {
				odd_i = i;
			}
			else {
				odd_i = -2;
			}
		}
	}
	if(odd_i == -2) {
		cout << "NO" << endl;
	}
	else if(odd_i != -1 && (cnt[odd_i] == 1 && odd_i == a[n/2])) {
		cout << "NO" << endl;
	}
	else {

		vi p = obtain_p_permutation(a);
		if(odd_i != -1 && p[n/2] == n/2) {
			for(int i=0; i < n; ++i) {
				if(i != n/2 && a[i] == odd_i) {
					p[n/2] = p[i];
					p[i] = n/2;
					break;
				}
			}
		}
		vi rp(n);
		for(int i=0; i < n; ++i) {
			rp[p[i]] = i;
		}
		vvi cycles;
		vi in_cyc(n);
		cycles = find_cycles(p, in_cyc);


		vi dsu(n);
		for(int i=0; i < n; ++i) dsu[i] = i;
		for(int i=0; i < n; ++i) {
			if(find_set(dsu, in_cyc[i]) != find_set(dsu, in_cyc[n-i-1])) {
				dsu[find_set(dsu, in_cyc[i])] = find_set(dsu, in_cyc[n-i-1]);
				int j1 = rp[i];
				int j2 = rp[n-i-1];
				p[j2] = i;
				rp[i] = j2;
				p[j1] = n-i-1;
				rp[n-i-1] = j1;  
			}
		}
		cycles = find_cycles(p, in_cyc);
		int nc = cycles.size();
	

		vi prev_p = vi(p);
		vi prev_rp = vi(rp);

		for(int i=0; i < nc-1; ++i) {
			int i0 = cycles[i][0];
			int ip1 = cycles[(i+1)][0];
			p[prev_rp[n-i0-1]] = ip1;
			rp[ip1] = prev_rp[n-i0-1]; 
		}
		p[prev_rp[n-cycles[nc-1][0]-1]] = n-cycles[0][0]-1;
		rp[n-cycles[0][0]-1] = prev_rp[n-cycles[nc-1][0]-1];
		for(int i=0; i < nc-1; ++i) {
			int i0 = cycles[i][0];
			int ip1 = cycles[(i+1)][0];
			p[prev_rp[i0]] = n-ip1-1;
			rp[n-ip1-1] = prev_rp[i0];
		}
		p[prev_rp[cycles[nc-1][0]]] = cycles[0][0];
		rp[cycles[0][0]] = prev_rp[cycles[nc-1][0]];

		cout << "YES" << endl;
		for(int i=0; i < n; ++i) {
			cout << rp[i]+1 << " ";
		}
		cout << endl;

	}
	


}

int main() {
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
}

#include<bits/stdc++.h>
 
using namespace std;
 
typedef __int128 ll; 
typedef vector<ll> vi;
typedef vector<vi> vvi;
 
 
ll read_ll() {
	string s;
	cin >> s;
	ll x = 0;
	for(int i=0; i < (int)s.length(); ++i) {
		x *= 10;
		x += ll(s[i]-'0');
	}
	return x;
}
 
void print_ll(ll x) {
	vector<int> p;
	while(x > 0) {
		p.push_back((int)(x%10));
		x /= 10;
	}
	reverse(p.begin(), p.end());
	for(int y : p) cout << y;
}
 
inline ll ctz(ll x) {
	long long a = x&((ll(1)<<ll(63))-ll(1));
	long long b = x>>ll(63);
	if(a == 0) return ll(63)+__builtin_ctzll(b);
	return __builtin_ctzll(a);  
}
 
inline ll abll(ll x) {
	return x >= 0 ? x : -x;
}
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	if(a == 0) return b;
 
	int az = ctz(a);
	int bz = ctz(b);
	int shift = min(az, bz);
	b >>= bz;
 
	while(a != 0) {
		a >>= az;
		ll diff = b-a;
		if(diff) az = ctz(diff);
		b = min(a, b);
		a = abll(diff);
	}
	return b << shift;
}
 
void init_st(vi& st, const vi& v) {
	int n = v.size();
	for(int i=0; i < n; ++i) {
		st[n+i] = v[i];
	}
	for(int i=n-1; i >= 1; --i) {
		st[i] = gcd(st[2*i], st[2*i+1]);
	}
}

void update_st(vi& st, int i, ll x) {
	int n = (int)st.size() / 2;
	int pos = n+i;
	st[pos] = x;
	while(pos > 1) {
		pos /= 2;
		st[pos] = gcd(st[2*pos], st[2*pos+1]);
	}
}
 
void solve(const vi& a, const vi& b, vector<bool>& ai, vector<bool>& bi) {
	int n = a.size();
	int m = b.size();
	vvi st_a = vvi(n, vi(2*m, 0));
	vvi st_b = vvi(m, vi(2*n, 0));
	for(int i=0; i < n; ++i) {
		vi af(m);
		for(int j=0; j < m; ++j) {
			af[j] = a[i]/gcd(a[i], b[j]);
		}
		init_st(st_a[i], af);
	}
	for(int i=0; i < m; ++i) {
		vi bf(n);
		for(int j=0; j < n; ++j) {
			bf[j] = b[i]/gcd(b[i], a[j]);
		}
		init_st(st_b[i], bf);
	}
	queue<int> dq;
	for(int i=0; i < n; ++i) {
		if(st_a[i][1] > 1) {
		       	dq.push(i);
			ai[i] = false;
		}
	}
	for(int i=0; i < m; ++i) {
		if(st_b[i][1] > 1) {
		       	dq.push(n+i);
			bi[i] = false;
		}
	}
	while(!dq.empty()) {
		int idx = dq.front();
		dq.pop();
		if(idx < n) {
			int i = idx;
			for(int j=0; j < m; ++j) {
				if(bi[j]) {
					update_st(st_b[j], i, b[j]);
					if(st_b[j][1] > 1) {
						dq.push(n+j);
						bi[j] = false;
					}
				}
			}
		}
		else {
			int i = idx-n;
			for(int j=0; j < n; ++j) {
				if(ai[j]) {
					update_st(st_a[j], i, a[j]);
					if(st_a[j][1] > 1) { 
						dq.push(j);
						ai[j] = false;
					}
				}
			}
		}
	}	
 
}
 
 
 
int main() {
	int T;
	cin >> T;
	while(T--) {
		int n, m;
		cin >> n >> m;
		vi a(n);
		vi b(m);
		for(int i=0; i < n; ++i) a[i] = read_ll();
		for(int i=0; i < m; ++i) b[i] = read_ll();
		vector<bool> ai(n, true);
		vector<bool> bi(m, true);
		solve(a, b, ai, bi);
		int as = 0;
		int bs = 0;
		for(int i=0; i < n; ++i) {
			if(ai[i]) as++;
		}
		for(int i=0; i < m; ++i) {
			if(bi[i]) bs++;
		}
		if(as == 0 || bs == 0) cout << "NO" << endl;
		else {
			cout << "YES" << endl;
			cout << as << " " << bs << endl;
			for(int i=0; i < n; ++i) {
				if(ai[i]) {
					print_ll(a[i]);
					cout << " ";
				}
			}
			cout << endl;
			for(int i=0; i < m; ++i) {
				if(bi[i]) {
					print_ll(b[i]);
					cout << " ";
				}
			}
			cout << endl;
			
 
		}
	}
}

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

struct graph {
	int n;
	int m;

	vvi al;
	vi morphism;

	vvi dfs_children;
	vi dfs_parent;
	vi dfs_num;
	vi dfs_low;
	int dfs_count;

	bool is_root_ac = false;

	bool bad_biccon = false;
	vii repr_edge;

	void dt_dfs(int v, int par) {
		dfs_parent[v] = par;
		dfs_num[v] = dfs_low[v] = dfs_count++;
		for(int u : al[v]) {
			if(u == par) {
				//Nothing
			}
			else if(dfs_num[u] == -1) {
				dfs_children[v].push_back(u);
				dt_dfs(u, v);
				dfs_low[v] = min(dfs_low[v], dfs_low[u]);
			}
			else {
				dfs_low[v] = min(dfs_low[v], dfs_num[u]);
			}
		}
	}

	ii min_repr_edge(ii a, ii b) {
		if(a.first == -1) return b;
		if(b.first == -1) return a;
		if(dfs_num[a.second] < dfs_num[b.second]) return a;
		if(dfs_num[a.second] > dfs_num[b.second]) return b;
		if(dfs_num[a.first] > dfs_num[b.first]) return a;
		if(dfs_num[a.first] < dfs_num[b.first]) return b;
		return a;
	}

	void dt_dfs_hamil(int v) {
		repr_edge[v] = ii(-1, -1);

		for(int u : dfs_children[v]) {
			dt_dfs_hamil(u);
			repr_edge[v] = min_repr_edge(repr_edge[v], repr_edge[u]);
		}

		for(int u : al[v]) {
			if(u == dfs_parent[v]) {
				//Nothing
			}
			else if(dfs_num[u] < dfs_num[v]) {
				repr_edge[v] = min_repr_edge(repr_edge[v], ii(v, u));
			}

		}

		if(dfs_parent[v] == -1) {
			//Root case
			
			//Nothing more to check, repr_edge will always be set correctly.
		}
		else {
			if(dfs_children[v].size() == 0) {
				//Nothing to check
			}
			else if(dfs_children[v].size() == 1) {
				//Lemma 4
				if(dfs_low[dfs_children[v][0]] != dfs_low[v] && dfs_low[dfs_children[v][0]] != dfs_num[dfs_parent[v]]) {
					bad_biccon = true;
				}
			}
			else if(dfs_children[v].size() == 2) {
				//Lemma 3
				if(dfs_parent[dfs_parent[v]] != -1) {
					if(!((dfs_low[dfs_children[v][0]] == dfs_num[dfs_parent[v]]) ^ (dfs_low[dfs_children[v][1]] == dfs_num[dfs_parent[v]]))) {
						bad_biccon = true;
					}
				}
				if(dfs_low[v] < min(dfs_low[dfs_children[v][0]], dfs_low[dfs_children[v][1]])) {
					bad_biccon = true;
				}
			}
			else {
				bad_biccon = true;
			}
		}
	}

	void dt_dfs_cedges(vvii& cedges, vii& edge_stack, int v, int par) {
		dfs_parent[v] = par;
		dfs_num[v] = dfs_low[v] = dfs_count++;
		for(int u : al[v]) {
			if(u == par) {
				//Nothing
			}
			else if(dfs_num[u] == -1) {
				dfs_children[v].push_back(u);
				edge_stack.emplace_back(v, u);
				dt_dfs_cedges(cedges, edge_stack, u, v);
				dfs_low[v] = min(dfs_low[v], dfs_low[u]);

				if((par == -1 && is_root_ac) || (par != -1 && dfs_low[u] >= dfs_num[v])) {
					vii comp;
					while(edge_stack.back().first != v || edge_stack.back().second != u) {
						comp.push_back(edge_stack.back());
						edge_stack.pop_back();
					}
					comp.push_back(edge_stack.back());
					edge_stack.pop_back();
					cedges.push_back(comp);
				}
			}
			else {
				dfs_low[v] = min(dfs_low[v], dfs_num[u]);
				if(dfs_num[u] < dfs_num[v]) {
					edge_stack.emplace_back(v, u);
				}
			}
		}
	}

	void generate_dfs_tree(int root) {
		dfs_children = vvi(n, vi());
		dfs_parent = vi(n);
		dfs_count = 0;
		dfs_num = vi(n, -1);
		dfs_low = vi(n, -1);
		dt_dfs(root, -1);
	}

	void generate_edge_partition(vvii& cedges, vii& edge_stack, int root) {
		generate_dfs_tree(root);
		is_root_ac = (dfs_children[root].size() > 1);

		dfs_children = vvi(n, vi());
		dfs_parent = vi(n);
		dfs_count = 0;
		dfs_num = vi(n, -1);
		dfs_low = vi(n, -1);
		dt_dfs_cedges(cedges, edge_stack, root, -1);
		if(!edge_stack.empty()) cedges.push_back(edge_stack);
	}

	void generate_hamil_dfs_tree(int root) {
		generate_dfs_tree(root);
		repr_edge = vii(n, ii());
		dt_dfs_hamil(root);
	}
};

vector<graph> partition_biconnected(graph& g) {
	vvii cedges;
	vii edge_stack;
	g.generate_edge_partition(cedges, edge_stack, 0);
	vector<graph> comp;
	for(vii& vec : cedges) {
		graph h;
		h.n = 0;
		h.m = vec.size();
		unordered_map<int, int> rmorph;
		for(ii e : vec) {
			if(rmorph.find(e.first) == rmorph.end()) {
				rmorph[e.first] = h.n++;
			}
			if(rmorph.find(e.second) == rmorph.end()) {
				rmorph[e.second] = h.n++;
			}
		}
		h.morphism = vi(h.n);
		h.al = vvi(h.n);
		for(ii e : vec) {
			int u = rmorph[e.first];
			int v = rmorph[e.second];
			h.morphism[u] = g.morphism[e.first];
			h.morphism[v] = g.morphism[e.second];
			h.al[u].push_back(v);
			h.al[v].push_back(u);
		}
		comp.push_back(h);
	}
	return comp;
}

void upwards_path(graph& g, vi& hc, int v, int tar);

void downwards_path(graph& g, vi& hc, int v, int tar);

void upwards_path(graph& g, vi& hc, int v, int tar) {
	if(g.dfs_children[v].size() == 2) {
		int u1 = g.dfs_children[v][0];
		int u2 = g.dfs_children[v][1];
		if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2);
		hc.push_back(v);
		downwards_path(g, hc, u1, g.repr_edge[u1].first);
		if(v != tar) { 
			upwards_path(g, hc, g.dfs_parent[v], tar);
		}
	}
	else if(g.dfs_children[v].size() == 1) {
		int u = g.dfs_children[v][0];
		hc.push_back(v);
		if(g.repr_edge[u] != g.repr_edge[v]) {
			downwards_path(g, hc, u, g.repr_edge[u].first);
		}
		if(v != tar) {
			upwards_path(g, hc, g.dfs_parent[v], tar);
		}
	}
	else {
		hc.push_back(v);
		if(v != tar) {
			upwards_path(g, hc, g.dfs_parent[v], tar);
		}
	}
}

void downwards_path(graph& g, vi& hc, int v, int tar) {
	if(g.dfs_children[v].size() == 2) {
		int u1 = g.dfs_children[v][0];
		int u2 = g.dfs_children[v][1];
		if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2);
		upwards_path(g, hc, g.repr_edge[u1].first, u1);
		hc.push_back(v);
		downwards_path(g, hc, u2, tar);
	}
	else if(g.dfs_children[v].size() == 1) {
		int u = g.dfs_children[v][0];
		if(v == tar) {
			upwards_path(g, hc, g.repr_edge[u].first, u);
			hc.push_back(v);
		}
		else {
			hc.push_back(v);
			downwards_path(g, hc, u, tar);
		}
	}
	else {
		hc.push_back(v);
	}
}

vi hamiltonian_cycle(graph& g) {
	g.generate_hamil_dfs_tree(0);
	if(g.bad_biccon) return vi();
	vi hc;
	downwards_path(g, hc, 0, g.repr_edge[0].first);
	assert((int)hc.size() == g.n);
	return hc;
}

int comp_index;
bool cyclic_comparator(int a, int b) {
	if(a < comp_index) a += 1e7;
	if(b < comp_index) b += 1e7;
	return a < b;
}

graph sort_graph(const graph& g, const vi& hc) {
	graph h;
	h.n = g.n;
	h.m = g.m;
	h.morphism = vi(g.n);
	h.al = vvi(g.n);
	vi rhc(g.n);
	for(int i=0; i < g.n; ++i) {
		h.morphism[i] = g.morphism[hc[i]];
		rhc[hc[i]] = i;
	}
	for(int i=0; i < g.n; ++i) {
		for(int j : g.al[hc[i]]) {
			h.al[i].push_back(rhc[j]);
		}
		comp_index = i;
		//This is m log m, can be improved
		sort(h.al[i].begin(), h.al[i].end(), cyclic_comparator);
	}
	return h;
}

bool has_crossing(const graph& g) {
	vii bad_stack;
	for(int i=0; i < g.n; ++i) {
		comp_index = i;
		while(!bad_stack.empty() && i == bad_stack.back().first) bad_stack.pop_back();
		for(int j=(int)g.al[i].size()-2; j > 0; --j) {
			int u = g.al[i][j];
			if(!bad_stack.empty() && cyclic_comparator(bad_stack.back().first, u) && cyclic_comparator(u, bad_stack.back().second)) {
				return true;
			}
			if(u > i && (bad_stack.empty() || u != bad_stack.back().first)) {
				bad_stack.emplace_back(u, i);
			}
		}
	}
	return false;
}

void merge_ans(const graph& g, vvi& ans) {
	for(int i=0; i < g.n; ++i) {
		for(int j : g.al[i]) {
			ans[g.morphism[i]].push_back(g.morphism[j]);
		}
	}
}

void merge_single_edge_ans(const graph& g, vvi& ans) {
	int u = g.morphism[0];
	int v = g.morphism[1];
	ans[u].push_back(v);
	ans[v].push_back(u);
}

vvi solve(graph& input_graph) {
	vvi ans(input_graph.n);
	vector<graph> components = partition_biconnected(input_graph);
	for(graph g : components) {
		if(g.n == 1) {
			//Nothing
		}
		else if(g.n == 2) {
			merge_single_edge_ans(g, ans);
		}
		else {
			vi hc = hamiltonian_cycle(g);
			if(hc.empty()) {
				return vvi();
			}
			graph g2 = sort_graph(g, hc);
			if(has_crossing(g2))  return vvi();
			merge_ans(g2, ans);
		}
	}	
	return ans;
}

graph read_graph() {
	graph g;
	int n, m;
	cin >> n >> m;
	g.n = n;
	g.m = m;
	g.al = vvi(n, vi());
	g.morphism = vi(n, 0);
	for(int i=0; i < n; ++i) {
		g.morphism[i] = i;
	}
	for(int i=0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		g.al[u].push_back(v);
		g.al[v].push_back(u);
	}
	return g;
}

void print_ans(const vvi& ans) {
	int n = ans.size();
	if(n == 0) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
		for(int i=0; i < n; ++i) {
			for(int x : ans[i]) {
				cout << x << " ";
			}
			cout << endl;
		}
	}
}

int main() {
	int T;
	cin >> T;
	while(T--) {
		graph input_graph = read_graph();
		vvi ans = solve(input_graph);
		print_ans(ans);
	}
}