#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int INF = (int) 1e9;

struct PokrNode
{
	int min, cnt;
	nt upd;
};

pair <int, int> edge[250005];
PokrNode tree_pokr[1000005];
int tree_sosed[1000005];
set <pair <int, int> > strong;
int svyaz[250005];
ordered_set opa[600005];
int quant = 0;

void full_pokr(int v, int lef, int rig, int val)
{
 	tree_pokr[v].min += val;
 	tree_pokr[v].upd += val;
 	return;
}

void push_pokr(int v, int lef, int rig)
{
 	int mid = (lef + rig) / 2;
 	full_pokr(2 * v, lef, mid, tree_pokr[v].upd);
 	full_pokr(2 * v + 1, mid + 1, rig, tree_pokr[v].upd);
 	tree_pokr[v].upd = 0;
 	return;
}

void build_pokr(int v, int lef, int rig)
{
	if (lef == rig) {tree_pokr[v] = {INF, 1, 0}; return;}
	int mid = (lef + rig) / 2;
	build_pokr(2 * v, lef, mid);
	build_pokr(2 * v + 1, mid + 1, rig);
	tree_pokr[v] = {INF, rig - lef + 1, 0};
	return; 	
}

void update_pokr(int v, int lef, int rig, int A, int B, int val)
{
 	if (lef > B || rig < A) return;
 	if (A <= lef && rig <= B)
 	{
 	 	full_pokr(v, lef, rig, val);
 	 	return;
 	}
 	push_pokr(v, lef, rig);
 	int mid = (lef + rig) / 2;
 	update_pokr(2 * v, lef, mid, A, B, val);
 	update_pokr(2 * v + 1, mid + 1, rig, A, B, val);

 	tree_pokr[v].min = tree_pokr[2 * v].min, tree_pokr[v].cnt = tree_pokr[2 * v].cnt;
 	if (tree_pokr[2 * v + 1].min < tree_pokr[v].min) tree_pokr[v].min = tree_pokr[2 * v + 1].min, tree_pokr[v].cnt = tree_pokr[2 * v + 1].cnt;
 	else if (tree_pokr[2 * v + 1].min == tree_pokr[v].min) tree_pokr[v].cnt += tree_pokr[2 * v + 1].cnt;
 	return;
}

void update_pokr_point(int v, int lef, int rig, int pos, int val)
{
 	if (lef == rig) {tree_pokr[v] = {val, 1, 0}; return;}
 	push_pokr(v, lef, rig);
 	int mid = (lef + rig) / 2;
 	if (pos <= mid) update_pokr_point(2 * v, lef, mid, pos, val);
 	else update_pokr_point(2 * v + 1, mid + 1, rig, pos, val);

 	tree_pokr[v].min = tree_pokr[2 * v].min, tree_pokr[v].cnt = tree_pokr[2 * v].cnt;
 	if (tree_pokr[2 * v + 1].min < tree_pokr[v].min) tree_pokr[v].min = tree_pokr[2 * v + 1].min, tree_pokr[v].cnt = tree_pokr[2 * v + 1].cnt;
 	else if (tree_pokr[2 * v + 1].min == tree_pokr[v].min) tree_pokr[v].cnt += tree_pokr[2 * v + 1].cnt;
 	return;
}

void build_sosed(int v, int lef, int rig)
{
 	if (lef == rig) {tree_sosed[v] = 0; return;}
 	int mid = (lef + rig) / 2;
 	build_sosed(2 * v, lef, mid);
 	build_sosed(2 * v + 1, mid + 1, rig);
 	tree_sosed[v] = 0;
 	return;
}

void dfsik_sosed(int v, int lef, int rig, int bound, int A, int B, vector <int> &spis)
{
 	if (tree_sosed[v] > bound) return;
 	if (lef > B || rig < A) return;
 	if (lef == rig) {spis.pb(lef); return;}
 	int mid = (lef + rig) / 2;
 	dfsik_sosed(2 * v, lef, mid, bound, A, B, spis);
 	dfsik_sosed(2 * v + 1, mid + 1, rig, bound, A, B, spis);
 	return;
}

void update_sosed(int v, int lef, int rig, int pos, int val)
{
 	if (lef == rig) {tree_sosed[v] = val; return;}
 	int mid = (lef + rig) / 2;
 	if (pos <= mid) update_sosed(2 * v, lef, mid, pos, val);
 	else update_sosed(2 * v + 1, mid + 1, rig, pos, val);
 	tree_sosed[v] = min(tree_sosed[2 * v], tree_sosed[2 * v + 1]);
 	return;
}

void cut(int start, int lef, int rig, ll &sum_sizes, int n)
{
	//cout << "Cut: " << start << '\n';
	//for (int x : opa[svyaz[start]]) cout << x << ' ';
	//cout << "--------------\n";

	int num = svyaz[start];
	int sz = (int) opa[num].size();
	int kol = opa[num].order_of_key(rig) - opa[num].order_of_key(lef);
 	if (kol == sz) return;
 	
 	sum_sizes -= (ll) sz * (sz - 1) / 2;
 	//cout << "Cut2: " << start << '\n';
 	quant++;
 	opa[quant].clear();
 	sum_sizes += (ll) kol * (kol - 1) / 2;
 	sum_sizes += (ll) (sz - kol) * (sz - kol - 1) / 2;

 	auto it1 = opa[num].find(start);
 	auto it2 = opa[num].lower_bound(rig);
 	int pr = (it1 == opa[num].begin()) ? 0 : *prev(it1);
 	int nx = (it2 == opa[num].end()) ? n : *it2;
 	if (2 * kol >= sz)
 	{
 		for (auto it = opa[num].begin(); *it != start; it++)
 			opa[quant].insert(*it);
 	 	for (auto it = opa[num].lower_bound(rig); it != opa[num].end(); it++)
 	 		opa[quant].insert(*it);
 	}
 	else
 	{
 		auto startIt = opa[num].find(start);
 		auto finishIt = opa[num].lower_bound(rig);
 		for (auto it = startIt; it != finishIt; it++)
 			opa[quant].insert(*it);
 	}
 	update_sosed(1, 1, n - 1, start, 0);
 	if (nx != n) update_sosed(1, 1, n - 1, nx, pr);	
 	for (int x : opa[quant])
 	{
 	 	svyaz[x] = quant;
 	 	opa[num].erase(x);
 	}
 	return;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);

 	int test;
 	cin >> test;
 	for (int rep = 1; rep <= test; rep++)
 	{
 	 	int n, m;
 	 	cin >> n >> m;
 	 	for (int i = 1; i <= m; i++)
 	 	{
 	 		cin >> edge[i].x >> edge[i].y;
 	 		if (edge[i].x > edge[i].y) swap(edge[i].x, edge[i].y); 	
 	 	}

 	 	if (n == 1)
 	 	{
 	 	 	for (int i = 1; i <= m; i++) cout << "0\n";
 	 	 	continue;
 	 	}

 	 	int all_edges = n - 1, bridges = n - 1;
 	 	ll sum_sizes = 0;
 	 	
 	 	strong.clear();
 	 	for (int i = 1; i <= n; i++) strong.insert(mp(i, i));

 	 	quant = 0;

 	 	build_pokr(1, 1, n - 1);
 	 	build_sosed(1, 1, n - 1);

 	 	for (int i = 1; i <= m; i++)
 	 	{
 	 	 	int lef = edge[i].x, rig = edge[i].y;
 	 	 	all_edges++;
 	 	 	
 	 	 	if (lef != rig)
 	 	 	{
 	 	 		auto itlef = strong.lower_bound(mp(lef + 1, 0));
 	 	 		itlef--;
 	 	 		auto itrig = strong.lower_bound(mp(rig + 1, 0));

 	 	 		vector <pair <int, int> > spis;
 	 	 		for (auto it = itlef; it != itrig; it++)
 	 	 			spis.pb(*it);
 	 	 		if ((int) spis.size() != 1)
 	 	 		{
 	 	 			quant++;
 	 	 			opa[quant].clear();
 	 	 		}
 	 	 		for (int i = 1; i < (int) spis.size(); i++)
 	 	 		{
 	 	 			update_pokr_point(1, 1, n - 1, spis[i - 1].y, 0);
 	 	 			opa[quant].insert(spis[i - 1].y);
 	 	 			svyaz[spis[i - 1].y] = quant;
 	 	 			bridges--;
 	 	 		}
 	 	 		update_pokr(1, 1, n - 1, lef, rig - 1, 1);
 	 	 		if ((int) spis.size() != 1)
 	 	 		{
 	 	 		 	int last = 0;
 	 	 		 	for (int x : opa[quant])
 	 	 		 	{
 	 	 		 	 	update_sosed(1, 1, n - 1, x, last);
 	 	 		 	 	last = x;
 	 	 		 	}
 	 	 		 	sum_sizes += (ll) opa[quant].size() * ((ll) opa[quant].size() - 1) / 2;
 	 	 		}

 	 	 		int resL = spis[0].x, resR = spis.back().y;
 	 	 		for (int i = 0; i < (int) spis.size(); i++) strong.erase(spis[i]);
 	 	 		strong.insert(mp(resL, resR));

 	 	 		vector <int> starts;
 	 	 		dfsik_sosed(1, 1, n - 1, lef - 1, lef, rig - 1, starts);

 	 	 		for (int start : starts) cut(start, lef, rig, sum_sizes, n);
 	 	 	}

 	 	 	ll ans = (ll) bridges * (bridges - 1) / 2 + (ll) bridges * (all_edges - bridges);
 	 	 	int mn = tree_pokr[1].min, cnt = tree_pokr[1].cnt;
 	 	 	if (mn == 1) ans += cnt;
 	 	 	ans += sum_sizes;
 	 	 	//cout << all_edges << ' ' << bridges << ' ' << mn << ' ' << cnt << ' ' << sum_sizes << '\n';
 	 	 	cout << ans << '\n';
        }
 	}

 	return 0;
}

answer.code:21:9: error: ‘nt’ does not name a type; did you mean ‘int’?
   21 |         nt upd;
      |         ^~
      |         int
answer.code: In function ‘void full_pokr(int, int, int, int)’:
answer.code:35:22: error: ‘struct PokrNode’ has no member named ‘upd’
   35 |         tree_pokr[v].upd += val;
      |                      ^~~
answer.code: In function ‘void push_pokr(int, int, int)’:
answer.code:42:49: error: ‘struct PokrNode’ has no member named ‘upd’
   42 |         full_pokr(2 * v, lef, mid, tree_pokr[v].upd);
      |                                                 ^~~
answer.code:43:57: error: ‘struct PokrNode’ has no member named ‘upd’
   43 |         full_pokr(2 * v + 1, mid + 1, rig, tree_pokr[v].upd);
      |                                                         ^~~
answer.code:44:22: error: ‘struct PokrNode’ has no member named ‘upd’
   44 |         tree_pokr[v].upd = 0;
      |                      ^~~
answer.code: In function ‘void build_pokr(int, int, int)’:
answer.code:50:51: error: no match for ‘operator=’ (operand types are ‘PokrNode’ and ‘<brace-enclosed initializer list>’)
   50 |         if (lef == rig) {tree_pokr[v] = {INF, 1, 0}; return;}
      |                                                   ^
answer.code:18:8: note: candidate: ‘constexpr PokrNode& PokrNode::operator=(const PokrNode&)’
   18 | struct PokrNode
      |        ^~~~~~~~
answer.code:18:8: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const PokrNode&’
answer.code:18:8: note: candidate: ‘constexpr PokrNode& PokrNode::operator=(PokrNode&&)’
answer.code:18:8: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘PokrNode&&’
answer.code:54:46: error: no match for ‘operator=’ (operand types are ‘PokrNode’ and ‘<brace-enclosed initializer list>’)
   54 |         tree_pokr[v] = {INF, rig - lef + 1, 0};
      |                                              ^
answer.code:18:8: note: candidate: ‘constexpr PokrNode& PokrNode::operator=(const PokrNode&)’
   18 | struct PokrNode
      |        ^~~~~~~~
answer.code:18:8: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const PokrNode&’
answer.code:18:8: note: candidate: ‘constexpr PokrNode& PokrNode::operator=(PokrNode&&)’
answer.code:18:8: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘PokrNode&&’
answer.code: In function ‘void update_pokr_point(int, int, int, int, int)’:
answer.code:79:51: error: no match for ‘operator=’ (operand types are ‘PokrNode’ and ‘<brace-enclosed initializer list>’)
   79 |         if (lef == rig) {tree_pokr[v] = {val, 1, 0}; return;}
      |                                                   ^
answer.code:18:8: note: candidate: ‘constexpr PokrNode& PokrNode::operator=(const PokrNode&)’
   18 | struct PokrNode
      |        ^~~~~~~~
answer.code:18:8: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const PokrNode&’
answer.code:18:8: note: candidate: ‘constexpr PokrNode& PokrNode::operator=(PokrNode&&)’
answer.code:18:8: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘PokrNode&&’