#[allow(unused_imports)] use std::cmp::{max, min, Ordering}; #[allow(unused_imports)] use std::collections::{HashMap, HashSet}; mod util { use std::io::stdin; use std::str::FromStr; use std::fmt::Debug; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn get() -> T where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().parse().unwrap() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn get2() -> (T, U) where ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } #[allow(dead_code)] pub fn get3() -> (S, T, U) where ::Err: Debug, ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } } // std::cmp::Reverse doesn't have Clone. #[derive(Eq, PartialEq, Clone)] struct Rev(pub T); impl PartialOrd for Rev { fn partial_cmp(&self, other: &Rev) -> Option { other.0.partial_cmp(&self.0) } } impl Ord for Rev { fn cmp(&self, other: &Rev) -> Ordering { other.0.cmp(&self.0) } } #[allow(unused_macros)] macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } } fn dfs( u: &[Vec], i: usize, ans: &mut Vec<(String, String)>, memo: &mut HashSet, ) -> bool { if i == u.len() { return true; } for k in 1..3 { let l: String = u[i][..k].iter().cloned().collect(); let r: String = u[i][k..].iter().cloned().collect(); if !memo.contains(&l) && !memo.contains(&r) { memo.insert(l.clone()); memo.insert(r.clone()); ans.push((l.clone(), r.clone())); if dfs(u, i + 1, ans, memo) { return true; } else { ans.pop(); memo.remove(&l); memo.remove(&r); } } if u[i][0] == u[i][2] { break; } } return false; } fn main() { let n: (usize) = util::get(); let u: Vec> = (0..n).map(|_| util::line().chars().collect()).collect(); let mut ans = Vec::new(); if dfs(&u, 0, &mut ans, &mut HashSet::new()) { for &(ref a, ref b) in &ans { println!("{} {}", a, b); } } else { println!("Impossible"); } }