//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
mt19937_64 rng(20210448);
int p[200200],inv[200200];
int vis[200200];
int ls[200200],rs[200200],fa[200200],siz[200200],mn[200200],mx[200200];
ull prior[200200];
int A[200200],P[200200];
void pushup(int x)
{
	if(ls[x]) fa[ls[x]]=x;
	if(rs[x]) fa[rs[x]]=x;
	siz[x]=1+siz[ls[x]]+siz[rs[x]];
	mn[x]=mx[x]=x;
	if(ls[x])
	{
		if(P[mn[ls[x]]]<P[mn[x]]) mn[x]=mn[ls[x]];
		if(P[mx[ls[x]]]>P[mx[x]]) mx[x]=mx[ls[x]];
	}
	if(rs[x])
	{
		if(P[mn[rs[x]]]<P[mn[x]]) mn[x]=mn[rs[x]];
		if(P[mx[rs[x]]]>P[mx[x]]) mx[x]=mx[rs[x]];
	}
}
int getpos(int x)
{
	int res=siz[ls[x]]+1;
	while(fa[x]&&(x==ls[fa[x]]||x==rs[fa[x]]))
	{
		if(x==rs[fa[x]]) res+=1+siz[ls[fa[x]]];
		x=fa[x];
	}
	return res;
}
int getval(int x,int p)
{
	if(p<=siz[ls[x]]) return getval(ls[x],p);
	if(p==siz[ls[x]]+1) return x;
	return getval(rs[x],p-siz[ls[x]]-1);
}
int merge(int u,int v)
{
	if(!u||!v) return u+v;
	if(prior[u]>prior[v])
	{
		rs[u]=merge(rs[u],v);
		pushup(u);
		return u;
	}
	else
	{
		ls[v]=merge(u,ls[v]);
		pushup(v);
		return v;
	}
}
void split(int x,int s,int &a,int &b)
{
	if(!x)
	{
		a=b=0;
		return ;
	}
	if(siz[ls[x]]+1<=s)
	{
		a=x;
		split(rs[x],s-siz[ls[x]]-1,rs[a],b);
		pushup(a);
	}
	else
	{
		b=x;
		split(ls[x],s,a,ls[b]);
		pushup(b);
	}
}
int search(int x,int v)
{
	if(ls[x]&&P[mn[ls[x]]]<=P[v]) return search(ls[x],v);
	if(P[x]<=P[v]) return x;
	return search(rs[x],v);
}
void solve(int rt)
{
	if(siz[rt]==1) return ;
	int u=mn[rt];
	int v=mx[rt];
	int pos=getpos(u);
	int A,B;
	split(rt,pos,A,B);
	rt=merge(B,A);
	pos=getpos(v);
	split(rt,pos,A,B);
	int w=search(B,getval(A,1));
	rt=merge(A,B);
	pos=getpos(w);
	int x=getval(rt,pos-1);
	cout<<inv[u]<<" "<<inv[x]<<'\n';
	split(rt,pos-1,A,B);
	solve(A);
	solve(B);
}
map<int,int> Mp;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,c;
		cin>>n>>c;
		ll tot=0;
		Mp.clear();
		for(int i=1;i<=n;i++)
		{
			cin>>A[i]>>P[i];
			Mp[P[i]]=i;
		}
		for(int i=1;i<=n;i++)
		{
			vis[i]=0;
			inv[i]=i;
			p[i]=Mp[A[i]];
			tot+=abs(A[i]-P[i]);
		}
		tot/=2;
		tot+=1ll*n*c;
		for(int i=1;i<=n;i++)
		{
			fa[i]=ls[i]=rs[i];
			prior[i]=rng();
			mn[i]=mx[i]=i;
			siz[i]=1;
		}
		vector<int> vrt;
		int k=n;
		for(int i=1;i<=n;i++)
			if(!vis[i])
			{
				int rt=0;
				int p=i;
				while(!vis[p])
				{
					vis[p]=1;
					rt=merge(rt,p);
					p=::p[p];
				}
				vrt.pb(rt);
				k--;
				tot-=c;
			}
		cout<<tot<<" "<<k<<'\n';
		for(auto rt:vrt) solve(rt);
	}
	return 0;
}