Removing Pairs

Interview

Time limit2sMemory limit512 MB

Summary

Decide whether string s can be obtained from string t by repeatedly deleting two adjacent characters, where each deletion removes any neighboring pair.

Level: Medium5 of 10
Topics: String, Dynamic programming, Greedy, Two pointers
Solved: No attempts yet

Problem

The pair removal operation removes two adjacent characters from a string. For example, from the string "abcd" we can obtain "ab", "ad", and "cd" by pair removal.

You are given a string $t$ . You can apply pair removal any number of times. Is it possible to obtain the string $s$ ?

Input

The first line contains the string $s$ , and the second line contains the string $t$ ( $1 \le |s| \le |t| \le 10^5$ ). Both strings are composed of lowercase letters of the English alphabet.

Output

Print "YES" if it is possible to obtain $s$ from $t$ using pair removal, or "NO" otherwise.

Hint

In the first test, one of the possible pair removal sequences is the following:

abcbcxdda
abcxdda
abcxa
axa

Examples3

Example 1
Input
```
axa
abcbcxdda
```
Expected output
```
YES
```
Example 2
Input
```
rrr
rdfgdfgrdr
```
Expected output
```
NO
```
Example 3
Input
```
w
uwwu
```
Expected output
```
NO
```