using System; using System.Linq; using System.Collections.Generic; using System.Text.RegularExpressions; using System.Text; public class Program { public void Proc() { Reader.IsDebug = false; int inputCount = int.Parse(Reader.ReadLine()); this.WordList = new string[inputCount]; for(int i=0; i ('z'-'a') + ('Z' - 'A') + 2) { Console.WriteLine("Impossible"); return; } List ans = this.GetAns(0, new Dictionary()); if(ans == null) { Console.WriteLine("Impossible"); } else { ans.ForEach(a=>Console.WriteLine(a)); } } private List GetAns(int idx, Dictionary dic) { string str1 = WordList[idx].Substring(0,1); string str2 = WordList[idx].Substring(1,2); if((!dic.ContainsKey(str1)) && (!dic.ContainsKey(str2))) { if(idx < this.WordList.Length - 1) { dic.Add(str1, idx); dic.Add(str2, idx); List tmp = GetAns(idx+1, dic); dic.Remove(str1); dic.Remove(str2); if(tmp != null) { tmp.Insert(0, str1 + " " + str2); return tmp; } } else { return new string[] {str1 + " " + str2}.ToList(); } } if(str1.Equals(this.WordList[idx].Substring(2)) || str2.Equals(this.WordList[idx].Substring(0,2))) { return null; } str1 = this.WordList[idx].Substring(0, 2); str2 = this.WordList[idx].Substring(2, 1); if((!dic.ContainsKey(str1)) && (!dic.ContainsKey(str2))) { if(idx < this.WordList.Length - 1) { dic.Add(str1, idx); dic.Add(str2, idx); List tmp = GetAns(idx+1, dic); dic.Remove(str1); dic.Remove(str2); if(tmp != null) { tmp.Insert(0, str1 + " " + str2); return tmp; } } else { return new string[] {str1 + " " + str2}.ToList(); } } return null; } private string[] WordList; public class Reader { public static bool IsDebug = true; private static System.IO.StringReader SReader; private static string InitText = @" "; public static string ReadLine() { if(IsDebug) { if(SReader == null) { SReader = new System.IO.StringReader(InitText.Trim()); } return SReader.ReadLine(); } else { return Console.ReadLine(); } } } public static void Main(string[] args) { Program prg = new Program(); prg.Proc(); } }