use std::fmt;
use std::io::{self, BufRead};
use std::time::Instant;

struct Graph {
    size: usize,
    matrix: Vec<Vec<i32>>,
}

struct Cutset {
    cardinality: usize,
    vertices: Vec<i32>,
    graph: Graph,
}

impl Clone for Graph {
    fn clone(&self) -> Self {
        let mut matrix = vec![vec![0; self.size]; self.size];
        for row in 0..self.size {
            for col in 0..self.size {
                matrix[row][col] = self.matrix[row][col];
            }
        }
        return Graph {
            size: self.size,
            matrix,
        };
    }
}

impl fmt::Display for Graph {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for row in 0..self.size {
            for col in 0..self.size {
                write!(f, "{}", self.matrix[row][col])?;
                if col < self.size - 1 {
                    write!(f, " ")?;
                }
            }
            if row < self.size - 1 {
                write!(f, "\n")?;
            }
        }
        return Ok(());
    }
}

fn iterate(n: usize) -> Vec<Vec<i32>> {
    let mut components = Vec::new();

    let mut v: Vec<i32> = vec![0; n];
    loop {
        let mut sum: usize = 0;
        for i in &v {
            sum += *i as usize;
        }

        if sum == v.len() {
            break;
        }

        let mut k = 0;
        for i in 0..v.len() {
            if v[i] == 1 {
                v[i] = 0;
            } else {
                k = i;
                break;
            }
        }
        v[k] = 1;
        components.push(v.clone());
    }

    return components;
}

impl Graph {
    fn from_g6(line: &String) -> Graph {
        let mut chars: Vec<u8> = Vec::new();
        for character in line.chars() {
            chars.push((character as i32 - 63) as u8);
        }
        // TODO: spec allows multi-byte vector size
        let size = chars[0] as usize;
        let bytes = &chars[1..];

        let mut matrix: Vec<Vec<i32>> = vec![vec![0; size]; size];
        let mut i = 0;
        for col in 1..size {
            for row in 0..col {
                let bit: i32 = (bytes[i / 6] >> (5 - i % 6) & 1) as i32;
                matrix[row][col] = bit;
                matrix[col][row] = bit;
                i += 1;
            }
        }
        return Graph { size, matrix };
    }

    fn degree(&self, vertex: usize) -> usize {
        let mut sum: usize = 0;
        for i in &self.matrix[vertex] {
            sum += if *i == 0 { 0 } else { 1 } as usize;
        }
        return sum;
    }

    fn min_degree(&self) -> usize {
        let mut min = self.size + 1;
        for i in 0..self.size {
            let d = self.degree(i);
            if d < min {
                min = d;
            }
        }
        return min;
    }

    fn get_closure_traced(&self, trace_steps: bool) -> Graph {
        let mut step = if trace_steps { 2 } else { 1 };

        let mut closure = self.clone();
        for _ in 0..(closure.size * closure.size) {
            let mut changed = false;
            for row in 0..closure.size {
                for col in 0..closure.size {
                    if row == col || closure.matrix[row][col] != 0 {
                        continue;
                    }
                    let sum = closure.degree(row) + closure.degree(col);
                    if sum >= closure.size {
                        closure.matrix[row][col] = step;
                        if trace_steps {
                            step += 1;
                        }
                        changed = true;
                    }
                }
            }
            if !changed {
                break;
            }
        }
        return closure;
    }

    fn get_hamiltonian_cycle(&self) -> Vec<usize> {
        let closure = self.get_closure_traced(true);

        let mut cycle = Vec::new();
        for i in 0..self.size - 1 {
            cycle.push(i + 1);
        }
        cycle.push(0);

        loop {
            let mut start = 0;
            let mut m = 0;

            let mut end = start;
            let mut new_start = start;
            let mut current = start;
            loop {
                let next = cycle[current];
                let val = closure.matrix[current][next];
                // println!("{current} -> {next} = {val}");
                if val > m {
                    m = val;
                    end = current;
                    new_start = next;
                }
                current = next;
                if current == start {
                    break;
                }
            }
            if m == 1 {
                break;
            }
            // println!("New start: {new_start}, end: {end}, m = {m}");
            start = new_start;

            let mut s = start;
            let mut current = cycle[start];
            while current != end {
                let next = cycle[current];
                let u1 = closure.matrix[start][next];
                let u2 = closure.matrix[end][current];
                if u1 < m && u2 < m {
                    s = current;
                    break;
                }
                current = next;
            }
            // println!("s = {s}");

            let mut new_cycle = Vec::new();
            new_cycle.push(start);
            let mut current = cycle[s];
            while current != end {
                new_cycle.push(current);
                current = cycle[current];
            }
            new_cycle.push(end);
            {
                let mut tmp = Vec::new();
                let mut current = cycle[start];
                while current != s {
                    tmp.push(current);
                    current = cycle[current];
                }
                tmp.push(s);
                tmp.reverse();
                for i in tmp {
                    new_cycle.push(i);
                }
            }
            for i in 0..self.size - 1 {
                cycle[new_cycle[i]] = new_cycle[i + 1];
            }
            cycle[new_cycle[self.size - 1]] = new_cycle[0];
        }

        return cycle;
    }

    fn cutsets(&self) -> Vec<Cutset> {
        let mut cs = Vec::new();
        for vertices in iterate(self.size) {
            let mut g = self.clone();
            for vertice in 0..g.size {
                for i in 0..g.size {
                    if vertices[vertice] == 0 {
                        g.matrix[vertice as usize][i as usize] = 0;
                        g.matrix[i as usize][vertice as usize] = 0;
                    }
                }
            }
            let cardinality = vertices.iter().sum::<i32>() as usize;
            cs.push(Cutset {
                cardinality,
                vertices: vertices.clone(),
                graph: g,
            });
        }
        return cs;
    }

    fn max_independent_cutset(&self) -> Cutset {
        let mut max_cutset = None;
        for cutset in self.cutsets() {
            if cutset.graph.is_independent() {
                match &max_cutset {
                    None => max_cutset = Some(cutset),
                    Some(m_cutset) => {
                        if cutset.cardinality > m_cutset.cardinality {
                            max_cutset = Some(cutset);
                        }
                    }
                };
            }
        }
        return max_cutset.unwrap();
    }

    fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
        visited[*vertex] = 1;
        for i in 0..self.size {
            if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
                self.dfs(&i, visited);
            }
        }
        return;
    }

    fn count_components(&self) -> usize {
        let mut visited = vec![0; self.size];
        let mut count = 0;
        while visited.iter().sum::<usize>() != visited.len() {
            let mut next = 0;
            for i in 0..self.size {
                if visited[i] == 0 {
                    next = i;
                    break;
                }
            }
            self.dfs(&next, &mut visited);
            count += 1;
        }
        return count;
    }

    fn get_closure(&self) -> Graph {
        self.get_closure_traced(false)
    }

    fn is_complete(&self) -> bool {
        for row in 0..self.size {
            for col in 0..self.size {
                if row != col && self.matrix[row][col] == 0 {
                    return false;
                }
            }
        }
        return true;
    }

    fn is_independent(&self) -> bool {
        for row in 0..self.size {
            for col in 0..self.size {
                if row != col && self.matrix[row][col] != 0 {
                    return false;
                }
            }
        }
        return true;
    }
}

fn main() {
    let stdin = io::stdin();

    let mut t = 0;
    let mut count = 0;
    for line in stdin.lock().lines() {
        let line = line.unwrap();

        let g = Graph::from_g6(&line);

        let start = Instant::now();
        let closure = g.get_closure();
        let is_complete = closure.is_complete();

        if is_complete {
            count += 1;
        }

        if is_complete {
            let components_count = g.count_components();
            println!("Components count: {components_count}");
            let min_degree = g.min_degree();
            println!("Minimal degree: {min_degree}");
            println!("Graph: {line}\n{g}");

            let cutset = g.max_independent_cutset();
            println!("Maximal independent cutset:\n{}", cutset.graph);
            println!("Included vertices: {:?}", cutset.vertices);
            println!("Cutset cardinality: {}", cutset.cardinality);

            let cycle = g.get_hamiltonian_cycle();
            print!("Hamiltonian cycle: ");
            let start = 0;
            let mut current = start;
            loop {
                print!("{}", current + 1);
                print!(" -> ");
                current = cycle[current];
                if current == start {
                    println!("{}", current + 1);
                    break;
                }
            }
        }

        let elapsed = start.elapsed();
        t += elapsed.as_nanos();
    }

    println!("Count of Hamiltonian graphs: {}", count);
    println!("Time elapsed: {}s", t as f64 / 1e9);
}