Codeforces Round 856 (Div. 2) |
---|
Закончено |
Маркос очень любит строки, поэтому у него есть любимая строка $$$s$$$, состоящая из строчных латинских букв. Для этой строки он записал все ее непустые префиксы и суффиксы (кроме $$$s$$$) на листе бумаги в произвольном порядке. Вы увидели все эти строки и задумались, является ли любимая строка Маркоса палиндромом или нет? Ваша задача — выяснить, является ли $$$s$$$ палиндромом.
Строка $$$a$$$ является префиксом строки $$$b$$$, если $$$a$$$ получается из $$$b$$$ удалением нескольких (возможно, нуля или всех) символов с конца.
Строка $$$a$$$ является суффиксом строки $$$b$$$, если $$$a$$$ получается из $$$b$$$ удалением нескольких (возможно, нуля или всех) символов с начала.
Палиндром — это строка, которая читается одинаково как в прямом, так и в обратном направлении, например строки «gg», «ioi», «abba», «icpci» являются палиндромами, а строки «codeforces», «abcd», «alt» — нет.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 120$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$2\le n \le 20$$$) — длину строки $$$s$$$.
Вторая строка каждого набора входных данных содержит $$$2n-2$$$ строк $$$a_1, a_2, \cdots, a_{2n-2}$$$ — все непустые префиксы и суффиксы $$$s$$$, кроме самой себя, в произвольном порядке.
Гарантируется, что все эти строки являются непустыми префиксами и суффиксами некоторой строки, состоящей из строчных латинских букв.
Для каждого набора входных данных выведите «YES», если $$$s$$$ является палиндромом, и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
54bcd cd a d abc ab3i io i oi2g g3t al lt a4bba a ab a abb ba
NO YES YES NO YES
В первом наборе входных данных $$$s$$$ равна «abcd». Ее префиксы «a», «ab» и «abc», а ее суффиксы «d», «cd» и «bcd». Поскольку строка «abcd» не является палиндромом, ответ будет «NO».
Во втором наборе входных данных $$$s$$$ равна «ioi». Ее префиксы «i» и «io», а ее суффиксы «i» и «oi». Поскольку строка «ioi» является палиндромом, ответ будет «YES».
В третьем наборе входных данных $$$s$$$ равна «gg», что является палиндромом.
В четвертом наборе входных данных $$$s$$$ равна «alt», что не является палиндромом.
Название |
---|