import java.util.Scanner;
import java.io.*;

/*
 * Lab 11
 *
 * Author: Robin Dawes
 *
 * Date: 20091130
 *
 * Comment: some diagnostic output has been included to make it possible to follow the execution of the algorithm
 *
 */

public class Spies {

    static int instances;
    static int numOfUsers;
    
    static int[][] friends;
    
    static int globalU;

    public static void main (String[] argv) throws Exception {
        Scanner myScanner = new Scanner(new File("Lab_11_Data.txt"));
        // find out how many instances
        instances = myScanner.nextInt();
        for (int i = 0; i < instances; i++) {
            
            System.out.println("\nInstance " + i + " input: ");
            
            numOfUsers = myScanner.nextInt();
            System.out.println("# of users = " + numOfUsers);
            
            friends = new int[numOfUsers][numOfUsers];
            
           
            for (int r = 0; r < numOfUsers; r++) 
                for (int c = 0; c < numOfUsers; c++) 
                    friends[r][c] = myScanner.nextInt();
                    
            
            for (int r = 0; r < numOfUsers; r++) {
                for (int c = 0; c < numOfUsers; c++)
                    System.out.print(friends[r][c] + "\t");
                System.out.println();
            }
            
            // initialize the global upper bound
            globalU = numOfUsers;            
            
            boolean notDone = true;
            
            // initialize the heap S of partial solutions
            
            PartialSolutionHeap S = new PartialSolutionHeap();
            boolean[] chosen = new boolean[numOfUsers];
            boolean[] dominated = new boolean[numOfUsers];
            
            // initialize the set of partial solutions
            System.out.println("Initializing set of partial solutions");
            int nextWorker = 0;
            
            // either choose this user ...
            
            chosen[0] = true;
            dominated[0] = true;
            for (int u = 1; u < numOfUsers; u++) dominated[u] = (friends[0][u] == 1);
            for (int u = 1; u < numOfUsers; u++) chosen[u] = false;
            
            PartialSolution p = new PartialSolution(numOfUsers, friends, chosen, dominated, 1, 0);
            if (p.getLower() <= globalU) S.insert(p);
            if (p.getUpper() < globalU) globalU = p.getUpper();
            
            // or don't ...
            chosen = new boolean[numOfUsers];
            dominated = new boolean[numOfUsers];
            for (int u = 0; u < numOfUsers; u++) {
                chosen[u] = false;
                dominated[u] = false;
            }
            p = new PartialSolution(numOfUsers, friends, chosen, dominated, 0, 0);
            if (p.getLower() <= globalU) S.insert(p);
            if (p.getUpper() < globalU) globalU = p.getUpper();
        
            
            System.out.println("Partial solution set initialized");
            
            while (notDone && S.notEmpty()) {
                // extract the partial solution P with the lowest lower bound
                // System.out.println("Extracting a partial solution");
                PartialSolution x = S.extractMin();
                // if it is a full solution, output it and set notDone = false
                if (x.isFullSolution()) {
                    System.out.println("Solution found");
                    x.printChoices();
                    S.report();
                    notDone = false;
                }
                else {
                    // else generate all possible expansions of P and add them to S
                    globalU = x.expand(S, globalU);
                }
            } // while
            System.out.println("*******************");    
        } // for
        
    } // main
    
   
    
} // class