#include #define _overload(_1,_2,_3,name,...) name #define _rep(i,n) _range(i,0,n) #define _range(i,a,b) for(int i=int(a);i=int(b);--i) #define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__) #define _all(arg) begin(arg),end(arg) #define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg)) #define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary) #define clr(a,b) memset((a),(b),sizeof(a)) #define bit(n) (1LL<<(n)) #define popcount(n) (__builtin_popcountll(n)) using namespace std; templatebool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;} templatebool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;} using ll = long long; using R = long double; const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7 inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);} inline R sq(R x) {return sqrt(max(x, 0.0L));} const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; // Problem Specific Parameter: #define error(args...) {} //{ vector _debug = split(#args, ',');err(begin(_debug), args);} vector split(const string& s, char c) { vector v; stringstream ss(s); string x; while (getline(ss, x, c)) v.emplace_back(x); return move(v); } void err(vector::iterator it) {cerr << endl;} template void err(vector::iterator it, T a, Args... args) { cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ", err(++it, args...); } // Description: 2-SAT // Verifyed: Many Diffrent Problem // Required: 有向グラフに対する強連結成分 //Appropriately Changed using edge = struct {int to;}; using G = vector>; //Appropriately Changed void add_edge(G &graph, int from, int to) { error(from, to); graph[from].push_back({to}); } // Description: 有向グラフに対する強連結成分 // TimeComplexity: $ \mathcal{O}(V + E) $ // Verifyed: AOJ GRL_3_C auto strongly_connected_components(const G& graph,vector &topolgy) { int n = graph.size(), k = 0; vector par(n), ord(n, -1), low(n), scc(n, -1), res; stack s; auto dfs = [&](int v, int p, int &k) { auto func = [&](int v, int p, int &k, auto func)->void{ ord[v] = k++, low[v] = ord[v], par[v] = p, s.push(v); for (auto &e : graph[v]) { if (scc[e.to] != -1) continue; if (ord[e.to] == -1) { func(e.to, v, k, func); chmin(low[v], low[e.to]); } else chmin(low[v], ord[e.to]); } if (ord[v] != low[v]) return ; while (1) { int u = s.top(); s.pop(); scc[u] = v; if (u == v) break; } }; return func(v, p, k, func); }; for(auto &v:topolgy) if (ord[v] == -1) dfs(v, -1, k); return make_tuple(scc, ord); } // Description: 有向グラフに対するトポロジカルソート // TimeComplexity: $ \mathcal{O}(V + E) $ // Verifyed: AOJ GRL_4_B auto topological_sort(const G& graph){ const int n=graph.size(); vector used(n,0),order; auto dfs=[&](int v){ auto func=[&](int v,auto func)->void{ used[v]=true; for(auto &e:graph[v]) if(!used[e.to]) func(e.to,func); order.push_back(v); }; return func(v,func); }; rep(v,n)if(!used[v]) dfs(v); reverse(_all(order)); return order; } // x&1 == 1 True // x&1 == 0 False void closure_or(G &graph, int a, int b) { add_edge(graph, a ^ 1, b); add_edge(graph, b ^ 1, a); } auto get_variable(G &graph) { const int n = graph.size() / 2; vector ret(n, 0); vector topolgy = topological_sort(graph); vector scc, ord; tie(scc, ord) = strongly_connected_components(graph,topolgy); rep(i, 2 * n) error(scc[i], ord[i]); rep(i, n) { if (scc[2 * i] == scc[2 * i + 1]) ret[0] = -1; else { // F -> T というトポロジカル順序 // 理由 F を満たすと、Tを満たすとなるためアウト ret[i] = (scc[2 * i + 1] > scc[2 * i]); } } return ret; } string s[1010]; int main(void) { int n; cin >> n; const int limit = 52; if (n > limit * limit) { puts("Impossible"); return 0; } rep(i, n) cin >> s[i]; G graph(2 * n); // F a | bc // T ab | c rep(i, n)rep(j, i) { // F F if (s[i].substr(0, 1) == s[j].substr(0, 1) or s[i].substr(1, 2) == s[j].substr(1, 2)) { error(i, "F", j, "F"); closure_or(graph, 2 * i + 1, 2 * j + 1); } // T F if (s[i].substr(2, 1) == s[j].substr(0, 1) or s[i].substr(0, 2) == s[j].substr(1, 2)) { error(i, "T", j, "F"); closure_or(graph, 2 * i, 2 * j + 1); } // F T if (s[i].substr(0, 1) == s[j].substr(2, 1) or s[i].substr(1, 2) == s[j].substr(0, 2)) { error(i, "F", j, "T"); closure_or(graph, 2 * i + 1, 2 * j); } // T T if (s[i].substr(2, 1) == s[j].substr(2, 1) or s[i].substr(0, 2) == s[j].substr(0, 2)) { error(i, "T", j, "T"); closure_or(graph, 2 * i, 2 * j); } } vector ret = get_variable(graph); if (ret[0] == -1) { puts("Impossible"); return 0; } rep(i, n) { error(ret[i]); if (ret[i]) cout << s[i][0] << s[i][1] << " " << s[i][2] << endl; else cout << s[i][0] << " " << s[i][1] << s[i][2] << endl; } return 0; }