[Solution] Deletions of Two Adjacent Letters solution codeforces

Deletions of Two Adjacent Letters solution codeforces – The string 𝑠s is given, the string length is odd number. The string consists of lowercase letters of the Latin alphabet.

As long as the string length is greater than 11, the following operation can be performed on it: select any two adjacent letters in the string 𝑠s and delete them from the string. For example, from the string “lemma” in one operation, you can get any of the four strings: “mma“, “lma“, “lea” or “lem” In particular, in one operation, the length of the string reduces by 22.

Formally, let the string 𝑠s have the form 𝑠=𝑠1𝑠2𝑠𝑛s=s1s2…sn (𝑛>1n>1). During one operation, you choose an arbitrary index 𝑖i (1𝑖<𝑛1≤i<n) and replace 𝑠=𝑠1𝑠2𝑠𝑖1𝑠𝑖+2𝑠𝑛s=s1s2…si−1si+2…sn.

Deletions of Two Adjacent Letters solution codeforces

For the given string 𝑠s and the letter 𝑐c, determine whether it is possible to make such a sequence of operations that in the end the equality 𝑠=𝑐s=c will be true? In other words, is there such a sequence of operations that the process will end with a string of length 11, which consists of the letter 𝑐c?

Input

The first line of input data contains an integer 𝑡t (1𝑡1031≤t≤103) — the number of input test cases.

The descriptions of the 𝑡t cases follow. Each test case is represented by two lines:

  • string 𝑠s, which has an odd length from 11 to 4949 inclusive and consists of lowercase letters of the Latin alphabet;
  • is a string containing one letter 𝑐c, where 𝑐c is a lowercase letter of the Latin alphabet.

Deletions of Two Adjacent Letters solution codeforces

For each test case in a separate line output:

  • YES, if the string 𝑠s can be converted so that 𝑠=𝑐s=c is true;
  • NO otherwise.

You can output YES and NO in any case (for example, the strings yEsyesYes and YES will be recognized as a positive response).

Example
input

Copy
5
abcde
c
abcde
b
x
y
aaaaaaaaaaaaaaa
a
contest
t

Deletions of Two Adjacent Letters solution codeforces

YES
NO
NO
YES
YES

Deletions of Two Adjacent Letters solution codeforces Note

In the first test case, 𝑠s=”abcde“. You need to get 𝑠s=”c“. For the first operation, delete the first two letters, we get 𝑠s=”cde“. In the second operation, we delete the last two letters, so we get the expected value of 𝑠s=”c“.

In the second test case, 𝑠s=”x“, it is required to get 𝑠s=”y“. Obviously, this cannot be done.

 

For Solution

Click Here

Leave a Comment