#include <fstream>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <vector>
#include <numeric>

#include "util.h"

using Pos = std::string;
using Moves = std::vector<bool>;
using Map = std::unordered_map<Pos,std::pair<Pos,Pos>>;

constexpr char EQUAL[] = "=";

std::pair<Moves,Map> parse(const char* path)
{
    Map map{};
    Moves moves{};

    std::ifstream input{ path };
    if (input.is_open())
    {
        std::string line;
        std::getline(input,line);

        moves.resize(line.size());
        std::transform(line.cbegin(), line.cend(),
            moves.begin(), [](unsigned char c) { return c == 'L'; });

        std::string from, tol, tor;
        while (not std::getline(input,line).eof())
        {
            if (line.empty()) continue;

            std::istringstream in{ line };
            in >> from >> util::skip<EQUAL> >> tol >> tor;
            tol.erase(0,1); tol.pop_back();
            tor.pop_back();
            map.insert({ from, { tol, tor } });
        }
    }
    input.close();

    return { std::move(moves), std::move(map) };
}

long long compute(const Map& map, const Moves& moves, Pos pos)
{
    long long idx{};

    while (pos[2] != 'Z')
    {
        bool left = moves[idx++ % moves.size()];
        pos = left ? map.at(pos).first : map.at(pos).second; 
    }

    return idx;
}

int main(int argc, char* argv[])
{
    long long answer{ 1 };

    auto [moves, map] = parse(argv[1]);

    for (const auto& kv : map)
    {
        if (kv.first[2] == 'A')
        {
            answer = std::lcm(answer, compute(map, moves, kv.first));
        }
    }

    std::cout << answer << std::endl;
    return 0;
}