package invsplust; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) { IO io = new IO(); int n = io.nextInt(); String[] u = new String[n]; for(int i=0;i> 1) & 1; int l2 = k & 1; String s1 = u1.substring(0, l1 + 1); String t1 = u1.substring(l1 + 1, 3); String s2 = u2.substring(0, l2 + 1); String t2 = u2.substring(l2 + 1, 3); //(3文字なのでs1=t1やs2=t2はありえない) if (s1.equals(s2) || s1.equals(t2) || t1.equals(s2) || t1.equals(t2)) { //ダメなのでこの分割をしたとき0になるような節を追加する ts.addClause(l1 == 0, i, l2 == 0, j); } } } } boolean[] right = ts.solve(); if (right == null) { io.println("Impossible"); return; } for(int i=0;i (false, 0, true, 1) public void addClause(boolean tf1, int x1, boolean tf2, int x2) { // System.out.println((tf1 ? "" : "¬") + x1 + "∨" + (tf1 ? "" : "¬") + x2); graph.addEdge(x1 + (tf1 ? 0 : n), x2 + (tf2 ? n : 0)); //¬x1 -> x2 graph.addEdge(x2 + (tf2 ? 0 : n), x1 + (tf1 ? n : 0)); //¬x2 -> x1 } //充足不可能なときnull, そうでなければ真偽の割り当て public boolean[] solve() { graph.scc(); int[] order = graph.order; boolean[] res = new boolean[n]; for(int i=0;i order[i]) { res[i] = true; } } return res; } } class SCC { int n; ArrayList[] graph; //グラフ ArrayList[] rgraph; //逆辺からなるグラフ ArrayList vertices; //帰りがけ順に頂点を並べる boolean[] used; int[] order; //強連結成分のトポロジカル順序 int sccNum; @SuppressWarnings("unchecked") public SCC(int n) { this.n = n; graph = new ArrayList[n]; rgraph = new ArrayList[n]; for(int i=0;i(); rgraph[i] = new ArrayList<>(); } } public void addEdge(int from,int to) { // System.out.println(from + "->" + to); graph[from].add(to); rgraph[to].add(from); } private void dfs(int v) { used[v] = true; for(int u: graph[v]) { if (!used[u]) { dfs(u); } } vertices.add(v); } private void rdfs(int v, int k) { used[v] = true; order[v] = k; for(int u: rgraph[v]) { if (!used[u]) { rdfs(u, k); } } } public void scc() { used = new boolean[n]; order = new int[n]; vertices = new ArrayList<>(); sccNum = 0; for(int i=0;i=0;i--) { int v = vertices.get(i); if (!used[v]) { rdfs(v, sccNum++); } } } //scc()の後に呼び出して強連結成分をトポロジカル順序で返す @SuppressWarnings("unchecked") public ArrayList[] restoreSCCs() { ArrayList[] res = new ArrayList[sccNum]; for(int i=0;i(); } for(int i=0;i Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } public double nextDouble() { return Double.parseDouble(next());} public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i