Must be in python

Consider a graph (V,E) where V is a set of nodes and E is a set of edges which connect 2 nodes and ordering on the elements in V , then the cover of two connected vertices vi and vj is defined as the distance in the ordering between vi and vj . The maximum cover of the ordering is then defined as the maximum of the individual covers. For example, consider the following graph: This can be

Figure 1: A Sample Graph

sample graph couldnt be uploaded but consists of a 3d box with points A,B,C... all the way to letter H.

ordered in many ways, two of which are illustrated below (with lines connecting adjacent vertices): For these orderings, the maximum covers of the nodes (in order) are 6, 6, 1, 4, 1, 1, 6, 6 giving a

Figure 2: Two possible orderings

maximum cover of 6, and 5, 3, 1, 4, 3, 5, 1, 4 giving a maximum cover of 5. Write a program that will find the ordering of a graph that minimizes the maximum cover.

Input

Input consists of a series of graphs. The first line of input contains a single integer g indicating the number of graphs. The first line of each graph contains of an integer n indicating the number (n > 0) of vertices in the graph. The next n lines are of the format ldl1l2...ld indicating that vertex l is connected to the vertices l1, l2. . . andld Although for analysis you should assume an infinite number of nodes, each node name (a single upper case character in the range A to Z .

Output

Output will consist of one line for each graph, listing the ordering of the nodes followed the maximum cover for that ordering. All items must be separated from their neighbors by exactly one space. If more than one ordering produces the same maximum cover, then choose the one that would appear first in an alphabetic listing.

Sample Input

1 8 A2BF B3AGC C2BD D3CGE E2DH F3AGH G3BFD H2FE

Corresponding Sample Output

ABCFGDHE3

Required Data Structure

class Graph { public: Graph (int size); // creates an empty graph with size vertices void fillGraph(); // fills in the graph from cin 

void printGraph(); // prints the graph (for debugging only) int maxCover( vector order); // returns the maxCover for the 

 // ordering order int cover( char vertex, vector order); // returns the cover size for vertex 

private: Matrix adj;// or Matrix adj; }; // from Data Structures and Algorithm Analysis in C++ (Third Edition), by Mark Allen Weiss template  class Matrix 

2

CIS 350/3501 Barely Covered Fall 2017

{ public:

 Matrix( int rows=0, int cols=0 ) : array( rows ) { 

 for( int i = 0; i < rows; i++ ) array[ i ].resize( cols ); 

 } void resize( int rows, int cols ) 

 { array.resize(rows); 

 for( int i = 0; i < rows; i++ ) array[ i ].resize( cols ); 

 } const vector