//#define local
#ifndef local
#include "Alicelib.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
bool ck[1505][1505];
void Alice( int N, int M, int A[], int B[]){
int tol_nodes = N + ceil(log2(N)) * 2 + 1;
// first node in order to know n
// next log2(n) nodes for addition
// next nodes for getting permutation
if(N == 2 && !M){
InitG(tol_nodes - 1, 0);
return;
}
for(int i = 1; i <= ceil(log2(N)); i++){
for(int j = i + 1; j <= ceil(log2(N)); j++) ck[i][j] = 1;
for(int j = 2 * ceil(log2(N)) + 1; j <= 2 * ceil(log2(N)) + N; j++){
int a = i - ceil(log2(N)) - 1, b = j - 2 * ceil(log2(N)) - 1;
if(!(b & (1LL << a))){
ck[i][j] = 1;
// cout << "EDGE2 " << i << " " << j << "\n";
}
}
}
for(int i = ceil(log2(N)) + 1; i <= 2 * ceil(log2(N)); i++){
for(int j = 2 * ceil(log2(N)) + 1; j < tol_nodes; j++){
int a = i - 1 - ceil(log2(N)), b = j - 2 * ceil(log2(N)) - 1;
if(b & (1LL << a)){
ck[i][j] = 1;
// cout << "EDGE2 " << i << " " << j << "\n";
}
}
}
int maxi = -1;
for(int i = 2 * ceil(log2(N)); i >= ceil(log2(N)) + 1; i--){
int deg = 0;
for(int j = 1; j < tol_nodes; j++) deg += (ck[i][j] | ck[j][i]);
if(deg <= maxi && i <= 2 * ceil(log2(N))){
for(int j = 1; j <= (maxi - deg + 1); j++) ck[j][i] = 1;
deg += (maxi - deg + 1);
}
maxi = max(maxi, deg);
// cout << maxi << '\n';
}
for(int i = 0; i < M; i++){
if(A[i] > B[i]) swap(A[i], B[i]);
ck[A[i] + 2 * (int)ceil(log2(N)) + 1][B[i] + 2 * (int)ceil(log2(N)) + 1] = 1;
}
vector<ii> edges;
vector<int> degs(tol_nodes + 6);
for(int i = 1; i < tol_nodes; i++) ck[i][tol_nodes] = 1;
for(int i = 1; i <= 2 * ceil(log2(N)); i++) ck[i][tol_nodes + 1] = 1;
for(int i = tol_nodes + 2; i < tol_nodes + 5; i++) ck[tol_nodes][i] = 1;
for(int i = 1; i < tol_nodes + 5; i++){
for(int j = i + 1; j < tol_nodes + 5; j++){
if(ck[i][j]){
// cout << i << " " << j << "\n";
edges.pb({i, j});
degs[i]++, degs[j]++;
}
}
}
// for(int i = 1; i < tol_nodes + 5; i++) cout << "DEGS " << i << " " << degs[i] << "\n";
InitG(tol_nodes + 4, edges.size());
int pos = 0;
for(auto it : edges){
MakeG(pos, it.fi - 1, it.se - 1);
pos++;
}
}
#ifdef local
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif
//#define local
#ifndef local
#include "Boblib.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
//mt19937 rng(1);
vector<ii> deg;
bool ckk[1505][1505];
int which[N];
bool is[N];
bool cmp(ii a, ii b){
if(is[a.se] != is[b.se]) return is[a.se];
else if(a.fi != b.fi) return a.fi > b.fi;
else return a.se < b.se;
}
void Bob(int V, int U, int C[], int D[]){
//return;
int n;
for(int i = 0; i <= 3000; i++){
// cout << i << " " << V << "\n";
int temp = i + 2 * ceil(log2(i)) + 5;
if(temp == V){
n = i;
break;
}
}
// cout << n << "\n";
// return;
deg.resize(V);
if(n == 1){
InitMap(1, 0);
return;
}
else if(n == 2 && !U){
InitMap(2, 0);
return;
}
else if(n == 2){
InitMap(2, 1);
MakeMap(0, 1);
return;
}
for(int i = 0; i < V; i++) deg[i].se = i;
for(int i = 0; i < U; i++){
deg[C[i]].fi++;
deg[D[i]].fi++;
ckk[C[i]][D[i]] = ckk[D[i]][C[i]] = 1;
// cout << C[i] << " " << D[i] << "\n";
}
sort(deg.begin(), deg.end(), greater<ii>());
int temp = deg[0].se, temp2;
for(int i = 0; i < V; i++) if(i != temp && !ckk[i][temp]) temp2 = i;
// cout << temp << " " << temp2 << "\n";
vector<ii> deg2 = deg;
deg.clear();
for(int i = 0; i < V; i++){
if(deg2[i].se == temp || deg2[i].se == temp2) continue;
// cout << deg2[i].se << " " << ckk[deg2[i].se][temp2] << "\n";
if(ckk[deg2[i].se][temp2]) is[deg2[i].se] = 1;
deg.pb(deg2[i]);
}
sort(deg.begin(), deg.end(), cmp);
// first up: the nodes for addition (log2(n)) nodes
// second up: the nodes from (log2(n) - 1 to 0)
for(int i = ceil(log2(n)); i < 2 * ceil(log2(n)); i++){
for(int j = 2 * ceil(log2(n)); j < 2 * ceil(log2(n)) + n; j++){
// cout << deg[i].se << " " << deg[j].se << "\n";
if(ckk[deg[i].se][deg[j].se]){
// cout << "EDGE " << deg[i].se << " " << deg[j].se << "\n";
which[deg[j].se] += (1LL << (i - (int)ceil(log2(n))));
}
}
}
vector<ii> v;
for(int j = 2 * ceil(log2(n)); j < 2 * ceil(log2(n)) + n; j++){
for(int k = j + 1; k < 2 * ceil(log2(n)) + n; k++){
//cout << deg[j].se << " " << deg[k].se << " " << which[deg[j].se] << " " << which[deg[k].se] << "\n";
if(ckk[deg[j].se][deg[k].se]) v.pb({min(which[deg[j].se], which[deg[k].se]), max(which[deg[j].se], which[deg[k].se])});
}
}
//cout << n << " " << v.size() << "\n";
//for(int i = 0; i < n + 2 * ceil(log2(n)); i++) cout << "OK " << i << " " << which[i] << "\n";
InitMap(n, (int)v.size());
for(auto it : v) MakeMap(it.fi, it.se);
}
/*
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}*/
#ifdef local
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) process();
}
#endif
