Similar Graphs

All submissions for this problem are available.
Chef recently developed an affinity for undirected graphs.
He likes pairs of graphs that are similar in structure.
However, Chef discovered that when the vertices of a graph are reorganized, it's often the case that the resulting graph,
although still structurally similar to the original, can look completely different.
Chef wants you to help him find similarities in pairs of graphs.
Chef only considers pairs of graphs where each graph has the same number of vertices (say N).
Chef then labels each vertex of each graph with an integer between 1 and N (inclusive),
using each integer exactly once per graph.
Chef then defines the similarity of the graphs as 2*COMMON/TOTAL, where COMMON is the number of
edges appearing in both graphs
(that is, the number of unordered pairs {A, B} such that in both graphs there exists an edge between the vertex labelled A
and the vertex labelled B), and TOTAL is the total number of edges in both graphs.
Chef's measure of similarity depends on how the vertices are labelled.
Chef wants you to help him find a labelling that maximizes the similarity.
Optimal solutions are not required, but better solutions will earn more points.
Input
Input will begin with an integer T, the number of test cases.
Each test case will begin with an integer N, the number of vertices in both graphs.
2*N lines follow. The first N lines describe the first graph, and the next N lines the second graph.
Each graph description consists of N lines of N integers each.
The ith integer on the jth line will be 1 if there is an edge between vertices i and j, and 0 otherwise.
The ith integer on the jth line will always be equal to the jth integer on the ith line,
and the ith integer on the ith line will always be 0.
Output
For each test case, output 2 lines with N integers each.
Each line must contain a permutation of the integers 1 through N, and indicates how Chef should label the corresponding graph.
Scoring
Your score for each test case is the similarity of the 2 graphs using the labelling you provide.
Your overall score is the average of your scores on the individual test cases.
Sample Input
2 3 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 4 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0
Sample Output
1 2 3 1 2 3 1 4 2 3 2 4 1 3
This output would score 2*0/3 = 0.0 on the first test case, and 2*2/4 = 1.0 on the second test case, for an overall score of 0.5.
Note that better scores are possible.
Test case generation
For each official test file, T is 5.
For each test case, N is randomly chosen between 30 and 75.
A real number D is randomly chosen between 0.05 and 0.5.
For each pair of vertices, an edge is added with probability D.
This graph is output as the first graph.
An integer C is randomly chosen between 0 and N*(N1)/2.
C distinct pairs of vertices are chosen.
For each pair, if an edge currently exists between them, the edge is removed with probability (1D).
If no edge exists between them, one is added with probability D.
Then, a random permutation is applied to the vertices of the graph, and it is output as the second graph.
You may safely assume there will be no test cases where TOTAL is 0.
Author:  pieguy 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/SIMGRAPH 
Tags  april12 challenge pieguy 
Date Added:  11032012 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions