using Kzrnm.Competitive.IO; using System; using System.Buffers.Text; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Text; namespace TopoSort.Problems { internal partial class Problemyc517 { static void Solve() { var P = cr.Int(); var A = cr.Repeat(P); var Q = cr.Int(); var B = cr.Repeat(Q); var N = 0; var toNums = new Dictionary(); var fromNums = new Dictionary(); foreach (var a in A) foreach(var c in a) { if (!toNums.ContainsKey(c)) { toNums[c] = N; fromNums[N] = c; N++; } } foreach (var b in B) foreach (var c in b) { if (!toNums.ContainsKey(c)) { toNums[c] = N; fromNums[N] = c; N++; } } var graph = new HashSet[N]; for (int i = 0; i < N; i++) graph[i] = new HashSet(); foreach (var a in A) for(int i = 0; i < a.Length - 1; i++) graph[toNums[a[i]]].Add(toNums[a[i + 1]]); foreach (var b in B) for (int i = 0; i < b.Length - 1; i++) graph[toNums[b[i]]].Add(toNums[b[i + 1]]); var indegs = new int[N]; for (int i = 0; i < N; i++) foreach (var v in graph[i]) indegs[v]++; var stk = new Stack(); for (int i = 0; i < N; i++) if (indegs[i] == 0) stk.Push(i); if (stk.Count() != 1) { cw.WriteLine(-1); return; } var dag = new List(); while(stk.Count() > 0) { var u = stk.Pop(); dag.Add(u); if (graph[u].Count() > 1) { cw.WriteLine(-1); return; } foreach (var v in graph[u]) { indegs[v]--; if (indegs[v] == 0) stk.Push(v); } } var ans = ""; for (int i = 0; i < dag.Count(); i++) ans += fromNums[dag[i]]; cw.WriteLine(ans); } } } #region Dependency resolution namespace TopoSort.Problems { internal partial class Problemyc517 { static ConsoleReader cr; static ConsoleWriter cw; #if COMPETITIVE public Problemyc517(string outputFilePath = null, bool solving = true) #else static void Main(string[] args) #endif { #if COMPETITIVE SourceExpander.Expander.Expand(outputFilePath: outputFilePath); #endif if (cw != null) cw.Dispose(); cr = new ConsoleReader(); cw = new ConsoleWriter(); #if COMPETITIVE if (solving) #endif Solve(); cw.Dispose(); } } } #endregion #region Expanded by https://github.com/kzrnm/SourceExpander namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[MI(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[MI(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[MI(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len=len)FillNextBuffer();return buf[pos++];}[MI(256)]public T Read(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw();}static T Throw()=>throw new NotSupportedException(typeof(T).Name);[MI(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[MI(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[MI(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[MI(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[MI(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[MI(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[MI(256)]public string String(){var sb=new List();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[MI(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[MI(256)]public int Int0()=>Int()-1;[MI(256)]public uint UInt0()=>UInt()-1;[MI(256)]public long Long0()=>Long()-1;[MI(256)]public ulong ULong0()=>ULong()-1;[MI(256)]public static implicit operator int(_R cr)=>cr.Int();[MI(256)]public static implicit operator uint(_R cr)=>cr.UInt();[MI(256)]public static implicit operator long(_R cr)=>cr.Long();[MI(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[MI(256)]public static implicit operator double(_R cr)=>cr.Double();[MI(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[MI(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat(int count){var arr=new T[count];for(int i=0;i();return arr;}}} namespace Kzrnm.Competitive.IO{using _W=ConsoleWriter;using MI=System.Runtime.CompilerServices.MethodImplAttribute;public sealed partial class ConsoleWriter:IDisposable{private const int BufSize=1<<12;private readonly StreamWriter sw;public StreamWriter StreamWriter=>sw;public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,BufSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){sw=new StreamWriter(output,encoding,bufferSize);}[MI(256)]public void Flush()=>sw.Flush();[MI(256)]public void Dispose()=>Flush();[MI(256)]public _W Write(T v){sw.Write(v.ToString());return this;}[MI(256)]public _W WriteLine(){sw.WriteLine();return this;}[MI(256)]public _W WriteLine(T v){sw.WriteLine(v.ToString());return this;}[MI(256)]public _W WriteLineJoin(IEnumerablecol)=>WriteMany(' ',col);[MI(256)]public _W WriteLineJoin((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);[MI(256)]public _W WriteLineJoin((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);[MI(256)]public _W WriteLineJoin((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);[MI(256)]public _W WriteLineJoin(TTuple tuple)where TTuple:System.Runtime.CompilerServices.ITuple{var col=new object[tuple.Length];for(int i=0;iWriteMany(' ',col);[MI(256)]public _W WriteLineJoin(T1 v1,T2 v2){sw.Write(v1.ToString());sw.Write(' ');sw.WriteLine(v2.ToString());return this;}[MI(256)]public _W WriteLineJoin(T1 v1,T2 v2,T3 v3){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.WriteLine(v3.ToString());return this;}[MI(256)]public _W WriteLineJoin(T1 v1,T2 v2,T3 v3,T4 v4){sw.Write(v1.ToString());sw.Write(' ');sw.Write(v2.ToString());sw.Write(' ');sw.Write(v3.ToString());sw.Write(' ');sw.WriteLine(v4.ToString());return this;}[MI(256)]public _W WriteLines(IEnumerablecol)=>WriteMany('\n',col);[MI(256)]public _W WriteGrid(IEnumerable>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[MI(256)]public _W WriteGrid(IEnumerabletuples)where TTuple:System.Runtime.CompilerServices.ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[MI(256)]private _W WriteMany(char sep,IEnumerablecol){var en=col.GetEnumerator();if(!en.MoveNext())goto End;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}End:sw.WriteLine();return this;}}} namespace Kzrnm.Competitive.IO{using MI=System.Runtime.CompilerServices.MethodImplAttribute;public partial class ConsoleWriter{[MI(256)]public ConsoleWriter WriteLine(ReadOnlySpanv){sw.WriteLine(v);return this;}[MI(256)]public ConsoleWriter WriteLineJoin(Spancol)=>WriteMany(' ',(ReadOnlySpan)col);[MI(256)]public ConsoleWriter WriteLineJoin(ReadOnlySpancol)=>WriteMany(' ',col);[MI(256)]public ConsoleWriter WriteLines(Spancol)=>WriteMany('\n',(ReadOnlySpan)col);[MI(256)]public ConsoleWriter WriteLines(ReadOnlySpancol)=>WriteMany('\n',col);[MI(256)]private ConsoleWriter WriteMany(char sep,ReadOnlySpancol){var en=col.GetEnumerator();if(!en.MoveNext())return this;sw.Write(en.Current.ToString());while(en.MoveNext()){sw.Write(sep);sw.Write(en.Current.ToString());}sw.WriteLine();return this;}}} namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander