Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Common ancestor

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe DNA sequence for every living creature in Berland can be represented as a non-empty line consisting of lowercase Latin letters. Berland scientists found out that all the creatures evolve by stages. During one stage exactly one symbol of the DNA line is replaced by exactly two other ones. At that overall there are *n* permissible substitutions. The substitution *a*_{i}->*b*_{i}*c*_{i} means that any one symbol *a*_{i} can be replaced with two symbols *b*_{i}*c*_{i}. Every substitution could happen an unlimited number of times.

They say that two creatures with DNA sequences *s*_{1} and *s*_{2} can have a common ancestor if there exists such a DNA sequence *s*_{3} that throughout evolution it can result in *s*_{1} and *s*_{2}, perhaps after a different number of stages. Your task is to find out by the given *s*_{1} and *s*_{2} whether the creatures possessing such DNA sequences can have a common ancestor. If the answer is positive, you have to find the length of the shortest sequence of the common ancestor’s DNA.

Input

The first line contains a non-empty DNA sequence *s*_{1}, the second line contains a non-empty DNA sequence *s*_{2}. The lengths of these lines do not exceed 50, the lines contain only lowercase Latin letters. The third line contains an integer *n* (0 ≤ *n* ≤ 50) — the number of permissible substitutions. Then follow *n* lines each of which describes a substitution in the format *a*_{i}->*b*_{i}*c*_{i}. The characters *a*_{i}, *b*_{i}, and *c*_{i} are lowercase Latin letters. Lines *s*_{1} and *s*_{2} can coincide, the list of substitutions can contain similar substitutions.

Output

If *s*_{1} and *s*_{2} cannot have a common ancestor, print -1. Otherwise print the length of the shortest sequence *s*_{3}, from which *s*_{1} and *s*_{2} could have evolved.

Examples

Input

ababa

aba

2

c->ba

c->cc

Output

2

Input

ababa

aba

7

c->ba

c->cc

e->ab

z->ea

b->ba

d->dd

d->ab

Output

1

Input

ababa

aba

1

c->ba

Output

-1

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 15:22:04 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|