//
// given a graph G = (V,E) and an integer h, remove as
// few edges from E such that every component of G is
// of size h or less.
//
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import org.chocosolver.solver.*;
import org.chocosolver.solver.variables.*;
import org.chocosolver.solver.constraints.*;
import org.chocosolver.solver.search.strategy.*;
import org.chocosolver.solver.search.strategy.strategy.IntStrategy;
import org.chocosolver.solver.search.strategy.selectors.values.*;
import org.chocosolver.solver.search.loop.monitors.*;

public class Cows3 {
    Solver solver;
    int n;               // number of vertices
    int m;               // number of edges
    int h;               // size of largest component
    int components;      // max number of components = (n+1)/h, using integer arithmetic
    int [][] adj;        // adj[i][j] = 1 <-> there is an edge between vertices i and j, read in
    IntVar[] v;          // v[i] = j <-> vertex v in component j, these are the decision variables   
    IntVar[][] A;        // A[i][j] = 1 <-> vertices i and j are adjacent
    IntVar[] flatEdges;  // all edges in A, flattened. We want to maximise the count of these
    IntVar sumEdges;     // total number of edges, to be maximised
    IntVar[][] location; //location[i][j] = 1 <-> v[j] = i, i.e. vertex j is in component i

    Cows3 (String fname,int h) throws IOException {
        Scanner sc = new Scanner(new File(fname));	       
	n          = sc.nextInt(); // number of vertices
	solver     = new Solver("cows");
	components = n;
	v          = VF.enumeratedArray("v",n,0,components-1,solver);
	A          = new IntVar [n][n];
	adj        = new int [n][n];
	this.h     = h; 
	sumEdges   = VF.enumerated("sumEdges",0,n*(n-1)/2,solver);
	location   = VF.enumeratedMatrix("location",components,n,0,1,solver);
		
	while (sc.hasNext()){
	    int i = sc.nextInt();
	    int j = sc.nextInt();
	    adj[i][j] = adj[j][i] = 1;
	    m++;
	}
	sc.close();
	//
	// read in graph as undirected edges
	//

	for (int i=0;i<n;i++) A[i][i] = VF.fixed(0,solver);
	// 
	// no need for this, it just makes output easier (saves an if)
	//

	for (int i=0;i<n;i++){
	    for (int j=0;j<n;j++) System.out.print(adj[i][j] +" ");
	    System.out.println();
	}
	System.out.println();
	//
	// input adjacency matrix, output it so we can see change
	//
	
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++){
		if (adj[i][j] == 0){ // unconstrained pair of vertices
		    A[i][j] = A[j][i] = VF.fixed(0,solver);
		}
		if (adj[i][j] == 1){ // constrained, there can be an edge
		    A[i][j] = A[j][i] = VF.enumerated("A["+ i +"]["+ j +"]",0,1,solver);
		    // A[i][j] = 1 -> v[i] = v[j] ... same component, i.e. select edge and take consequences
		    LCF.ifThen(ICF.arithm(A[i][j],"=",1),ICF.arithm(v[i],"=",v[j]));
		}
	    }

        // make sure every component has size no more than h, using global cardinality constraint
        int[] values = new int[components]; // the different values that can be taken
	for (int i=0;i<components;i++) values[i] = i;
        IntVar[] occurrences =  VF.enumeratedArray("occurrences",components,0,h,solver); // occurences of each value
        solver.post(ICF.global_cardinality(v,values,occurrences,true)); // values can occur between 0 and h times.

	// we want to maximise number of edges selected
	flatEdges = VF.enumeratedArray("flatEdges",n*(n-1)/2,0,1,solver);
	for (int i=0,k=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++,k++)
		flatEdges[k] = A[i][j];
	solver.post(ICF.sum(flatEdges,"=",sumEdges));

	//
	// symmetry break
	// location[i][j] = 1 <-> v[j] is in component i
	// we can then lex order loaction, first by channeling from v to location
	// and then lex ordering rows of location.
	//
	for (int i=0;i<components;i++)
	    for (int j=0;j<n;j++){
		LCF.ifThen(ICF.arithm(location[i][j],"=",1),ICF.arithm(v[j],"=",i));
		LCF.ifThen(ICF.arithm(v[j],"=",i),ICF.arithm(location[i][j],"=",1));
	    }
	solver.post(ICF.lex_chain_less_eq(location)); // matrix is lex ordered
	
    }

    void solve() {
	solver.set(ISF.minDom_UB(v)); // decisons are vertex components, values decending, to help lex constraint
	solver.findOptimalSolution(ResolutionPolicy.MAXIMIZE,sumEdges); // maximise number of edges selected
    }

    void result(){
	for (int i=0;i<n;i++){
	    for (int j=0;j<n;j++)
		System.out.print(A[i][j].getValue() +" ");
	    System.out.println();
	}
    }
    //
    // output new adjacency matrix
    //

     void locations(){
	 System.out.println();
	 System.out.println("locations");
	 for (int i=0;i<n;i++){
	    for (int j=0;j<n;j++)
		System.out.print(location[i][j].getValue() +" ");
	    System.out.println();
	}
    }

    void stats() {
        System.out.println("nodes: " + solver.getMeasures().getNodeCount() + 
			   " cpu: " + solver.getMeasures().getTimeCount() +
			   " edge deletions: " + (m - sumEdges.getValue()));
    }

    public static void main(String[] args) throws IOException {
        Cows3 cows = new Cows3(args[0],Integer.parseInt(args[1]));
	long cpuLimit = Long.parseLong(args[2]);
	SMF.limitTime(cows.solver,cpuLimit*1000);
        cows.solve();
	cows.result();
	cows.locations();
	cows.stats();
    }
}