#include<bits/stdc++.h>
using namespace std;
int node,edge,zaoa_zay=0;
vector<int>adj_list[20];
map<char,int>mp;
map<int,char>rev_mp;
int vis[20];
void DFS(int curr,int dest)
{
vis[curr]=1;
if(curr==dest)
{
zaoa_zay=1;
return;
}
for(int i=0;i<adj_list[curr].size();i++)
{
int child=adj_list[curr][i];
if(vis[child]==0 && zaoa_zay==0)
{
DFS(child,dest);
}
}
return;
}
int main()
{
int id=0;
cin>>node>>edge;
for(int i=1;i<=edge;i++)
{
string e;
cin>>e;
if(mp.find (e[0])==mp.end())
{
mp[e[0]]=id;
rev_mp[e[i]]=e[0];
id++;
}
if(mp.find (e[1])==mp.end())
{
mp[e[1]]=id;
rev_mp[e[i]]=e[1];
id++;
}
adj_list[mp[e[0]]].push_back(mp[e[1]]);
}
char st,ds;
cin>>st>>ds;
for(int i=0;i<=node;i++)
vis[i]=0;
DFS(mp[st],mp[ds]);
cout<<zaoa_zay<<endl;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG5vZGUsZWRnZSx6YW9hX3pheT0wOwp2ZWN0b3I8aW50PmFkal9saXN0WzIwXTsKbWFwPGNoYXIsaW50Pm1wOwptYXA8aW50LGNoYXI+cmV2X21wOwppbnQgdmlzWzIwXTsKdm9pZCBERlMoaW50IGN1cnIsaW50IGRlc3QpCnsKdmlzW2N1cnJdPTE7CmlmKGN1cnI9PWRlc3QpCnsKemFvYV96YXk9MTsKcmV0dXJuOwp9CmZvcihpbnQgaT0wO2k8YWRqX2xpc3RbY3Vycl0uc2l6ZSgpO2krKykKewppbnQgY2hpbGQ9YWRqX2xpc3RbY3Vycl1baV07CmlmKHZpc1tjaGlsZF09PTAgJiYgemFvYV96YXk9PTApCnsKREZTKGNoaWxkLGRlc3QpOwp9Cn0KcmV0dXJuOwp9CmludCBtYWluKCkKewppbnQgaWQ9MDsKY2luPj5ub2RlPj5lZGdlOwpmb3IoaW50IGk9MTtpPD1lZGdlO2krKykKewpzdHJpbmcgZTsKY2luPj5lOwppZihtcC5maW5kIChlWzBdKT09bXAuZW5kKCkpCnsKbXBbZVswXV09aWQ7CnJldl9tcFtlW2ldXT1lWzBdOwppZCsrOwp9CmlmKG1wLmZpbmQgKGVbMV0pPT1tcC5lbmQoKSkKewptcFtlWzFdXT1pZDsKcmV2X21wW2VbaV1dPWVbMV07CmlkKys7Cn0KYWRqX2xpc3RbbXBbZVswXV1dLnB1c2hfYmFjayhtcFtlWzFdXSk7Cn0KY2hhciBzdCxkczsKY2luPj5zdD4+ZHM7CmZvcihpbnQgaT0wO2k8PW5vZGU7aSsrKQp2aXNbaV09MDsKREZTKG1wW3N0XSxtcFtkc10pOwpjb3V0PDx6YW9hX3pheTw8ZW5kbDsKfQ==

MTAgMTEKQUIKQkMKQkQKQUUKREUKREcKRkUKSEYKR0gKR0oKSEkKQQpK

10 11
AB
BC
BD
AE
DE
DG
FE
HF
GH
GJ
HI
A
J