B. Две бинарных строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две строки $$$a$$$ и $$$b$$$ одинаковой длины, состоящих только из символов 0 и/или 1; обе строки начинаются с символа 0 и заканчиваются символом 1.

Вы можете применять следующую операцию любое количество раз (возможно ноль раз):

  • выбрать какую-то строку и два равных символа в ней; затем превратить все символы между этими двумя в эти символы.

Формально, вы выбираете одну из двух строк (обозначим ее как $$$s$$$), затем выбираете два символа $$$l$$$ и $$$r$$$, такие, что $$$1 \le l < r \le |s|$$$ и $$$s_l = s_r$$$, затем заменяете все символы $$$s_i$$$, такие что $$$l < i < r$$$ на $$$s_l$$$.

Например, если выбранная строка это 010101, вы можете превратить ее в описанные ниже строки за одну операцию:

  • 000101, если выберете $$$l = 1$$$ и $$$r = 3$$$;
  • 000001, если выберете $$$l = 1$$$ и $$$r = 5$$$;
  • 010001, если выберете $$$l = 3$$$ и $$$r = 5$$$;
  • 010111, если выберете $$$l = 4$$$ и $$$r = 6$$$;
  • 011111, если выберете $$$l = 2$$$ и $$$r = 6$$$;
  • 011101, если выберете $$$l = 2$$$ и $$$r = 4$$$.

Вам нужно определить, можно ли сделать эти две строки одинаковыми при помощи применения к ним любого количества описанной выше операции.

Входные данные

Первая строка содержит одно число $$$t$$$ ($$$1 \le t \le 2000$$$)  — количество наборов входных данных.

Каждый набор входных данных содержит две строки:

  • в первой содержится строка $$$a$$$ ($$$2 \le |a| \le 5000$$$), состоящая только из символов 0 и/или 1.
  • во второй содержится строка $$$b$$$ ($$$2 \le |b| \le 5000$$$), состоящая только из символов 0 и/или 1.

Дополнительные ограничения на входные данные:

  • в каждом наборе входных данных $$$|a| = |b|$$$ (строки имеют одинаковую длину);
  • в каждом наборе данных любая из двух строк начинается с символа 0 и заканчивается символом 1;
  • суммарная длина строк $$$a$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Выходные данные

Для каждого набора входных данных выведите YES, если возможно сделать строки равными. Иначе выведите NO. Символы в ответе могут быть в любом регистре.

Пример
Входные данные
7
01010001
01110101
01001
01001
000101
010111
00001
01111
011
001
001001
011011
010001
011011
Выходные данные
YES
YES
YES
NO
NO
NO
YES
Примечание

В первом наборе входных данных мы можем выполнить следующие операции:

  1. выбрать строку $$$a$$$, $$$l = 2$$$, $$$r = 4$$$; после этой операции $$$a$$$ равна 01110001, $$$b$$$ равна 01110101;
  2. выбрать строку $$$b$$$, $$$l = 5$$$, $$$r = 7$$$; после этой операции $$$a$$$ равна 01110001, $$$b$$$ равна 01110001.

Во втором наборе входных данных строки уже равны.

В третьем наборе входных данных мы можем выполнить следующие операции:

  1. выбрать строку $$$a$$$, $$$l = 4$$$, $$$r = 6$$$; после этой операции $$$a$$$ равна 000111, $$$b$$$ равна 010111;
  2. выбрать строку $$$b$$$, $$$l = 1$$$, $$$r = 3$$$; после этой операции $$$a$$$ равна 000111, $$$b$$$ равна 000111;

В четвертом и пятом наборах входных данных невозможно сделать строки равными.