#include using namespace std; class SCC{ private: int nV; vector> G; vector> rG; vector vs; vector used; void dfs(int v){ used[v] = true; for (auto u: G[v]) if (not used[u]) dfs(u); vs.push_back(v); } void rdfs(int v, int k){ used[v] = true; cmp[v] = k; for (auto u: rG[v]) if (not used[u]) rdfs(u, k); } public: vector cmp; SCC(const vector>& _G): nV(_G.size()), G(_G), rG(nV,vector()), vs(), used(nV, false), cmp(nV, 0){ for (int from = 0; from < nV; ++from) for (auto to : G[from]) rG[to].push_back(from); for (int v = 0; v < nV; ++v) if (not used[v]) dfs(v); used.assign(nV, false); int k = 0; for (auto rit = vs.rbegin(); rit != vs.rend(); ++rit){ if (not used[*rit]) rdfs(*rit, k++); } } }; pair> TwoSAT(const vector> &Es){ // vertex 0..n-1 : variable[i] = true // vertex n..2*n-1 : variable[i] = false // return value: bool: 2SAT can be satisfied or not // return value: vector: One solution which satisfies the SAT. assert(Es.size() % 2 == 0); int n = Es.size() / 2; vector sol(n, false); SCC scc(Es); for (int i = 0; i < n; ++i) if (scc.cmp[i] == scc.cmp[i + n]) return make_pair(false, sol); for (int i = 0; i < n; ++i) sol[i] = scc.cmp[i] > scc.cmp[i + n]; return make_pair(true, sol); } int main(){ int N; cin >> N; if (N > 52){ cout << "Impossible" << endl; return 0; } vector Us(N); for (auto &U : Us) cin >> U; vector> Es(2 * N, vector()); for (int i = 0; i < N - 1; ++i){ char a = Us[i][0]; char b = Us[i][1]; char c = Us[i][2]; for (int j = i + 1; j < N; ++j){ char d = Us[j][0]; char e = Us[j][1]; char f = Us[j][2]; // a + bc と分割するとき(頂点 i に対応) // d + ef と分割したときに重複が発生するか否か if ((a == d) or (b == e and c == f)){ // 重複する場合 Es[i].push_back(j + N); // a+bc としたならば de+f とすることが必要 Es[j].push_back(i + N); // d+ef としたならば ab+c とすることが必要 } // a + bc と分割するとき(頂点 i に対応) // de + f と分割したときに重複が発生するか否か if ((a == f) or (b == d and c == e)){ // 重複する場合 Es[i].push_back(j); // a+bc としたならば d+ef とすることが必要 Es[j + N].push_back(i + N); // de+f としたならば ab+c とすることが必要 } // ab + c と分割するとき(頂点 i に対応) // d + ef と分割したときに重複が発生するか否か if ((c == d) or (a == e and b == f)){ // 重複する場合 Es[i + N].push_back(j + N); // ab+c としたならば de+f とすることが必要 Es[j].push_back(i); // d+ef としたならば a+bc とすることが必要 } // ab + c と分割するとき(頂点 i に対応) // de + f と分割したときに重複が発生するか否か if ((c == f) or (a == d and b == e)){ // 重複する場合 Es[i + N].push_back(j); // ab+c としたならば d+ef とすることが必要 Es[j + N].push_back(i); // de+f としたならば a+bc とすることが必要 } } } auto result = TwoSAT(Es); if (result.first == false){ cout << "Impossible" << endl; }else{ int i = 0; for (auto tf: result.second){ if (tf){ cout << Us[i][0] << ' ' << Us[i][1] << Us[i][2] << '\n'; }else{ cout << Us[i][0] << Us[i][1] << ' ' << Us[i][2] << '\n'; } ++i; } } return 0; }