Description

Alice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双

向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2 到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和 Bob能完成他们的愿望吗？

Input

本题有多组测试数据。

每组数据第一行包含7个空格隔开的整数，分别为N、al、a2、an、bl、b2、bn。

接下来是一个N行N列的对称矩阵，由大写字母组成。矩阵的i行j列描述编号i一1和j-l的岛屿间的连接情况，若为“O”则表示有危桥相连：为“N”表示有普通的桥相连：为“X”表示没有桥相连。

|

Output

对于每组测试数据输出一行，如果他们都能完成愿望输出“Yes”，否则输出“No”。

Sample Input

4 0 1 1 2 3 1

XOXX

OXOX

XOXO

XXOX

4 0 2 1 1 3 2

XNXO

NXOX

XOXO

OXOX

Sample Output

Yes

No

数据范围

4<=N<50

O<=a1, a2, b1, b2<=N-1

1 <=an. b<=50

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int N=60,inf=10000000; 6 struct ee{
   int to,next,f;}e[N*N*20]; 7 int S,T,cnt=1,n,k,timer,m,u,v,w,a1,a2,an,b1,b2,bn; 8 char s[N]; 9 long long ans;10 int head[N],dis[N],pre[N],q[N],map[N][N];11 bool inq[N];12 void ins(int u,int v,int f){13     e[++cnt].to=v,e[cnt].next=head[u],e[cnt].f=f,head[u]=cnt;14     e[++cnt].to=u,e[cnt].next=head[v],e[cnt].f=0,head[v]=cnt;15 }16 bool bfs(){17     for (int i=1;i<=T;i++) dis[i]=inf;18     int h=0,t=1,now;19     q[1]=S;dis[S]=0;20     while(h!=t){21         now=q[++h];22         for (int i=head[now];i;i=e[i].next){23             int v=e[i].to;24             if (e[i].f&&dis[now]+1