DMOPC '21 Contest 9 P2 - String Puzzle

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Bored after completing all of the statistics handouts for the day, you turn around to take a peek at what Christian is doing. As it turns out, he is working on a list of T string puzzles. The goal of the i-th puzzle is to transform a string of lowercase letters A_i into the string B_i using the following operation any number of times:

  • Select two consecutive occurrences of the same letter and replace them with one occurrence of the next letter in the alphabet. Note that z is the last letter of the alphabet, so zz cannot be replaced.

After working on the puzzles for a few minutes, you have a strange suspicion that some of them are impossible. Thus, write a program to determine if it is possible to solve each puzzle.


1 \le T \le 10^5

1 \le |A_i|, |B_i| \le 10^6

The sum of |A_i| + |B_i| over all puzzles does not exceed 10^6.

A_i and B_i contain only lowercase letters.

Subtask 1 [30%]

A_i and B_i contain only a and b.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains an integer T.

The next T lines each contain 2 space-separated strings A_i and B_i.

Output Specification

For each puzzle, output YES if it is solvable or NO otherwise.

Sample Input

caabdfgg efh
zz z
dmopc funcontest

Sample Output



There are no comments at the moment.