Codeforces 868A Bark to Unlock【字符串+二维string输入输出+特判】

As technologies develop, manufacturers are making the process of unlocking a phone as user-friendly as possible. To unlock its new phone, Arkady's pet dog Mu-mu has to bark the password once. The phone represents a password as a string of two lowercase English letters.

Mu-mu's enemy Kashtanka wants to unlock Mu-mu's phone to steal some sensible information, but it can only bark ndistinct words, each of which can be represented as a string of two lowercase English letters. Kashtanka wants to bark several words (not necessarily distinct) one after another to pronounce a string containing the password as a substring. Tell if it's possible to unlock the phone in this way, or not.

Input

The first line contains two lowercase English letters — the password on the phone.

The second line contains single integer n (1 ≤ n ≤ 100) — the number of words Kashtanka knows.

The next n lines contain two lowercase English letters each, representing the words Kashtanka knows. The words are guaranteed to be distinct.

Output

Print "YES" if Kashtanka can bark several words in a line forming a string containing the password, and "NO" otherwise.

You can print each letter in arbitrary case (upper or lower).

Examples

input

ya
4
ah
oy
to
ha

output

YES

input

hp
2
ht
tp

output

NO

input

ah
1
ha

output

YES

In the first example the password is "ya", and Kashtanka can bark "oy" and then "ah", and then "ha" to form the string "oyahha" which contains the password. So, the answer is "YES".

In the second example Kashtanka can't produce a string containing password as a substring. Note that it can bark "ht" and then "tp" producing "http", but it doesn't contain the password "hp" as a substring.

In the third example the string "hahahaha" contains "ah" as a substring.

【题意】：给出一个目标串（长度为2），再给n行长度为2的文本串，要求在文本串（可连续多个相同，不要求有序）中判断是否有该目标串。

【分析】：要注意当文本串里面刚好含有目标串特判为YES，否则根据文本串的某个头=目标串的尾&&文本串的某个尾=目标串的头，枚举即可。

【代码】：

#include<bits/stdc++.h>
using namespace std;
string s;
string ss[103];
int n;
int main()
{
    cin>>s;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ss[i];
        if(s==ss[i])
        {
            cout<<"YES";  //或者直接flag标记，在末尾统一判断后输出
            return 0;    //注意不能用break 因为下面还有循环 会输出2个 YESNO这样
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if( s[0]==ss[i][1]&&s[1]==ss[j][0] )

            {
                cout<<"YES";
                return 0;
            }
        }
    }

    cout<<"NO";
}

View Code

Codeforces 868A Bark to Unlock【字符串+二维string输入输出+特判】

A. Bark to Unlock