Main Idea: Instead of directly comparing permutations,I transformed each permutation and required permutation into a number that allows prefix matching efficiently.After doing i just have to find the permutation which is nearest to reruired permutation .

Complexity: O(n * m * log n)

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int BASE = 11;

/*
    Find how many digits are different
    from the back while comparing hashes
*/
int common(int x,int y){

    int cnt=0;

    while(x!=y){
        x/=BASE;
        y/=BASE;
        cnt++;
    }

    return cnt;
}

/*
    Binary search the closest hash
    and return minimum mismatch count
*/
int best(int n,vector<int> &a,int m){

    int st=0,end=a.size()-1;

    while(st<=end){

        int mid=(st+end)/2;

        if(a[mid]<=n){
            st=mid+1;
        }
        else{
            end=mid-1;
        }
    }

    int ans=m;

    // check upper bound candidate
    if(st<a.size()){
        ans=min(ans,common(n,a[st]));
    }

    // check lower bound candidate
    if(end>=0){
        ans=min(ans,common(n,a[end]));
    }

    return ans;
}

int32_t main() {

    int t;
    cin>>t;

    while(t--){

        int n,m;
        cin>>n>>m;

        vector<int> equ(n),req(n);

        for(int i=0;i<n;i++){

            vector<int> a(m);

            for(int j=0;j<m;j++){
                cin>>a[j];
                a[j]--;
            }

            /*
                temp  -> original permutation hash
                treq  -> inverse permutation hash
            */

            int temp=0,treq=0;

            // create original permutation hash
            for(int j=0;j<m;j++){
                temp=temp*BASE+a[j];
            }

            // build inverse permutation
            vector<int> pos(m);

            for(int j=0;j<m;j++){
                pos[a[j]]=j;
            }

            // create inverse permutation hash
            for(int j=0;j<m;j++){
                treq=treq*BASE+pos[j];
            }

            req[i]=temp;
            equ[i]=treq;
        }

        // sort inverse hashes for binary search
        sort(equ.begin(),equ.end());

        vector<int> ans(n);

        for(int i=0;i<n;i++){

            int cnt=best(req[i],equ,m);

            // matched prefix length
            ans[i]=m-cnt;
        }

        for(int i=0;i<n;i++){
            cout<<ans[i]<<" ";
        }

        cout<<endl;
    }
}

374473747