Codeforces Round #624 (Div. 3) B - WeirdSort

B - WeirdSort

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa of length nn.

You are also given a set of distinct positions p1,p2,…,pmp1,p2,…,pm, where 1≤pi<n1≤pi<n. The position pipi means that you can swap elements a[pi]a[pi] and a[pi+1]a[pi+1]. You can apply this operation any number of times for each of the given positions.

Your task is to determine if it is possible to sort the initial array in non-decreasing order (a1≤a2≤⋯≤ana1≤a2≤⋯≤an) using only allowed swaps.

For example, if a=[3,2,1]a=[3,2,1] and p=[1,2]p=[1,2], then we can first swap elements a[2]a[2] and a[3]a[3] (because position 22 is contained in the given set pp). We get the array a=[3,1,2]a=[3,1,2]. Then we swap a[1]a[1] and a[2]a[2] (position 11 is also contained in pp). We get the array a=[1,3,2]a=[1,3,2]. Finally, we swap a[2]a[2] and a[3]a[3] again and get the array a=[1,2,3]a=[1,2,3], sorted in non-decreasing order.

You can see that if a=[4,1,2,3]a=[4,1,2,3] and p=[3,2]p=[3,2] then you cannot sort the array.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

Then tt test cases follow. The first line of each test case contains two integers nn and mm (1≤m<n≤1001≤m<n≤100) — the number of elements in aa and the number of elements in pp. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100). The third line of the test case contains mm integers p1,p2,…,pmp1,p2,…,pm (1≤pi<n1≤pi<n, all pipi are distinct) — the set of positions described in the problem statement.

Output

For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order (a1≤a2≤⋯≤ana1≤a2≤⋯≤an) using only allowed swaps. Otherwise, print "NO".

Example

input

6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4

output

YES
NO
YES
YES
NO
YES

此题有很多做法，我用的是并查集，其实也可以用冒泡排序的思想来做，最后再检查是否有序即可

并查集的思路也很简单就是题目给的可交换的下标都可以合在一起，然后去检查排好序之后的下标和原先的下标是不是在一个集合内就ok了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x]+=val;x+=lb(x);}}//第x个加上val
struct node
{
    ll val,pos;
}p[105];
inline bool cmp(const node&a,const node&b)
{
    if(a.val==b.val)return a.pos<b.pos;
    return a.val<b.val;
}
ll t,f[105],q[105];
inline void init(ll m)
{
    memset(f,0,sizeof(f));
    for(rg i=1;i<=100;i++)f[i]=i;
}
inline ll fa(ll x)
{
    return f[x]==x?x:f[x]=fa(f[x]);
}
inline void merge(ll x,ll y)
{
    ll fx=fa(x),fy=fa(y);
    if(fx!=fy)
    {
        f[fy]=fx;
    }
}
int main()
{
	cin>>t;
    for(rg i=1;i<=t;i++)
    {
        ll n,m,sum=0;
        cin>>n>>m;
        init(m);
        for(rg i=1;i<=n;i++)cin>>p[i].val,p[i].pos=i;
        for(rg j=1;j<=m;j++)cin>>q[j],merge(q[j],q[j]+1);
        sort(p+1,p+1+n,cmp);
        for(rg j=1;j<=n;j++)
        {
            if(fa(p[j].pos)==fa(j))
            {
                sum++;
            }
        }
        sum==n?cout<<"YES"<<endl:cout<<"NO"<<endl;
    }
    while(1)getchar();
    return 0;
    
}
/*
3 2 1
1 2
*/