reference:

Rabin-Karp and Knuth-Morris-Pratt Algorithms By TheLlama– TopCoder Member https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/

// to be improved

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAXN 1000005

#define MAXM 10005

int nums[MAXN];

int cnums[MAXM];

int ffunc[MAXM]={0};

int main() {

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif

    int T,n,m,i,j,k, res;

    int *p,*pend, *q, *r, *rend;

    if(scanf("%d",&T)!=1) return -1;

    while(T-->0 && scanf("%d%d",&n,&m)==2 && n>=m && m>0) {

        for(i=1;i<=n;++i) scanf("%d",&nums[i]);

        for(i=1;i<=m;++i) scanf("%d",&cnums[i]);

        for(i=2;i<=m;++i) {

            for(j=ffunc[i-1];;j=ffunc[j]) {

                if(cnums[j+1]==cnums[i] || j==0 && --j) break;

            }

            ffunc[i]=j+1;

        }

        for(i=1, k=0;;) {

            if(nums[i]==cnums[k+1]) { ++k; }

            else if(k>0) { k=ffunc[k]; continue; }

            if(++i>n || k>=m) break;

        }

        res=k!=m?-1:i-m;

        printf("%d\n",res);

    }

    return 0;

}