#include<bits/stdc++.h>

using namespace std;
int n,C;
int p[200005];
int val[200005];
// unordered_map<int,int>id;
bool pd[200005];
int last[200005];
vector<pair<int,int> >lans;
int read(){
    int x=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c-'0'),c=getchar();
    return x;
}
int id1[200005],id2[200005];
bool cmp(int x,int y){
    return p[x]<p[y];
}
bool cmpp(int x,int y){
    return val[x]<val[y];
}
void Solve(){
    // scanf("%d%d",&n,&C);
    n=read();C=read();
    lans.clear();
    for(int i=1;i<=n;i++){
        // scanf("%d%d",&p[i],&val[i]);
        p[i]=read();val[i]=read();
        pd[i]=false;
        id1[i]=id2[i]=i;
    }
    sort(id1+1,id1+1+n,cmp);
    sort(id2+1,id2+1+n,cmpp);
    for(int i=1;i<=n;i++)p[id1[i]]=id2[i];
    long long sum=0,ans=1ll*C*n;
    for(int i=1;i<=n;i++)sum+=abs(val[i]-val[p[i]]);
    for(int i=1;i<=n;i++){
        if(!pd[i]){
            int x=i,y=i,sav;
            while(!pd[x]){
                if(val[x]<val[y])y=x;
                pd[x]=true;
                x=p[x];
            }
            x=p[y];sav=y;
            stack<int>st;ans-=C;
            st.push(y);
            while(x!=y){
                if(val[x]>val[y])st.push(x);
                else {
                    int fi=0;vector<int>dl;
                    while(!st.empty()&&val[st.top()]>val[x]){
                        fi=st.top();dl.push_back(fi);
                        st.pop();
                    }
                    lans.push_back({st.top(),y});
                    for(int j=dl.size()-1;j>=1;j--)lans.push_back({dl[j],y});
                    if(x==sav)break;
                    st.push(x);
                }
                y=x;x=p[x];
            }
        }
    }
    printf("%lld %d\n",sum/2+ans,(int)lans.size());
    for(auto [x,y]:lans)printf("%d %d\n",x,y);
}
int main(){
    int T;
    T=read();
    while(T--)Solve();
    return 0;
}