#include using namespace std; struct StronglyConnectedComponent { const int V; vector> G, revG; vector id; StronglyConnectedComponent(const int V) : V(V), G(vector>(V, vector())), revG(vector>(V, vector())), id(vector(V)) {} void addEdge(int from, int to) { G[from].push_back(to); revG[to].push_back(from); } void build() { vector used(V, false); stack st; for(int from = 0; from < V; ++from) { if(not used[from]) { dfs(from, used, st); } } int num = 0; while(st.size()) { int from = st.top(); st.pop(); if(used[from]) { revdfs(from, num, used); ++num; } } } void dfs(int from, vector &used, stack &st) { used[from] = true; for(int to : G[from]) { if(not used[to]) { dfs(to, used, st); } } st.push(from); } void revdfs(int from, int num, vector &used) { used[from] = false; id[from] = num; for(int to : revG[from]) { if(used[to]) { revdfs(to, num, used); } } } int get(int x) { return id[x]; } }; struct TwoSatisfiability { const int V; vector> G; vector pos; StronglyConnectedComponent scc; TwoSatisfiability(const int V) : V(V), G(vector>(2 * V, vector())), pos(vector(2 * V)), scc(StronglyConnectedComponent(2 * V)) {} inline int NOT(int A) { return (A + V) % (2 * V); } // A -> B <=> not B -> not A inline void addIF(int A, bool Apos, int B, bool Bpos) { if(not Apos) A = NOT(A); if(not Bpos) B = NOT(B); scc.addEdge(A, B); // A -> B scc.addEdge(NOT(B), NOT(A)); // not B -> not A } // A <=> (not A -> A) void addUNARY(int A, bool Apos) { addIF(A, not Apos, A, Apos); // not A -> A } // A or B <=> not A -> B void addOR(int A, bool Apos, int B, bool Bpos) { addIF(A, not Apos, B, not Bpos); // not A -> B } // not(A and B) => A -> not B void addNAND(int A, bool Apos, int B, bool Bpos) { addIF(A, Apos, B, not Bpos); // A -> not B } // A xor B <=> not(A and B) and not(not A and not B) void addXOR(int A, bool Apos, int B, bool Bpos) { addNAND(A, Apos, B, Bpos); // not(A and B) addNAND(A, not Apos, B, not Bpos); // not(not A and not B) } // not(A xor B) <=> A xor not B void addXNOR(int A, bool Apos, int B, bool Bpos) { addXOR(A, Apos, B, not Bpos); // A xor not B } bool solve() { scc.build(); for(int i = 0; i < V; ++i) { if(scc.get(i) == scc.get(i + V)) { return false; } pos[i] = (scc.get(i) > scc.get(i + V)); } return true; } bool get(int x) { return pos[x]; } }; int main() { int n; cin >> n; string u[n]; for(int i = 0; i < n; ++i) { cin >> u[i]; } if(n > 100) { cout << "Impossible" << '\n'; return 0; } TwoSatisfiability sat(n); for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { for(int mask = 0; mask < (1 << 2); ++mask) { bool ipos = (mask & 1); bool jpos = ((mask >> 1) & 1); int sin = 1; if(not ipos) { sin = 2; } int sjn = 1; if(not jpos) { sjn = 2; } set st; st.insert(u[i].substr(0, sin)); st.insert(u[i].substr(sin)); st.insert(u[j].substr(0, sjn)); st.insert(u[j].substr(sjn)); if(st.size() < 4) { sat.addNAND(i, ipos, j, jpos); } } } } if(not sat.solve()) { cout << "Impossible" << '\n'; return 0; } for(int i = 0; i < n; ++i) { if(sat.get(i)) { cout << u[i].substr(0, 1) << " " << u[i].substr(1) << '\n'; } else { cout << u[i].substr(0, 2) << " " << u[i].substr(2) << '\n'; } } return 0; }