Untitled

import java.io.*;

public class Main {
    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][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, 1, 0, sol);
        sol = insertActor(d1d2[1] - 1, 2, 1, sol);
        usedActors[0] = 1;
        usedActors[1] = 2;
        actorsUsed += 2;
        int roleIndex = 2;
        int superActor = k + 1;
        boolean found = false;
        // Create starting graph.
        for (int i = 0; i < n; i++) {
            if (d1d2[0] == i + 1 || d1d2[1] == i + 1) {
                continue;
            }
            for (int j = 1; j < rolesActors[i].length; j++) {
                if (!checkTaken(rolesActors[i][j], usedActors)) {
                    usedActors[roleIndex] = rolesActors[i][j];
                    actorsUsed++;
                    found = true;
                    sol = insertActor(i, rolesActors[i][j], roleIndex, sol);
                    break;
                }
            }
            if (!found) {
                usedActors[roleIndex] = superActor;
                sol = insertActor(i, superActor, roleIndex, sol);
                superActor++;
                actorsUsed++;
            }
            roleIndex++;
            found = false;
        }

        int i = 0;

        while (swapMade) {
            while (!localMinima && i != 150) {
                sol = optimizeLocal(sol, rolesActors, scenesRoles, d1d2, k, superActor, rolePartners);
                i++;
            }
            sol = swapTwoActors(sol, d1d2, k, n, rolePartners, rolesActors);
        }

        System.out.println(actorsUsed);
        printSol(sol);

        io.close();

    }

    private static int[][] optimizeLocal(int[][] sol, int[][] rolesActors, int[][] scenesRoles, int[] d1d2, int k,
            int superActor, int[][] rolePartners) {
        int[] r1r2 = new int[2];
        int localSuperIndex = superIndex;
        int rn = 0;
        boolean check = true;
        boolean localFlag = true;
        for (int i = 0; i < sol.length; i++) {
            if (sol[i][0] == 0) {
                continue;
            }
            if (sol[i][2] != d1d2[0] && sol[i][2] != d1d2[1]) {
                if (sol[i][0] > k) {
                    continue;
                }
                for (int j = 0; j < superActor; j++) {
                    rn = getSuper(sol, k);
                    if (rn == 0) {
                        continue;
                    }
                    r1r2[1] = sol[rn][2];
                    if (!checkRolePossible(sol[i][0], r1r2[1], rolesActors)) {
                        continue;
                    }

                    for (int e = 0; e < sol[i][1]; e++) {
                        r1r2[0] = sol[i][e + 2];
                        check = checkRoleScenes(r1r2, rolePartners);
                        if (check) {
                            break;
                        }
                    }

                    if (!check) {
                        sol[i][1] += 1;
                        sol[i][sol[i][1] + 1] = sol[rn][2];
                        sol[rn][0] = sol[rn][1] = sol[rn][2] = 0;
                        actorsUsed--;
                        localSuperIndex = superIndex;
                        localFlag = false;
                        break;
                    }
                }
                if (check) {
                    superIndex = 1;
                }
                check = true;

            }
        }
        if (localFlag == true) {
            localMinima = true;
        }

        return sol;
    }

    private static boolean checkValid(int[][] sol, int i, int k, int[] d1d2) {
        if (sol[i][0] == 0) {
            return true;
        }
        if (sol[i][2] == d1d2[0] || sol[i][2] == d1d2[1]) {
            return true;
        }
        if (sol[i][0] > k) {
            return true;
        }
        if (sol[i][1] != 1) {
            return true;
        }
        return false;
    }

    private static int[][] swapTwoActors(int[][] sol, int[] d1d2, int k, int n, int[][] rolePartners,
            int[][] rolesActors) {
        swapMade = false;
        int[] r1r2 = new int[2];
        boolean check = true;
        for (int i = iSwap; i < sol.length; i++) {
            if (checkValid(sol, i, k, d1d2)) {
                iSwap++;
                continue;
            }
            iSwap++;
            for (int j = jSwap + 1; j < sol.length; j++) {
                jSwap++;
                if (checkValid(sol, j, k, d1d2)) {
                    continue;
                }
                r1r2[0] = sol[i][2];
                r1r2[1] = sol[j][2];
                if (!checkRolePossible(sol[i][0], r1r2[1], rolesActors)) {
                    continue;
                }
                if (!checkRolePossible(sol[j][0], r1r2[0], rolesActors)) {
                    continue;
                }
                check = checkRoleScenes(r1r2, rolePartners);
                if (!check) {
                    sol[i][2] = r1r2[1];
                    sol[j][2] = r1r2[0];
                    swapMade = true;
                    break;
                }
            }
            if (swapMade) {
                break;
            }
        }
        return sol;
    }

    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 int getSuper(int[][] sol, int k) {
        for (int i = 0; i < sol.length; i++) {
            if (sol[i][0] == k + superIndex) {
                superIndex++;
                return i;
            }
        }
        return 0;
    }

    private static void printSol(int[][] sol) {
        for (int i = 0; i < sol.length; i++) {
            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 roleIndex, int[][] sol) {
        sol[roleIndex][0] = actor;
        sol[roleIndex][1] = 1;
        sol[roleIndex][2] = role + 1;
        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 boolean checkDivaScenes(int[] d1d2, int[][] sr) {
        boolean dOneInScene = false;
        boolean dTwoInScene = false;
        if (d1d2[0] == 0 || d1d2[1] == 0) {
            return true;
        }
        for (int i = 0; i < sr.length; i++) {
            for (int j = 1; j <= sr[i][0]; j++) {
                if (sr[i][j] == d1d2[0]) {
                    dOneInScene = true;
                } else if (sr[i][j] == d1d2[1]) {
                    dTwoInScene = true;
                }
                if (dOneInScene == true && dTwoInScene == true) {
                    return true;
                }
            }
            dOneInScene = dTwoInScene = 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;

    }
}