use std::io::{self, BufRead};
use itertools::Itertools;

fn read_input() -> Vec<(String, String)> {
    let stdin = io::stdin();

    stdin.lock().lines()
        .map(|line| line.unwrap().split(')').map(|s| s.to_string())
             .next_tuple().unwrap()
        ).collect()
}

#[derive(Clone, Debug)]
struct Tree {
    name: String,
    children: Vec<Tree>,
}

impl Tree {
    fn new(name: &str) -> Self {
        Tree {
            name: name.to_string(),
            children: Vec::new(),
        }
    }

    fn new_with_one(name: &str, tree: Tree) -> Self {
        Tree {
            name: name.to_string(),
            children: vec![tree],
        }
    }

    fn join(&mut self, mut tree:Tree) -> bool {
        if self.name == tree.name {
            self.children.append(&mut tree.children);
            true
        } else {
            for c in &mut self.children {
                if c.contains(&tree.name) {
                    c.join(tree);
                    return true;
                }
            }
            false
        }
    }

    fn contains(&self, needle:&str) -> bool {
        if &self.name == needle {
            return true;
        }

        for c in &self.children {
            if c.contains(needle) {
                return true;
            }
        }

        false
    }

    fn orbit_count(&self) -> usize {
        fn orbit_count_internal(t: &Tree, s:usize) -> usize {
            let mut n = s;
                for c in &t.children {
                    n += orbit_count_internal(c, s + 1);
                }
            n
        }

        orbit_count_internal(self, 0)
    }

    fn find_distance(&self, to: &str) -> Option<usize> {
        fn find_distance_internal(t:&Tree, p: &str, s:usize) -> usize {
            for c in &t.children {
                if c.contains(p) {
                    return find_distance_internal(c, p, s + 1);
                }
            }

            s
        }

        if self.contains(to) {
            Some(find_distance_internal(self, to , 0))
        } else {
            None
        }
    }

    fn last_common_ancestor(&self, from: &str, to: &str) -> Option<Tree> {
        fn ancestor_internal(t: &Tree, from: &str, to: &str) -> Option<Tree> {
            if t.contains(from) && t.contains(to) {
                for c in &t.children {
                    if c.contains(from) && c.contains(to) {
                        return ancestor_internal(c, from, to);
                    }
                }
                Some(t.clone())
            } else {
                None
            }
        }

        ancestor_internal(self, from, to)
    }
}

fn build_tree(orbit_map: Vec<(String, String)>) -> Option<Tree> {
    let mut trees:Vec<Tree> = Vec::new();

    for (parent, child) in &orbit_map {
        let mut found = false;

        for t in &mut trees {
            if t.contains(parent) {
                let newtree = Tree::new_with_one(parent, Tree::new(child));
                found = t.join(newtree);
                break;
            }
        }

        if ! found {
            let newtree = Tree::new_with_one(parent, Tree::new(child));
            trees.push(newtree);
        }
    }

    while {
        let last_len = trees.len();

        let mut i = 0;
        while i < trees.len() {
            let mut one = trees.remove(i);
            let mut j = 0;
            while j < trees.len() {
                let mut two = trees.remove(j);
                if one.contains(&two.name) {
                    one.join(two);
                } else if two.contains(&one.name) {
                    two.join(one);
                    one = two;
                } else {
                    trees.push(two);
                }
                j += 1;
            }
            trees.push(one);
            i += 1;
        }
        trees.len() != last_len
    } {}

    if trees.len() == 1 {
        trees.pop()
    } else {
        None
    }
}

fn first_puzzle(tree: &Tree) {
    println!("Solution to first part: {}.", tree.orbit_count());
}

fn second_puzzle(tree: &Tree, from: &str, to: &str) {
    let junction = tree.last_common_ancestor(from, to);

    let distance = match junction {
        Some(j) => 
            j.find_distance(from).expect("Not reachable.") +
            j.find_distance(to).expect("Not reachable.") - 2,
        None    => panic!("No path between {} and {}.", from, to),
    };

    println!("Solution to second part: {}.", distance);
}

fn main() {
    let orbit_map = read_input();

    let tree = build_tree(orbit_map.clone());

    match &tree {
        Some(t) => {
            first_puzzle(t);
            second_puzzle(t, "YOU", "SAN");
        },
        None =>    panic!("Could not make sense of orbit map.")
    }


}