<?php

ini_set('memory_limit', -1);

function readInput(): array
{
    $lines = [];

    $f = fopen( 'php://stdin', 'r' );

    while( $line = fgets( $f ) ) {
        $withOutNewLine = str_replace(PHP_EOL,'',$line);
        if ($withOutNewLine != '') {
            $lines[] = $withOutNewLine;
        }
    }

    fclose($f);

    return $lines;
}

$input = readInput();

$graph = [];

foreach ($input as $line) {
    $connection = explode('-',$line);
    if (!array_key_exists($connection[0], $graph)) {
        $graph[$connection[0]] = [];
    }

    if (!array_key_exists($connection[1], $graph)) {
        $graph[$connection[1]] = [];
    }

    if ($connection[0] == 'start') {
        $graph[$connection[0]][] = $connection[1];
        continue;
    }

    if ($connection[1] == 'end') {
        $graph[$connection[0]][] = $connection[1];
        continue;
    }

    $graph[$connection[0]][] = $connection[1];

    $graph[$connection[1]][] = $connection[0];
}

$total = [
    'count' => 0
];

countPaths('start', $graph, $total, 'fuck', []);

echo $total['count'] . PHP_EOL;

function countPaths($currentNode, $graph, &$counter, $previous, $smallVisited)
{
    if ($currentNode == 'end') {
        $counter['count']++;

        return;
    }

    if (ctype_lower($currentNode) && $currentNode != 'start') {
        $smallVisited[$currentNode] = ($smallVisited[$currentNode] ?? 0) + 1;
    }

    foreach ($graph[$currentNode] as $neighbour) {
        if (ctype_upper($currentNode) && ctype_upper($neighbour) && $neighbour == $previous) {
            continue;
        }

        if ($neighbour == 'start') {
            continue;
        }

        if (($smallVisited[$neighbour] ?? 0) >= 1 && max(array_values($smallVisited)) > 1) {
            continue;
        }

        countPaths($neighbour, $graph, $counter, $currentNode, $smallVisited);
    }
}