CF2049B pspspsps

# pspspsps 猫会被 $ pspspsps $ 所吸引，但 $ Evirir $ 作为一条有尊严的龙，只被具有奇怪特定要求的 $ pspspsps $ 所吸引...... 给定一个长度为 $ n $ 的字符串 $ s = s_1s_2 \dots s_n $ ，由字符 $ p、s $ 和 $.$（点）组成，确定长度为 $ n $ 的排列 $ ^{∗} $ $ p $ 是否存在，使得对于所有整数 $ i $ （ $ 1 \le i \le n $ ）： - 如果 $ s_i $ 是 $ p $，那么 $ [p_1， p_2， \dots， p_i] $ 形成一个排列（长度为 $ i $ ）; - 如果 $ s_i $ 是 $ s $，那么 $ [p_i， p_{i+1}， \dots， p_{n}] $ 形成一个排列（长度为 $ n-i+1 $ ）; - 如果 $ s_i $ 为 $ . $（点），则没有其他限制。 $ ^{∗} $ 长度为 $ n $ 的排列是一个数组，由 $ n $ 个从 $ 1 $ 到 $ n $ 的任意顺序的不同的整数组成。例如，$ [2,3,1,5,4] $ 是排列，但 $ [1,2,2] $ 不是排列（ $ 2 $ 在数组中出现两次），$ [1,3,4] $ 也不是排列（ $ n=3 $ 但数组中有 $ 4 $）。

每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $ （ $ 1 \le t \le 10^4 $ ）。测试用例的描述如下。 每个测试用例的第一行包含一个整数 $ n $ （ $ 1 \le n \le 500 $ ），长度为 $ s $ 。 每个测试用例的第二行包含一个长度为 $ n $ 的字符串 $ s $，该字符串由字符 $ p、s $ 和 $ . $ （点） 组成。 保证所有测试用例的 $ n $ 之和不超过 $ 5000 $ 。

对于每个测试用例，在一行上输出 YES 或 NO。如果存在这样的排列，则输出 YES，否则输出 NO。 答案忽视字母大小写。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 将会被判定正确。 ## 样例 #1 ### 样例输入 #1 ``` 9 4 s.sp 6 pss..s 5 ppppp 2 sp 4 .sp. 8 psss.... 1 . 8 pspspsps 20 .................... ``` ### 样例输出 #1 ``` YES NO YES YES NO NO YES NO YES ```

对于第一个测试用例，一个有效的排列是 $ p = [3， 4， 1， 2] $ 。要求如下： - $ s_1 = s $： $ [p_1， p_2， p_3， p_4] = [3， 4， 1， 2] $ 形成排列。 - $ s_2 = . $（点）：无其它要求。 - $ s_3 = s $： $ [p_3， p_4] = [1， 2] $ 形成排列。 - $ s_4 = p $： $ [p_1， p_2， p_3， p_4] = [3， 4， 1， 2] $ 形成排列。 对于第二个测试用例，可以证明没有满足所有要求的排列。 对于第三个测试用例，满足要求的一个排列是 $ p = [1， 2， 3， 4， 5] $ 。