#include <stdio.h>
#include <string.h>

#define	MAX_WORDS	50
#define	MAX_CHARS	30
#define	MAX_N_MAX	5

char	words[MAX_WORDS][MAX_CHARS];
int	n_words;
int	used[MAX_WORDS];
int	best_used[MAX_WORDS];
int	n_max;
char	new_sol[MAX_WORDS*MAX_CHARS*MAX_N_MAX];
char	best_sol[MAX_WORDS*MAX_CHARS*MAX_N_MAX];

int	read_inp_file( char *s )
{
	FILE	*fp;
	int	i;

	fp = fopen( s, "r" );
	if( fp == NULL )
		return( 0 );
	fscanf( fp, "%d\n", &n_words );
	for( i = 0; i < n_words; i++ )
		fscanf( fp, "%s\n", &(words[i]) );
	fclose( fp );

	return( 1 );
}

int	is_compat( char *s1, char *s2 )
{
	int	i;

	if( strlen( s1 ) < 2 || strlen( s2 ) < 2 )
		return( 0 );

	i = strlen( s1 )-2;

	if( s1[i] == s2[0] && s1[i+1] == s2[1] )
		return( 1 );

	return( 0 );
}

void	recursive_merge( char *ns )
{
	int	i;
	int	flag;
	char	os[MAX_WORDS*MAX_CHARS*MAX_N_MAX];

	flag = 0;
	for( i = 0; i < n_words; i++ )
		if( used[i] < n_max && is_compat( ns, words[i] ) )
		{
			flag = 1;
			strcpy( os, ns );
			strcat( ns, words[i]+2 );
			used[i]++;
			recursive_merge( ns );
			strcpy( ns, os );
			used[i]--;
		}
	if( !flag )
	{
		if( strlen( ns ) > strlen( best_sol ) )
		{
			strcpy( best_sol, ns );
			for( i = 0; i < n_words; i++ )
				best_used[i] = used[i];
		}
		return;
	}
}

int	main( int argc, char **argv )
{
	char	inp_name[80];
	char	out_name[80];
	int	i, j;

	if( argc < 3 )
	{
		printf( "Usage: %s inp_file n_max\n", argv[0] );
		return( 1 );
	}

	strcpy( inp_name, argv[1] );
	sscanf( argv[2], "%d", &n_max );

	if( !read_inp_file( inp_name ) )
	{
		printf( "Inpossibile aprire: %s\n", inp_name );
		return( 1 );
	}

	best_sol[0] = '\0';
	for( i = 0; i < n_words; i++ )
	{
		for( j = 0; j < n_words; j++ )
			used[j] = 0;
		new_sol[0]='\0';

		strcpy( new_sol, words[i] );
		used[i]++;
		recursive_merge( new_sol );
	}

	for( i = 0; i < n_words; i++ )
		if( best_used[i] )
			printf( "%s\n", words[i] );

	printf( "\n%s\n", best_sol );

	return( 0 );
}