#include using namespace std; typedef int ll; typedef pair P; #define each(i,a) for (auto&& i : a) #define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++) #define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) RFOR(i,0,n) #define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME #define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__) #define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__) #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define chmin(x,v) x = min(x, v) #define chmax(x,v) x = max(x, v) const ll linf = 1e18; const double eps = 1e-12; const double pi = acos(-1); template istream& operator>>(istream& is, vector& vec) { each(x,vec) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& vec) { rep(i,vec.size()) { if (i) os << " "; os << vec[i]; } return os; } template ostream& operator<<(ostream& os, const vector< vector >& vec) { rep(i,vec.size()) { if (i) os << endl; os << vec[i]; } return os; } void scc_dfs(ll v, vector& used, vector& vs, const vector>& G) { used[v] = true; each(to, G[v]) { if (!used[to]) scc_dfs(to, used, vs, G); } vs.pb(v); } void scc_rdfs(ll v, ll k, vector& used, vector& cmp, const vector>& rG) { used[v] = true; cmp[v] = k; each(to, rG[v]) { if (!used[to]) scc_rdfs(to, k, used, cmp, rG); } } // cmpが返る // 同じcmpは強連結成分 // cmp[i] < cmp[j] なら j から i に行けない vector scc(const vector>& G) { const ll n = G.size(); vector used(n, false); vector vs; rep(i, n) { if (!used[i]) scc_dfs(i, used, vs, G); } used.assign(n, false); vector> rG(n); rep(i, n) { each(to, G[i]) { rG[to].pb(i); } } vector res(n); ll k = 0; rrep(i, vs.size()) { if (!used[vs[i]]) scc_rdfs(vs[i], k++, used, res, rG); } return res; } vector> get_scc_graph(const vector& cmp, const vector>& G) { vector> res(*max_element(all(cmp))+1); rep(i, G.size()) { each(to, G[i]) { if (cmp[i] != cmp[to]) { res[cmp[i]].pb(cmp[to]); } } } rep(i, res.size()) { sort(all(res[i])); res[i].erase(unique(all(res[i])), res[i].end()); } return res; } class Sat { ll n; vector> G; ll node_id(ll id, bool b) const { return id * 2 + b; } public: Sat(ll size) : n(size), G(size*2) {} // (id1, b1) => (id2, b2) void add(ll id1, bool b1, ll id2, bool b2) { // cout << "add: " << id1 << " " << b1 << " " << id2 << " " << b2 << endl; G[node_id(id1, b1)].pb(node_id(id2, b2)); G[node_id(id2, !b2)].pb(node_id(id1, !b1)); } bool check() const { vector cmp = scc(G); rep(i, n) { if (cmp[node_id(i, true)] == cmp[node_id(i, false)]) { return false; } } return true; } vector solve() const { assert( check() ); vector cmp = scc(G); vector used(n, false), res(n); vector

v; rep(i, 2*n) v.eb(cmp[i], i); sort(all(v), greater

()); stack S; each(p, v) { ll i = p.second; if (used[i/2]) continue; used[i/2] = true; S.push(i); while ( !S.empty() ) { ll v = S.top(); S.pop(); res[v/2] = v & 1; each(to, G[v]) { if (used[to/2]) continue; used[to/2] = true; S.push(to); } } } return res; } }; int main() { // { // Sat sat(3); // sat.add(0, true, 1, false); // sat.add(1, false, 1, true); // sat.add(2, true, 0, true); // cout << sat.solve() << endl; // return 0; // } ios::sync_with_stdio(false); cin.tie(0); ll n; cin >> n; vector s(n); cin >> s; Sat sat(9*n); ll idx = n; map>> m; rep(i, n) { m[s[i].substr(0, 1)].eb(i, false); m[s[i].substr(1, 2)].eb(i, false); m[s[i].substr(0, 2)].eb(i, true); m[s[i].substr(2, 1)].eb(i, true); } each(p, m) { // left rep(i, 1, p.second.size()) { sat.add(idx+i, true, idx+i-1, true); } rep(i, p.second.size()) { bool b = p.second[i].second; if (i > 0) sat.add(p.second[i].first, b, idx+i-1, true); sat.add(idx+i, true, p.second[i].first, !b); } idx += p.second.size(); // right rep(i, 1, p.second.size()) { sat.add(idx+i-1, true, idx+i, true); } rep(i, p.second.size()) { bool b = p.second[i].second; if (i+1 < p.second.size()) sat.add(p.second[i].first, b, idx+i+1, true); sat.add(idx+i, true, p.second[i].first, !b); } idx += p.second.size(); } if (!sat.check()) { cout << "Impossible" << endl; } else { vector ans = sat.solve(); rep(i, n) { if (!ans[i]) { cout << s[i].substr(0, 1) << " " << s[i].substr(1, 2) << '\n'; } else { cout << s[i].substr(0, 2) << " " << s[i].substr(2, 1) << '\n'; } } cout << flush; } }