#!/usr/bin/perl -w

use v5.16;
use strict;

my %rules;
while (<>) {
	chomp;
	last if /^$/;
	my ($src, $dst) = /(\w+) => (\w+)/;
	# push @rules, [$src, $dst];
	push @{ $rules{$src} }, [ split(/(?=[A-Z])/, $dst) ];
}

chomp (my $mol = <>);
my @mol = split(/(?=[A-Z])/, $mol);

$; = ',';
my $added = 1;
while ($added) {
	$added = 0;
	for my $elem (keys %rules) {
		for my $rule (@{ $rules{$elem} }) {
			my $first = $
my @q = ([ ['e'], \@mol, 0 ]);

my %seen;

while (@q) {
	my $entry = shift @q;
	my ($stack, $mol, $steps) = @$entry;

	if (!@$stack && !@$mol) {
		say $steps;
		last;
	}
	if (!@$stack || !@$mol) {
		next;
	}
	say "apply $steps: @$stack => @$mol";

	if ($stack->[0] eq $mol->[0]) {
		say "reduce $stack->[0]";
		my @nstack = @$stack;
		shift @nstack;
		my @nmol = @$mol;
		shift @nmol;
		unshift @q, [ \@nstack, \@nmol, $steps ];
	}
	for my $rule (@{ $rules{$stack->[0]} }) {
		my @nstack = @$stack;
		shift @nstack;
		unshift @nstack, @$rule;
		my $key = join(' ', @nstack, '=', @$mol);
		next if $seen{$key}++;
		say "push $stack->[0] => @$rule";
		push @q, [ \@nstack, [ @$mol ], $steps+1 ];
	}
}
