public class Main {
    static ArrayList<Integer> [] verkko;
    static int [] vari;
    static boolean virhe;

    public static void varitys(int solmu, int edellisenVari){
        if (vari[solmu] == edellisenVari) return;
        if (vari[solmu] == 3-edellisenVari){
            virhe = false;
            return;
        }
        vari[solmu] = edellisenVari;
        for (int i = 0; i < verkko[solmu].size(); i++){
            varitys(verkko[solmu].get(i), 3-edellisenVari);
        }

    }

    public static boolean lahjajako(int n, int[] mista, int[] minne) {
        virhe = true;
        vari = new int[n+1];
        verkko = new ArrayList[n+1];
        for (int i = 1; i <= n; i++){
            verkko[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < mista.length; i++){
            verkko[mista[i]].add(minne[i]);
            verkko[minne[i]].add(mista[i]);

        }


            varitys(1,1);


        return virhe;
    }