Untitled

import java.io.*;

public class Main2 {
    public static int noOfDivaOneRoles = 0;
    public static int noOfDivaTwoRoles = 0;

    public static int d1Index = 0;
    public static int d2Index = 0;

    public static int superIndex = 1;
    public static int actorsUsed = 0; // Antal skådespelare som fått roller

    public static boolean localMinima = false;

    public static boolean swapMade = true;

    public static int iSwap = 0;
    public static int jSwap = 0;

    public static void main(String args[]) throws FileNotFoundException {

        InputStream is = new FileInputStream("testinput.txt");
        // Kattio io = new Kattio(System.in, System.out);
        Kattio io = new Kattio(is, System.out);

        int n = io.getInt(); // Antal roller i problemet.
        int s = io.getInt(); // Antal scener i problemet.
        int k = io.getInt(); // Antal skådespelare i problemet.

        int rolesActors[][] = new int[n][k + 1];
        int scenesRoles[][] = new int[s][n + 1];
        int rolePartners[][] = new int[n + 1][(n * n) + 1];
        int divaOneRoles[] = new int[n];
        int divaTwoRoles[] = new int[n];

        int usedActors[] = new int[n];
        int sol[][] = new int[n * k + 2][n + 2]; // Lösningsarray.

        // Initialize number of roles to 0.
        for (int i = 0; i < n + 1; i++) {
            rolePartners[i][0] = 0;
        }

        // Fyll 2d array med alla roller och vilka skådisar som kan spela respektive
        // roll.
        int available = 0;
        for (int i = 0; i < n; i++) {
            available = io.getInt();
            rolesActors[i][0] = available;
            // System.out.print("roleActors[" + i + "][0]: " + rolesActors[i][0] + " ");
            for (int j = 1; j <= available; j++) {
                rolesActors[i][j] = io.getInt();
                // System.out.print("roleActors[" + i + "][" + j + "]: " + rolesActors[i][j] + "
                // ");
                if (rolesActors[i][j] == 1) {
                    divaOneRoles[noOfDivaOneRoles] = i + 1;
                    noOfDivaOneRoles++;
                } else if (rolesActors[i][j] == 2) {
                    divaTwoRoles[noOfDivaTwoRoles] = i + 1;
                    noOfDivaTwoRoles++;
                }
            }
        }
        // Fyll 2d array med alla scener och vilka roller som är i respektive scen.
        for (int i = 0; i < s; i++) {
            int incr = 0;
            available = io.getInt();
            scenesRoles[i][0] = available;
            for (int j = 1; j <= available; j++) {
                scenesRoles[i][j] = io.getInt();
            }
            for (int p = 1; p <= scenesRoles[i][0]; p++) {
                for (int e = 1; e <= scenesRoles[i][0]; e++) {
                    rolePartners[scenesRoles[i][p]][0] += 1;
                    incr = rolePartners[scenesRoles[i][p]][0];
                    rolePartners[scenesRoles[i][p]][incr] = scenesRoles[i][e];

                }
            }
        }

        int d1d2[] = new int[2];

        d1d2 = getDivas(divaOneRoles, divaTwoRoles);

        // This could go bad if no solution exists but we naively
        // do it this way because the lab says there always is a solution
        while (checkRoleScenes(d1d2, rolePartners)) {
            d1d2 = getDivas(divaOneRoles, divaTwoRoles);
        }
        sol = insertActor(d1d2[0], 1, sol);
        sol = insertActor(d1d2[1], 2, sol);
        usedActors[0] = 1;
        usedActors[1] = 2;
        int usedIndex = 2;
        actorsUsed += 2;
        int superActor = k + 1;
        int[] r1r2 = new int[2];
        boolean found = false;
        boolean roleCheck = true;
        // Create starting graph. --- HÄRIFRÅN ÄR DET RELEVANT, och variablerna ovan.
        for (int i = 0; i < n; i++) {
            if (d1d2[0] == i + 1 || d1d2[1] == i + 1) {
                continue;
            }
            for (int j = 1; j <= rolesActors[i][0]; j++) {
                if (rolesActors[i][j] == 1 || rolesActors[i][j] == 2) {
                    continue;
                }
                if (!checkTaken(rolesActors[i][j], usedActors)) {
                    usedActors[usedIndex] = rolesActors[i][j];
                    sol = insertActor(i + 1, rolesActors[i][j], sol);
                    actorsUsed++;
                    usedIndex++;
                    found = true;
                    break;
                } else {
                    for (int m = 0; m < sol[rolesActors[i][j]][1]; m++) {
                        r1r2[0] = i + 1;
                        r1r2[1] = sol[rolesActors[i][j]][m + 2];
                        roleCheck = checkRoleScenes(r1r2, rolePartners);
                        if (roleCheck) {
                            break;
                        }
                    }
                    if (!roleCheck) {
                        sol = insertActor(i + 1, rolesActors[i][j], sol);
                        found = true;
                        roleCheck = true;
                        break;
                    }
                }
            }
            if (!found) {
                sol = insertActor(i + 1, superActor, sol);
                superActor++;
                actorsUsed++;
            }
            found = false;
        }
        // ------------------FRAM TILLS HIT, IGNORERA RESTEN
        System.out.println(actorsUsed);
        printSol(sol);

        io.close();

    }

    private static boolean checkRolePossible(int actor, int role, int[][] ra) {
        for (int i = 1; i < ra[role - 1].length; i++) {
            if (ra[role - 1][i] == actor) {
                return true;
            }
        }
        return false;
    }

    private static void printSol(int[][] sol) {
        boolean nullRow = false;
        for (int i = 0; i < sol.length; i++) {
            if (sol[i][0] == 0) {
                continue;
            }
            for (int j = 0; j < sol[i].length; j++) {
                if (sol[i][j] == 0) {
                    break;
                }
                System.out.print(sol[i][j] + " ");
            }
            System.out.println("");
        }
    }

    private static int[][] insertActor(int role, int actor, int[][] sol) {
        sol[actor][0] = actor;
        sol[actor][1] += 1;
        sol[actor][sol[actor][1] + 1] = role;
        return sol;
    }

    private static boolean checkTaken(int actor, int[] usedActors) {
        for (int i = 0; i < usedActors.length; i++) {
            if (usedActors[i] == actor) {
                return true;
            }
        }
        return false;
    }

    private static boolean checkRoleScenes(int[] r1r2, int[][] rolePartners) {
        int max = 0;
        int role = 0;
        int role2 = 0;
        if (rolePartners[r1r2[0]][0] > rolePartners[r1r2[1]][0]) {
            max = rolePartners[r1r2[1]][0];
            role = r1r2[1];
            role2 = r1r2[0];
        } else {
            max = rolePartners[r1r2[0]][0];
            role = r1r2[0];
            role2 = r1r2[1];
        }
        for (int i = 1; i <= max; i++) {
            if (rolePartners[role][i] == role2) {
                return true;
            }
            if (rolePartners[role][i] == 0) {
                return false;
            }
        }
        return false;
    }

    private static int[] getDivas(int[] d1r, int[] d2r) {
        int[] d1d2 = new int[2];
        for (int i = d1Index; i < noOfDivaOneRoles; i++) {
            for (int j = d2Index; j < noOfDivaTwoRoles; j++) {
                if (d1r[i] != d2r[j]) {
                    d1d2[0] = d1r[i];
                    d1d2[1] = d2r[j];
                    d2Index++;
                    return d1d2;
                }
                d2Index++;
            }
            d2Index = 0;
            d1Index++;
        }
        return d1d2;

    }
}