from collections import deque import sys sys.setrecursionlimit(10**7) N=int(input()) A=[] for _ in range(N): S=input() a,b,c,d=S[:1],S[1:],S[:2],S[2:] A.append((a,b,c,d)) def scc(N, G, RG): order = [] used = [0]*N def dfs(s): used[s] = 1 for t in G[s]: if not used[t]: dfs(t) order.append(s) for i in range(N): if not used[i]: dfs(i) group = [-1]*N label = 0 order.reverse() for s in order: if group[s] != -1: continue que = deque([s]) group[s] = label while que: v = que.popleft() for w in RG[v]: if group[w] != -1: continue que.append(w) group[w] = label label += 1 return group # topological ordering G = [[] for i in range(2*N)] RG = [[] for i in range(2*N)] # add (a ∨ b) # a = x_i if neg_i = 0 # a = ~x_i if neg_i = 1 def add_edge(i, neg_i, j, neg_j): if neg_i: i0 = i+N; i1 = i else: i0 = i; i1 = i+N if neg_j: j0 = j+N; j1 = j else: j0 = j; j1 = j+N # add (~a ⇒ b) G[i1].append(j0); RG[j0].append(i1) # add (~b ⇒ a) G[j1].append(i0); RG[i0].append(j1) # check if the formula is satisfiable def check(group): for i in range(N): if group[i] == group[i+N]: return False return True # assign values to variables def assign(group): res = [0]*N for i in range(N): if group[i] > group[i+N]: res[i] = 1 return res G=[[] for i in range(2*N)]; RG=[[] for i in range(2*N)] for i in range(N-1): for j in range(i+1,N): a,b,c,d=A[i];aa,bb,cc,dd=A[j] e=0 D=[a,b,aa,bb] if len(D)!=len(set(D)): add_edge(i,0,j,0) e+=1 D=[a,b,cc,dd] if len(D)!=len(set(D)): add_edge(i,0,j,1) e+=1 D=[c,d,aa,bb] if len(D)!=len(set(D)): add_edge(i,1,j,0) e+=1 D=[c,d,cc,dd] if len(D)!=len(set(D)): add_edge(i,1,j,1) e+=1 if e==4: print('Impossible') exit() B=scc(2*N, G, RG) for i in range(N): if B[i]==B[i+N]: print('Impossible') exit() for i in range(N): if B[i]