#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>



using std::stringstream;
using std::vector;
using std::cin;
using std::cout;
using std::endl;



typedef unsigned long ULong;



enum EVerbosity
{
	eNone = 0,
	eSome = 1,
	eAll	= 2
};



class	SDefeat
{
public:

	SDefeat( void ) {}
	~SDefeat( void ) {}
	
	ULong x;
	ULong y;
	ULong strength;
	ULong margin;	
};



#define ThrowIf_( x, theException ) if ( x ) throw theException



static void 	PrintHTMLMatrix( vector<ULong> &matrix, ULong nOptions );
static bool 	CondorcetRankedPairs( vector<ULong> &matrix, ULong nOptions, EVerbosity verbosity );
static void		SortUnconsideredDefeats( vector<ULong>		&defeats,
																			 vector<ULong>		&considered,
																			 vector<ULong>		&matrix,
																			 ULong 						nOptions,
																			 vector<SDefeat>	&outSorted );
static void 	FloydsAlgorithm( vector<ULong>	&a, ULong nOptions );



int main( int argc, const char * argv[] )
{
	ULong					x;
	ULong					nOptions			= 0;
	ULong					matrixSize;
  vector<ULong>	matrix;
	ULong					inVerbosity;
	int						exitStatus		= 0;
	EVerbosity		verbosity;
	ULong					i							= 1;

	try
	{
		stringstream strStream;
		strStream << argv[i];
		strStream >> nOptions;
		strStream.clear();
		i++;
		
		matrixSize 	= nOptions * nOptions;
		ThrowIf_( ULong(argc) != matrixSize + 3, 1 );

		matrix.resize(matrixSize);

		for ( x = 0; x < matrixSize; x++ )
		{
			strStream.str( "" );
			strStream << argv[i];
			strStream >> matrix[x];
			strStream.clear();
			
			i++;
		}

		strStream << argv[i];
		strStream >> inVerbosity;

		verbosity = EVerbosity(inVerbosity);

		if ( verbosity > eNone )
		{
			cout << "The input matrix was:<br>" << endl;
			PrintHTMLMatrix( matrix, nOptions );
		}

		CondorcetRankedPairs( matrix, nOptions, verbosity );
	}
	catch( ... )
	{
		exitStatus = 1;
	}

	return exitStatus;
}



bool CondorcetRankedPairs( vector<ULong> &matrix, ULong nOptions, EVerbosity verbosity )
{
	ULong							x, y;
	vector<ULong> 		defeats;
	vector<ULong> 		kept;
	vector<ULong> 		considered;
	vector<ULong> 		tie;
	vector<SDefeat> 	sortedDefeats;
	vector<SDefeat> 	consideringDefeats;
	ULong							matrixSize					= nOptions * nOptions;
	bool							success							= true;
	bool							hasDefeat;
	ULong							xyIndex;
	ULong							yxIndex;
	ULong							yyIndex;
	
	try
	{
		defeats.resize( matrixSize );
		kept.resize( matrixSize );
		considered.resize( matrixSize );
		tie.resize( matrixSize );
		
		for ( x = 0; x < nOptions; x++ )
		{
			for ( y = 0; y < nOptions; y++ )
			{
				xyIndex = ( x * nOptions ) + y;
				yxIndex = ( y * nOptions ) + x;
				
				defeats[xyIndex] = matrix[xyIndex];
				
				if ( matrix[xyIndex] > matrix[yxIndex] )
					defeats[yxIndex] = 0;
				else if ( matrix[xyIndex] < matrix[yxIndex] )
					defeats[xyIndex] = 0;
				else if ( matrix[xyIndex] == matrix[yxIndex] )
					defeats[xyIndex] = defeats[yxIndex];

				if ( defeats[xyIndex] > 0 )
					tie[xyIndex] = 1;
				
				kept[xyIndex] 			= 0;
				considered[xyIndex] = 0;
			}
		}

		if ( verbosity > eNone )
		{
			cout << "The defeats matrix was: <br>" << endl;
			PrintHTMLMatrix( defeats, nOptions );
			cout << "<br>" << endl;
		}

		// first pass
		//   vertices that don't cycle back to themselves
		//   have defeats we can keep
		FloydsAlgorithm( tie, nOptions );
		
		for ( x = 0; x < nOptions; x++ )
		{
			for ( y = 0; y < nOptions; y++ )
			{
				xyIndex = ( x * nOptions ) + y;
				if ( defeats[xyIndex] > 0 )
				{
					if ( tie[ ( y * nOptions ) + y ] == 0 )
					{
						kept[xyIndex] = considered[xyIndex] = 1;
						
						if ( verbosity > eNone )
							cout << "Now Keeping: " << x << " defeats " << y << "<br>" << endl;
					}			
				}
			}
		}

		if ( verbosity > eSome )
		{
			std::cout << "The first pass Floyd Results:<br>" << std::endl;
			PrintHTMLMatrix( tie, nOptions );
			std::cout << "<br>" << std::endl;
			
			std::cout << "The first pass results were (kept/considered):<br>" << std::endl;
			PrintHTMLMatrix( kept, nOptions );
			std::cout << "<br>" << std::endl;
		}

		SortUnconsideredDefeats( defeats, considered, matrix, nOptions, sortedDefeats );
		if ( verbosity > eSome )
		{
			std::cout << "Sorted defeats count = " << sortedDefeats.size() << "<br>" << std::endl;
			for ( x = 0; x < sortedDefeats.size(); x++ )
				std::cout << sortedDefeats[x].x << " "
									<< sortedDefeats[x].y << " "
									<< sortedDefeats[x].strength << " "
									<< sortedDefeats[x].margin << " "
									<< "<br>" << std::endl;
		}
		
		while ( sortedDefeats.size() > 0 )
		{
			// add in the already kept defeats
			tie.assign( kept.begin(), kept.end() );
			
			// find the next set of defeats to check cycles for
			consideringDefeats.clear();
			consideringDefeats.push_back( sortedDefeats.back() );
			sortedDefeats.pop_back();
			
			xyIndex 							= ( consideringDefeats.back().x * nOptions ) +
																consideringDefeats.back().y;
			tie[xyIndex] 					= 1;
			considered[xyIndex]		= 1;

			while ( sortedDefeats.size() > 0 &&
					 		sortedDefeats.back().strength == consideringDefeats.back().strength &&
					 		sortedDefeats.back().margin   == consideringDefeats.back().margin )
			{
				consideringDefeats.push_back( sortedDefeats.back() );
				sortedDefeats.pop_back();

				xyIndex 							= ( consideringDefeats.back().x * nOptions ) +
																	consideringDefeats.back().y;
				tie[xyIndex] 					= 1;
				considered[xyIndex]		= 1;
			}

			if ( verbosity > eSome )
			{
				cout << "Now considering:<br>" << endl;
				
				for ( x = 0; x < consideringDefeats.size(); x++ )
					cout << consideringDefeats[x].x << " "
										<< consideringDefeats[x].y << " "
										<< consideringDefeats[x].strength << " "
										<< consideringDefeats[x].margin << " "
										<< "<br>" << endl;
				
					
				cout << "Checking cycles on:<br>" << endl;
				PrintHTMLMatrix( tie, nOptions );
				cout << "<br>" << endl;
			}

			FloydsAlgorithm( tie, nOptions );
			
			if ( verbosity > eSome )
			{
				cout << "Floyd Result:<br>" << endl;
				PrintHTMLMatrix( tie, nOptions );
				cout << "<br>" << endl;
			}
			
			for ( x = 0; x < consideringDefeats.size(); x++ )
			{				
				//yyIndex = ( consideringDefeats[x].y * nOptions ) + consideringDefeats[x].y;
				yxIndex = ( consideringDefeats[x].y * nOptions ) + consideringDefeats[x].x;
				xyIndex = ( consideringDefeats[x].x * nOptions ) + consideringDefeats[x].y;
				
				if ( tie[yxIndex] == 0 )
				{
					kept[xyIndex] = 1;
					if ( verbosity > eNone )
						cout << "Now Keeping: "
											<< consideringDefeats[x].x
											<< " defeats "
											<< consideringDefeats[x].y
											<< "<br>" << endl;
				}
			}

			if ( verbosity > eSome )
			{
				cout << "Kept Matrix:<br>" << endl;
				PrintHTMLMatrix( kept, nOptions );
				cout << "<br>" << endl;
				
				cout << "Considered Matrix:<br>" << endl;
				PrintHTMLMatrix( considered, nOptions );
				cout << "<br>" << endl;
			}
		}

		cout << "WIN";
		
		for ( x = 0; x < nOptions; x++ )
		{
			hasDefeat		= false;
			for ( y = 0; y < nOptions && !hasDefeat; y++ )
			{
				yxIndex = ( y * nOptions ) + x;
				
				if ( kept[yxIndex] > 0 )
					hasDefeat = true;
			}

			cout << "-";
			
			if ( !hasDefeat )
				cout << "1";
			else
				cout << "0";
		}
	}
	catch( ... )
	{
		success = false;
	}

	return success;
}



void SortUnconsideredDefeats( vector<ULong>			&defeats,
															vector<ULong>			&considered,
															vector<ULong>			&matrix,
															ULong 						nOptions,
															vector<SDefeat>		&outSorted )
{
	ULong			x, y;
	ULong			i					= 0;
	ULong			xyIndex;
	ULong			yxIndex;
	SDefeat	defeat;
	
	// obtain the defeats
	for ( x = 0; x < nOptions; x++ )
	{
		for ( y = 0; y < nOptions; y++ )
		{
			xyIndex = ( x * nOptions ) + y;
			yxIndex = ( y * nOptions ) + x;
			
			if ( defeats[xyIndex] > 0 && considered[xyIndex] == 0 )
			{
				defeat.x 				= x;
				defeat.y 				= y;
				defeat.strength = defeats[xyIndex];
				defeat.margin		= matrix[xyIndex] - matrix[yxIndex];
				outSorted.push_back( defeat );
				i++;
			}
		}
	}

	sort( outSorted.begin(), outSorted.end() );
}



void FloydsAlgorithm( vector<ULong> &a, ULong nOptions )
{
	ULong	xyIndex;
	ULong yjIndex;
	ULong xjIndex;
	ULong	x, y, j;
	ULong value;
	
	for ( y = 0; y < nOptions; y++ )
	{
		for ( x = 0; x < nOptions; x++ )
		{
			xyIndex = ( x * nOptions ) + y;
			
			if ( a[xyIndex] > 0 )
			{
				for ( j = 0; j < nOptions; j++ )
				{
					yjIndex = ( y * nOptions ) + j;
					
					if ( a[yjIndex] > 0 )
					{
						xjIndex = ( x * nOptions ) + j;
						value = a[xyIndex] + a[yjIndex];
						if ( a[xjIndex] == 0 || value < a[xyIndex] )
							a[xjIndex] = value;
					}
				}
			}
		}
	}
}



void PrintHTMLMatrix( vector<ULong> &matrix, ULong nOptions )
{
	ULong x, y;
	
	cout << "<table  bgcolor=#cccccc border=2>" << endl;
	
	// output first row
	cout << "<tr>" << endl;

		// upper left corner of table
	cout << "<td>Option</td>" << endl;

		// build remainder of row
	for ( x = 0; x < nOptions; x++ )
	{
		cout <<  "<td align=center>" << x << "</td>" << endl;
	}

	cout <<  "</tr>" << endl;

	// output remaining rows
	for ( x = 0; x < nOptions; x++ )
	{
		cout <<  "<tr>" << endl;
		cout <<  "<td valign=center>" << x << "</td>" << endl;

		for ( y = 0; y < nOptions; y++ )
		{
			cout <<  "<td>" << endl;
			cout <<  matrix[ ( x * nOptions ) + y ];
			cout <<  "</td>" << endl;
		}

		cout <<  "</tr>" << endl;
	}

	cout <<  "</table>" << endl;
}



bool operator< ( const SDefeat &a, const SDefeat &b )
{
	if ( a.strength > b.strength )
		return false;
	else if ( a.strength < b.strength )
		return true;
	else if ( a.margin > b.margin )
		return false;
	else if ( a.margin < b.margin )
		return true;
	else
		return false;
}



bool operator== ( const SDefeat &a, const SDefeat &b )
{
	if ( a.strength > b.strength )
		return false;
	else if ( a.strength < b.strength )
		return false;
	else if ( a.margin > b.margin )
		return false;
	else if ( a.margin < b.margin )
		return false;
	else
		return true;
}