#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 (abool chmin(T &a, const T &b) { return (bEPS=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...) 0 //{ 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){ 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); }; rep(v,n) if(ord[v]==-1) dfs(v,-1,k); return make_tuple(scc,ord); } // 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 scc,ord; tie(scc,ord) = strongly_connected_components(graph); rep(i,n){ if(scc[2*i] == scc[2*i+1]) ret[0] = -1; else{ // T -> F というトポロジカル順序 ret[i] = (ord[2*i+1] < ord[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); 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; }