class Digraph: """重み[なし]有向グラフを生成する. """ #入力定義 def __init__(self,vertex=[]): self.vertex=set(vertex) self.edge_number=0 self.vertex_number=len(vertex) self.adjacent_out={v:set() for v in vertex} #出近傍(vが始点) self.adjacent_in={v:set() for v in vertex} #入近傍(vが終点) #頂点の追加 def add_vertex(self,*adder): for v in adder: if not self.vertex_exist(v): self.adjacent_in[v]=set() self.adjacent_out[v]=set() self.vertex.add(v) self.vertex_number+=1 #辺の追加 def add_edge(self,From,To): self.add_vertex(From) self.add_vertex(To) if To not in self.adjacent_out[From]: self.adjacent_out[From].add(To) self.adjacent_in[To].add(From) self.edge_number+=1 #辺を除く def remove_edge(self,From,To): self.add_vertex(From) self.add_vertex(To) if To in self.adjacent_out[From]: self.adjacent_out[From].discard(To) self.adjacent_in[To].discard(From) self.edge_number-=1 #頂点を除く def remove_vertex(self,*vertexes): for v in vertexes: if v in self.vertex: self.vertex_number-=1 for u in self.adjacent_out[v]: self.adjacent_in[u].discard(v) self.edge_number-=1 del self.adjacent_out[v] for u in self.adjacent_in[v]: self.adjacent_out[u].discard(v) self.edge_number-=1 del self.adjacent_in[v] self.vertex.discard(v) #Walkの追加 def add_walk(self,*walk): N=len(walk) for k in range(N-1): self.add_edge(walk[k],walk[k+1]) #Cycleの追加 def add_cycle(self,*cycle): self.add_walk(*cycle) self.add_edge(cycle[-1],cycle[0]) #頂点の交換 def __vertex_swap(self,p,q): self.vertex.sort() #グラフに頂点が存在するか否か def vertex_exist(self,v): return v in self.vertex #グラフに辺が存在するか否か def edge_exist(self,From,To): if self.vertex_exist(From) and self.vertex_exist(To): return False return To in self.adjacent_out[From] #近傍 def neighbohood(self,v): """vの出近傍, 入近傍を出力する. Input: v:頂点 Output: (出近傍, 入近傍) """ if not self.vertex_exist(v): return (set(),set()) return (self.adjacent_out[v],self.adjacent_in[v]) #出次数 def out_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_out[v]) #入次数 def in_degree(self,v): if not self.vertex_exist(v): return 0 return len(self.adjacent_in[v]) #次数 def degree(self,v): return (self.out_degree(v),self.in_degree(v)) #頂点数 def vertex_count(self): return self.vertex_number #辺数 def edge_count(self): return self.edge_number #頂点vに到達可能な頂点 def reachable_to(self,v): if not self.vertex_exist(v): return [] from collections import deque T={v:0 for v in self.vertex} T[v]=1 Q=deque([v]) while Q: x=Q.popleft() for y in self.adjacent_in[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in self.vertex if T[x]] #頂点vから到達可能な頂点 def reachable_from(self,v): if not self.vertex_exist(v): return [] from collections import deque T={v:0 for v in self.vertex} T[v]=1 Q=deque([v]) while Q: x=Q.popleft() for y in self.adjacent_out[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in self.vertex if T[x]] #深いコピー def deepcopy(self): from copy import deepcopy D=Digraph() D.vertex=deepcopy(self.vertex) D.edge_number=self.edge_number D.vertex_number=len(self.vertex) D.adjacent_out=deepcopy(self.adjacent_out) D.adjacent_in=deepcopy(self.adjacent_in) return D #Warshall–Floyd def Warshall_Floyd(D): """Warshall–Floyd法を用いて,全点間距離を求める. D:負Cycleを含まない有向グラフ """ T={v:{} for v in D.vertex} #T[u][v]:uからvへ for u in D.vertex: for v in D.vertex: if v==u: T[u][v]=0 elif v in D.adjacent_out[u]: T[u][v]=1 else: T[u][v]=float("inf") for u in D.vertex: for v in D.vertex: for w in D.vertex: T[v][w]=min(T[v][w],T[v][u]+T[u][w]) return T def Dijkstra(D,From,To,with_path=False): """Dijksta法を用いて,FromからToまでの距離を求める. D:辺の重みが全て非負の有向グラフ From:始点 To:終点 with_path:最短路も含めて出力するか? (出力の結果) with_path=True->(距離,最短経路の辿る際の前の頂点) with_path=False->距離 """ from copy import copy from heapq import heappush,heappop T={v:float("inf") for v in D.vertex} T[From]=0 if with_path: Prev={v:None for v in D.vertex} Q=[(0,From)] Flag=False while Q: c,u=heappop(Q) if u==To: Flag=True break if T[u]T[u]+1: T[v]=T[u]+1 heappush(Q,(T[v],v)) if with_path: Prev[v]=u if not Flag: if with_path: return (float("inf"),None) else: return float("inf") if with_path: path=[To] u=To while (Prev[u]!=None): u=Prev[u] path.append(u) return (T[To],path[::-1]) else: return T[To] #================================================ S="" N=int(input()) A=[] for _ in range(N): A.append(input()) S+=A[-1] M=int(input()) B=[] for _ in range(M): B.append(input()) D=Digraph(S) for alpha in A: for i in range(len(alpha)-1): D.add_edge(alpha[i],alpha[i+1]) for beta in B: for j in range(len(beta)-1): D.add_edge(beta[j],beta[j+1]) X=Warshall_Floyd(D) flag=0 for s in S: for t in S: if X[s][t]==len(S)-1: flag+=1 i,j=s,t if flag!=1: print(-1) exit() _,A=Dijkstra(D,i,j,True) print("".join(A))