#include <stdio.h>
#include <malloc.h>

int main()
{
    int BrojVeza1(int* Veze, int n);
    int* Gradovi;
    int** VezeGradova;
    int n;

    scanf("%d", &n);

    Gradovi = (int*)calloc(n, sizeof(int));
    VezeGradova = (int**)calloc(n, sizeof(int*));
    for (int i = 0; i < n; ++i)
    {
        VezeGradova[i] = (int*)calloc(n - 1, sizeof(int));
    }

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &Gradovi[i]);
    }

    int* BrojVeza = (int**)calloc(n, sizeof(int*));

    for (int i = 0; i < n - 1; ++i)
    {
        int Grad, Veza;
        scanf("%d", &Grad);
        scanf("%d", &Veza);
        VezeGradova[Grad - 1][BrojVeza[Grad - 1]++] = Veza;
        VezeGradova[Veza - 1][BrojVeza[Veza - 1]++] = Grad;
    }

    int BrojOpcija;
    int BrojOpcija2 = 0;
    int* ResenjaOpcija2;

    scanf("%d", &BrojOpcija);

    ResenjaOpcija2 = (int*)calloc(BrojOpcija, sizeof(int));

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

        scanf("%d %d %d", &Opcija, &Pozicija1, &Pozicija2);

        if (Opcija == 1)
        {
            Opcija1(Gradovi, VezeGradova, n, Pozicija1, Pozicija2);
            for (int i = 0; i < n; ++i)
            {
                printf("%d\n", BrojVeza1(VezeGradova[i], n - 1));
                for (int j = 0; j <  BrojVeza1(VezeGradova[i], n - 1); ++j)
                {
                    printf("%d ", VezeGradova[i][j]);
                }
                printf("\n");
            }
        }
        else
        {
            int Grad;
            scanf("%d", &Grad);
            ResenjaOpcija2[BrojOpcija2++] = Opicja2(Gradovi, VezeGradova, n, Pozicija1, Pozicija2, Grad);
            printf("%d\n", ResenjaOpcija2[BrojOpcija2 - 1]);
        }
    }

    for (int i = 0; i < BrojOpcija2; ++i)
    {
        printf("%d\n", ResenjaOpcija2[i]);
    }
}

void Opcija1(int *Gradovi, int **VezeGradova, int n, int Pozicija1, int Pozicija2)
{
    int Grad1 = Gradovi[Pozicija1 - 1];
    int Grad2 = Gradovi[Pozicija2 - 1];

    int* VezeSmena = (int*)calloc(n, sizeof(int));

    for (int i = 0; i < n; ++i)
    {
        VezeSmena[i] = VezeGradova[Grad2 - 1][i];
        VezeGradova[Grad2 - 1][i] = VezeGradova[Grad1 - 1][i];
        VezeGradova[Grad1 - 1][i] = VezeSmena[i];
    }

    int Smena = Gradovi[Pozicija1 - 1];
    Gradovi[Pozicija1 - 1] = Gradovi[Pozicija2 - 1];
    Gradovi[Pozicija2 - 1] = Smena;
}

int Opicja2(int *Gradovi, int **VezeGradova, int n, int Opseg1, int Opseg2, int Grad)
{
    int NajduziPut = 0;
    int l = Opseg2 - Opseg1;

    for (int i = 0; i <= l; ++i)
    {
        int debbug = 0;
        int TrenutniPut = 0;
        int TrenutniGrad = Gradovi[i + Opseg1 - 1];
        int PocetniGrad = TrenutniGrad;
        int PrethodniGrad = 0;
        int RedniDeoGrane = 0;
        int* KoraciUGrani = (int*)calloc(n - 1, sizeof(int));
        int* GradUGrani = (int*)calloc(n - 1, sizeof(int));

        GradUGrani[0] = TrenutniGrad;

        for (int i = 0; TrenutniGrad != Grad; ++i)
        {
            TrenutniGrad = GradUGrani[i];
            int BrojV = BrojVeza1(VezeGradova[TrenutniGrad - 1]);

            for (int j = KoraciUGrani[i]; j < BrojV; ++j)
            {
                KoraciUGrani[i] = j;
                int PotencijalniGrad = VezeGradova[TrenutniGrad - 1][j];

                if (PotencijalniGrad == Grad)
                {
                    TrenutniGrad = PotencijalniGrad;
                    TrenutniPut = i;
                    break;
                }

                if (BrojVeza1(VezeGradova[PotencijalniGrad - 1], n - 1) == 1)
                {
                    continue;
                }

                if (PotencijalniGrad == 0)
                {
                    i -= 2;
                    break;
                }

                TrenutniGrad = PotencijalniGrad;
            }
        }

        if (TrenutniPut > NajduziPut)
        {
            NajduziPut = TrenutniPut;
        }

        free(KoraciUGrani);
        free(GradUGrani);
    }

    return NajduziPut;
}

int BrojVeza1(int* Veze, int n)
{
    for (int i = 0; i < n; ++i)
    {
        if (Veze[i] == 0)
        {
            return i;
        }
    }

    return n - 1;
}