/* -*- linux-c -*-

This program prints the number of orbits in a graph.
compile: nauty.o, nautil.o and naugraph.o.

This version uses dynamic allocation.

HAR HAR HAR
clnauty5000  also need clnauty1000, clnauty100, clnauty10

*/
#define MAXN 1025
#define MAX_SUBS 10000
#define SPLIT_TYPE 1
#define INDUCE_TYPE 2

#include "nauty.h"    
/* which includes <stdio.h> */

struct dbentry
{
	int verts[MAXN];
	int orbs[MAXN];
	int vertNum;
	int used;
	int maxOrb;
	int maxOrbIdx;
	int minDeg;
	int minDegIdx;
};

typedef  struct dbentry  subgr;


void printSubgr(subgr* a)
{
	int i;
	for(i=0;i<a->used;i++)
		printf("%d ",a->verts[i]);
	printf(" -1\n");
	for(i=0;i<a->vertNum-a->used;i++)
		printf("%d ",a->verts[i+a->used]);
	printf(" -2\n");
}


void copyOrbStruct(subgr* a, subgr* b)
{
	int i;	
	b->vertNum= a->vertNum;
	b->used=a->used;
	b->maxOrb=a->maxOrb;
	b->maxOrbIdx=a->maxOrbIdx;
	for(i=0;i<a->vertNum;i++){
		b->verts[i]=a->verts[i];
		b->orbs[i]=a->orbs[i];
	}
}

/*Returns 1 if they are isomorphic, returns 0 if they are different*/
int orbStructComp(subgr* a, subgr* b, int dasGraph[][MAXN])
{
	int i,j,k,l;
	int same=1;
/*	if(a->vertNum==37 && a->used==3){
		if(b->vertNum==36 && b->used==2){
			for(i=0;i<a->used;i++)
				fprintf(stderr,"%d ",a->verts[i]);
			fprintf(stderr," -1\n");
			for(i=0;i<a->vertNum-a->used;i++){
				if(a->verts[i+a->used]>=4095)
					fprintf(stderr,"**");
				fprintf(stderr,"%d ",a->verts[i+a->used]);
			}
			fprintf(stderr," -2\n");

			for(i=0;i<b->used;i++)
				fprintf(stderr,"%d ",b->verts[i]);
			fprintf(stderr," -1\n");
			for(i=0;i<b->vertNum-b->used;i++){
				if(a->verts[i+a->used]>=4095)
					fprintf(stderr,"**");	
				fprintf(stderr,"%d ",b->verts[i+b->used]);
			}
			fprintf(stderr," -2\n");
		
			for(i=0;i<(a->vertNum - a->used);i++){
				for(j=i+1;j<(a->vertNum - a->used);j++){
					fprintf(stderr,"checking dg[%d][%d] !=  dg[%d][%d]\n",a->verts[a->used+i],a->verts[a->used+j],b->verts[b->used+i],b->verts[b->used+j]);
					
					if(dasGraph[a->verts[a->used+i]][a->verts[a->used+j]] != dasGraph[b->verts[b->used+i]][b->verts[b->used+j]]){
						return 0;
					}   
				}
			}
			return same;
		}
		}*/
	for(i=0;i<(a->vertNum - a->used);i++){
		for(j=i+1;j<(a->vertNum - a->used);j++){
			
			if(dasGraph[a->verts[a->used+i]][a->verts[a->used+j]] != dasGraph[b->verts[b->used+i]][b->verts[b->used+j]]){
				return 0;
			}   
		}
	}
	return same;
}

void writeSubgr(subgr* a,int orbits[],int lab[], int theOrbits[], int dasGraph[][MAXN])
{
	int i,j,k,l,n;
	n=a->vertNum-a->used;
	/*remap the verticies into a cannonical order*/
	for(i=0;i<n;i++)
		theOrbits[i]=a->verts[i+a->used];
	for(i=0;i<n;i++){
		a->verts[i+a->used]=theOrbits[lab[i]];
	}
	for(i=0;i<n;i++)
		a->orbs[i]=orbits[lab[i]];
	/*relabel orbs to normal form by swaping*/
	for(i=0;i<n;i++){
		if(a->orbs[i]>i){
			k=a->orbs[i];
			for(j=i;j<n;j++){
				if(a->orbs[j]==k)
					a->orbs[j]=i;
				else if(a->orbs[j]==i)
					a->orbs[j]=k;
			}
		}
	}
	for(i=0;i<n;i++)
		theOrbits[i]=0;
	for(i=0;i<n;i++)
		theOrbits[a->orbs[i]]++;
	j=k=0;
	for(i=0;i<n;i++){
		if(theOrbits[i]>j){ 
			k=i;
			j=theOrbits[i];
		}
	}
	a->maxOrb=j;
	a->maxOrbIdx=k;


	for(i=0;i<a->vertNum-a->used;i++)
		theOrbits[i]=0;
	for(i=0;i<a->vertNum - a->used;i++){
		for(j=i;j<a->vertNum- a->used;j++){
			if(i!=j){
				if(dasGraph[a->verts[a->used+i]][a->verts[a->used+j]]){
					theOrbits[i]++;
					theOrbits[j]++;
				}
			}
		}
	}
	a->minDegIdx=0;
	a->minDeg=a->vertNum- a->used;
	for(i=0;i<a->vertNum- a->used;i++){
		if(theOrbits[i]<a->minDegIdx){
			a->minDeg=theOrbits[i];
			a->minDegIdx=i;
		}
	}
}

main()
{
	int dasGraph[MAXN][MAXN];
	int theOrbits[MAXN];
	subgr sg[MAX_SUBS];
	int subCount;
	int orbitNum;
	int bad;
	int i,j,k,l,n,m,v,theEdges,edg1,edg2;
	int lastSize;

/*Nauty variables*/
	graph g[MAXN*MAXM],g2[MAXN*MAXM];
	int lab[MAXN],ptn[MAXN],orbits[MAXN];
	static DEFAULTOPTIONS(options);
	statsblk(stats);
	setword workspace[50*MAXM];
	set *gv;

	//options.writeautoms =TRUE;
	options.getcanon=TRUE;
 
	scanf("%d",&n);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++)
			dasGraph[i][j]=0;
	}
	while(1){
		scanf("%d",&edg1);
		if(edg1<0)
			break;
		scanf("%d",&edg2);
		dasGraph[edg1][edg2]=dasGraph[edg2][edg1]=1;
	}          
    
	/* Init the graph data*/
	for(i=0;i<n;i++)
		sg[0].verts[i]=i;
	sg[0].vertNum=n;
	sg[0].used=0;
	subCount=1;
	m = (n + WORDSIZE - 1) / WORDSIZE;
	for (v = 0; v < n; ++v){
		gv = GRAPHROW(g,v,m);
		EMPTYSET(gv,m);
	}
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			if(dasGraph[i][j]){
				ADDELEMENT(GRAPHROW(g,i,m),j);
				ADDELEMENT(GRAPHROW(g,j,m),i);
			}	  
		}      
	}
	nauty(g,lab,ptn,NULL,orbits,&options,&stats,
	      workspace,100,m,n,g2);
	/*Write the nauty info to the subgr*/
	writeSubgr(&sg[0],orbits,lab,theOrbits,dasGraph);

	/*Start the main loop*/

	lastSize=sg[0].vertNum-sg[0].used;
	while(subCount<(MAX_SUBS-2)){
		switch(SPLIT_TYPE){
		case 1:
			j=sg[0].vertNum-sg[0].used;
			k=0;
			for(i=1;i<subCount;i++){
				if((sg[i].vertNum-sg[i].used)>j){
					j=sg[i].vertNum-sg[i].used;
					k=i;
				}
			}
			break;
		case 2:
			
			j=sg[0].maxOrb;
			k=0;
			for(i=1;i<subCount;i++){
				if((sg[i].maxOrb)>j){
					j=sg[i].maxOrb;
					k=i;
				}
			}
			break;
		case 3:
			j=sg[0].minDeg;
			k=0;
			for(i=1;i<subCount;i++){
				if((sg[i].minDeg)>j){
					j=sg[i].minDeg;
					k=i;
				}
			}
			break;
		}

		fprintf(stderr,"subcount:%d maxorb:%d index:%d unused:%d\n",subCount,sg[k].maxOrb,k,sg[k].vertNum-sg[k].used);



		/*Let the induced keep the index, and the orbitless tack on the end of the list*/
 
		for(i=0;i<sg[k].used;i++)
			sg[subCount].verts[i]=sg[k].verts[i];
		sg[subCount].used=sg[subCount].vertNum=sg[k].used;

		switch(INDUCE_TYPE){
		case 1:
			for(i=0;i<(sg[k].vertNum-sg[k].used);i++){
				if(sg[k].orbs[i]!=sg[k].orbs[sg[k].minDegIdx]){
					sg[subCount].verts[sg[subCount].vertNum]=sg[k].verts[sg[k].used+i];
					sg[subCount].vertNum++;
				}
			}
			break;
		case 2:
			if(sg[k].maxOrb>1){
				for(i=0;i<(sg[k].vertNum-sg[k].used);i++){
					if(sg[k].orbs[i]!=sg[k].orbs[sg[k].maxOrbIdx]){
						sg[subCount].verts[sg[subCount].vertNum]=sg[k].verts[sg[k].used+i];
						sg[subCount].vertNum++;
					}
				}
			}
			else{
				for(i=0;i<(sg[k].vertNum-sg[k].used);i++){
					if(sg[k].orbs[i]!=sg[k].orbs[sg[k].minDegIdx]){
						sg[subCount].verts[sg[subCount].vertNum]=sg[k].verts[sg[k].used+i];
						sg[subCount].vertNum++;
					}
				}
				
			}

			break;
		}

		n=sg[subCount].vertNum-sg[subCount].used;
		m = (n + WORDSIZE - 1) / WORDSIZE;
		for (v = 0; v < n; ++v){
			gv = GRAPHROW(g,v,m);
			EMPTYSET(gv,m);
		}
		for(i=0;i<n;i++){
			for(j=i+1;j<n;j++){
				if(dasGraph[sg[subCount].verts[sg[subCount].used+i]][sg[subCount].verts[sg[subCount].used+j]]){
					ADDELEMENT(GRAPHROW(g,i,m),j);
					ADDELEMENT(GRAPHROW(g,j,m),i);
				}	  
			}      
		}
		nauty(g,lab,ptn,NULL,orbits,&options,&stats,
		      workspace,100,m,n,g2);
		/*Write the nauty info to the subgr*/
		writeSubgr(&sg[subCount],orbits,lab,theOrbits,dasGraph);
		fprintf(stderr,"newsub: unused:%d used:%d maxOrb: %d\n",sg[subCount].vertNum-sg[subCount].used,sg[subCount].used,sg[subCount].maxOrb);
		subCount++;
		
		/*Induce the original*/
		/*Swap the max orb with the first unused vertex */
		i=sg[k].verts[sg[k].used];

		switch(INDUCE_TYPE){
		case 1:

			sg[k].verts[sg[k].used]=sg[k].verts[sg[k].used+sg[k].minDegIdx];
			sg[k].verts[sg[k].used+sg[k].minDegIdx]=i;
			break;
		case 2:
			if(sg[k].maxOrb>1){
			sg[k].verts[sg[k].used]=sg[k].verts[sg[k].used+sg[k].maxOrbIdx];
			sg[k].verts[sg[k].used+sg[k].maxOrbIdx]=i;
			}
			else{
				sg[k].verts[sg[k].used]=sg[k].verts[sg[k].used+sg[k].minDegIdx];
				sg[k].verts[sg[k].used+sg[k].minDegIdx]=i;
			}
	
			break;
		}
		sg[k].used++;
		/*Get rid of all verts not connected to the new used vert*/
		j=0;
		for(i=0;i<sg[k].vertNum-sg[k].used;i++){
			if(dasGraph[sg[k].verts[sg[k].used-1]][sg[k].verts[sg[k].used+i]]){
				sg[k].verts[sg[k].used+j]=sg[k].verts[sg[k].used+i];
				j++;
			}
			
		}
		sg[k].vertNum=sg[k].used+j;
		n=j;
		m = (n + WORDSIZE - 1) / WORDSIZE;
		for (v = 0; v < n; ++v){
			gv = GRAPHROW(g,v,m);
			EMPTYSET(gv,m);
		}
		for(i=0;i<n;i++){
			for(j=i+1;j<n;j++){
				if(dasGraph[sg[k].verts[sg[k].used+i]][sg[k].verts[sg[k].used+j]]){
					ADDELEMENT(GRAPHROW(g,i,m),j);
					ADDELEMENT(GRAPHROW(g,j,m),i);
				}	  
			}
		}      
		nauty(g,lab,ptn,NULL,orbits,&options,&stats,
		      workspace,100,m,n,g2);
/*Write the nauty info to the subgr*/
		writeSubgr(&sg[k],orbits,lab,theOrbits,dasGraph);
		fprintf(stderr,"induced  unused:%d used:%d maxOrb: %d\n",sg[k].vertNum-sg[k].used,sg[k].used,sg[k].maxOrb);
		/*if(subCount>=109)
			fprintf(stderr,"here2\n");*/
		
/*Check for isomorphisms, delete one with smaller used set*/
		for(i=0;i<subCount-1;i++){
			if((sg[subCount-1].vertNum-sg[subCount-1].used)==(sg[i].vertNum-sg[i].used)){
				j=orbStructComp(&sg[i],&sg[subCount-1],dasGraph);
				if(j==1){
					fprintf(stderr,"Sweet split one i:   k:\n",i,subCount-1);
					if(sg[i].used<sg[subCount-1].used)
						copyOrbStruct(&sg[subCount-1],&sg[i]);
					subCount--;
					break;
				}					
			}
		}
		/*if(subCount>=109)
		  fprintf(stderr,"here3\n");*/

		for(i=0;i<subCount;i++){
			if(i!=k){
				if((sg[k].vertNum-sg[k].used)==(sg[i].vertNum-sg[i].used)){
					j=orbStructComp(&sg[i],&sg[k],dasGraph);
					if(j==1)
						fprintf(stderr,"Sweet split one i:   k:\n",i,k);
					if(j==1){
						/*if(subCount>=109)
						  fprintf(stderr,"here3.6\n");*/
						if(sg[i].used<sg[k].used)
							copyOrbStruct(&sg[subCount-1],&sg[i]);
						else
							copyOrbStruct(&sg[subCount-1],&sg[k]);	
						subCount--;
						break;
					}					
				}
			}
		}
		/*if(subCount>=109)
		  fprintf(stderr,"here4\n");*/	
	}
	fprintf(stderr,"\n about to print results\n");
	for(i=0;i<subCount;i++)
		printSubgr(&sg[i]);
	printf("-3");
	return;
}