//
// Small test to generate isomorphs of a graph (automorph?)
//
// key generator is 
//  - f[i] = x is mapping/renaming of vertex i as vertex x, consequently
//  - if f[i] = x and f[j] = y then A[x][y] = adj[i][j]
//
// to make canonical the renaming must produce a "minimal" adjacency matrix A
//

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.*;


public class Canonical {

  
    public static void main(String[] args) throws IOException {
	Scanner sc    = new Scanner(new File(args[0]));
	int n         = sc.nextInt(); // vertices
	Solver solver = new Solver("canonical");
	IntVar[] f    = VF.enumeratedArray("f",n,0,n-1,solver); // n variables with values 0 to n-1
	IntVar[][] A  = VF.enumeratedMatrix("A",n,n,0,1,solver); // adjacency matrix
	int [][] adj  = new int[n][n];

	while (sc.hasNext()){
	    int i = sc.nextInt();
	    int j = sc.nextInt();
	    adj[i][j] = adj[j][i] = 1;
	}
	sc.close();
	//
	// read in edges
	//

	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++)
		for (int k=0;k<n;k++)
		    for (int l=0;l<n;l++){
			Constraint c1 = ICF.arithm(f[i],"=",k);
			Constraint c2 = ICF.arithm(f[j],"=",l);
			Constraint c3 = ICF.arithm(A[k][l],"=",adj[i][j]);
			LCF.ifThen(LCF.and(new Constraint[]{c1,c2}),c3);
		    }
	solver.post(ICF.alldifferent(f));
	//
	// post constraints to ensure bijection
	//

	for (int i=0;i<n-1;i++)
	    solver.post(ICF.lex_less_eq(A[i],A[i+1]));
	//
	// lex order on adjacency matrix A to make canonical
	//

	for (int i=0;i<n;i++){
	    for (int j=0;j<n;j++)
		System.out.print(adj[i][j]);
	    System.out.println();
	}
	//
	// original adjacency matrix
	//

	System.out.println(solver.findSolution());

	for (int i=0;i<n;i++) System.out.print(f[i].getValue() +" ");
	//
	// mapping/renaming of vertices
	//
	System.out.println();

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

	System.out.println("nodes: " + solver.getMeasures().getNodeCount() + 
                           "   cpu: " + solver.getMeasures().getTimeCount());
    }
}