CF1481C Fence Painting

Fence Painting - Luogu

Title Description

You finally woke up after this crazy dream and decided to walk around to clear your head. Outside you saw your house's fence — so plain and boring, that you'd like to repaint it.

You have a fence consisting of nn planks, where the ii -th plank has the color a_iai​ . You want to repaint the fence in such a way that the ii -th plank has the color b_ibi​ .

You've invited mm painters for this purpose. The jj -th painter will arrive at the moment jj and will recolor exactly one plank to color c_jcj​ . For each painter you can choose which plank to recolor, but you can't turn them down, i. e. each painter has to color exactly one plank.

Can you get the coloring bb you want? If it's possible, print for each painter which plank he must paint.

Input format

The first line contains one integer tt ( 1 \le t \le 10^41≤t≤104 ) — the number of test cases. Then tt test cases follow.

The first line of each test case contains two integers nn and mm ( 1 \le n, m \le 10^51≤n,m≤105 ) — the number of planks in the fence and the number of painters.

The second line of each test case contains nn integers a_1, a_2, \dots, a_na1​,a2​,…,an​ ( 1 \le a_i \le n1≤ai​≤n ) — the initial colors of the fence.

The third line of each test case contains nn integers b_1, b_2, \dots, b_nb1​,b2​,…,bn​ ( 1 \le b_i \le n1≤bi​≤n ) — the desired colors of the fence.

The fourth line of each test case contains mm integers c_1, c_2, \dots, c_mc1​,c2​,…,cm​ ( 1 \le c_j \le n1≤cj​≤n ) — the colors painters have.

It's guaranteed that the sum of nn doesn't exceed 10^5105 and the sum of mm doesn't exceed 10^5105 over all test cases.

Output format

For each test case, output "NO" if it is impossible to achieve the coloring bb .

Otherwise, print "YES" and mm integers x_1, x_2, \dots, x_mx1​,x2​,…,xm​ , where x_jxj​ is the index of plank the jj -th painter should paint.

You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" are all recognized as positive answer).

  Each carpenter must paint a piece and paint it in the order that it comes .

For every board , We just need to traverse the carpenter upside down , To find out what makes ai become bi Of ci, about ai==bi You can not think about it first , This is to make more ai!=bi Have the opportunity to turn into bi, It's a greedy thought .

In the process of traversal , We marked the carpenter

00000id10000id20000id3 Like this, , In the first to mark id1 The carpenter of , Full coating id1 Wooden board , apply id1 Then come to Tu id2 The carpenter of , Full coating id2 Wooden board , This avoids the confusion caused by graffiti . Anyway, in the end, we will become id, Then it doesn't matter what you painted before .

This is not enough , Case one , All ai==bi, But we must also use every carpenter , And there is no chance to change after the last carpenter runs out , That is, the last carpenter must have a corresponding bi, We found this bi Where i, that 1-m A carpenter painted it all i Just OK 了 , Otherwise, there is no solution

The second case , We searched and searched , Find out ai!=bi When , We can't find one that hasn't been marked anymore ci==bi, This is no solution

The third case , It's also a pit , That is according to the particularity of the last carpenter （ Can't change ） That is to say, we need to judge whether the last carpenter has been marked , without , Look for any one bi==c[m] that will do , Otherwise, there is no solution

The fourth situation , All's well that ends well , Just simulate according to our original idea

# include<iostream>
# include<set>
# include<algorithm>
# include<cstring>

using namespace std;

typedef long long int ll;

int a[100000+10],b[100000+10];
int c[100000+10];
int id[100000+10];

int main ()
{

    // Look backwards   , Find the first bi

    //


    int t;

    cin>>t;

    while(t--)
    {
        int n,m;

        cin>>n>>m;

        memset(id,0,sizeof(id));


        for(int i=1; i<=n; i++)
        {
            cin>>a[i];

        }
        for(int i=1; i<=n; i++)
        {
            cin>>b[i];

        }

        for(int i=1; i<=m; i++)
        {
            cin>>c[i];

        }
        int flag=0;

        int check=0;


        for(int i=1; i<=n; i++)
        {
            if(a[i]==b[i])
                continue;

            flag=1;

            check=0;

            for(int j=m; j>=1; j--)
            {
                if(id[j]==0&&c[j]==b[i])
                {
                    id[j]=i;

                    check=1;

                    break;

                }
            }

            if(check==0)
            {

                flag=-1;

                break;

            }

        }

        if(flag==-1)
        {
            cout<<"No"<<'\n';

        }
        else if(flag==0)
        {
            flag=0;

            int ans=0;
            for(int i=1; i<=n; i++)
            {
                if(c[m]==b[i])
                {
                    flag=1;

                    ans=i;

                    break;

                }
            }

            if(!flag)
            {
                cout<<"No"<<'\n';

            }
            else
            {
                cout<<"YES"<<'\n';

                for(int i=1; i<=m; i++)
                {
                    cout<<ans<<" ";

                }

                cout<<'\n';

            }
        }
        else
        {

            if(id[m]==0)
            {

                for(int i=1; i<=n; i++)
                {
                    if(c[m]==b[i])
                    {

                        id[m]=i;

                        break;

                    }
                }

                if(id[m]==0)
                {
                    cout<<"No"<<endl;

                    continue;

                }
            }

            int pre=1;

            cout<<"YES"<<'\n';

            for(int i=1; i<=m; i++)
            {
                if(id[i])
                {
                    for(int j=pre; j<=i; j++)
                    {
                        cout<<id[i]<<" ";

                    }

                    pre=i+1;
                }
            }

            cout<<endl;
        }
    }

    return 0;

}