1473B.md (1535B)
1 Source: https://codeforces.com/problemset/problem/1473/B 2 3 B. String LCM 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let's define a multiplication operation between a string $a$ and a positive integer $x$: $a \cdot x$ is the string that is a result of writing $x$ copies of $a$ one after another. For example, "abc" $\cdot~2~=$ "abcabc", "a" $\cdot~5~=$ "aaaaa". 22 23 A string $a$ is divisible by another string $b$ if there exists an integer $x$ such that $b \cdot x = a$. For example, "abababab" is divisible by "ab", but is not divisible by "ababab" or "aa". 24 25 LCM of two strings $s$ and $t$ (defined as $LCM(s, t)$) is the shortest non-empty string that is divisible by both $s$ and $t$. 26 27 You are given two strings $s$ and $t$. Find $LCM(s, t)$ or report that it does not exist. It can be shown that if $LCM(s, t)$ exists, it is unique. 28 29 Input 30 31 The first line contains one integer $q$ ($1 \le q \le 2000$) — the number of test cases. 32 33 Each test case consists of two lines, containing strings $s$ and $t$ ($1 \le |s|, |t| \le 20$). Each character in each of these strings is either 'a' or 'b'. 34 35 Output 36 37 For each test case, print $LCM(s, t)$ if it exists; otherwise, print -1. It can be shown that if $LCM(s, t)$ exists, it is unique. 38 39 Example 40 41 Input 42 43 ``` 44 3 45 baba 46 ba 47 aa 48 aaa 49 aba 50 ab 51 ``` 52 53 Output 54 55 ``` 56 baba 57 aaaaaa 58 -1 59 ``` 60 61 Note 62 63 In the first test case, "baba" = "baba" $\cdot~1~=$ "ba" $\cdot~2$. 64 65 In the second test case, "aaaaaa" = "aa" $\cdot~3~=$ "aaa" $\cdot~2$.