using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3");
WillReturn.Add("4 4");
WillReturn.Add("1 2");
WillReturn.Add("1 4");
WillReturn.Add("2 4");
WillReturn.Add("2 3");
WillReturn.Add("3");
WillReturn.Add("xxo");
WillReturn.Add("xox");
WillReturn.Add("oxo");
WillReturn.Add("oxx");
WillReturn.Add("1 0");
WillReturn.Add("4");
WillReturn.Add("oooo");
WillReturn.Add("5 5");
WillReturn.Add("1 4");
WillReturn.Add("2 3");
WillReturn.Add("4 5");
WillReturn.Add("3 4");
WillReturn.Add("2 5");
WillReturn.Add("7");
WillReturn.Add("oxxxxxx");
WillReturn.Add("xxoxxxo");
WillReturn.Add("xxxoxox");
WillReturn.Add("xoxxoxx");
WillReturn.Add("oxxxoxx");
//Yes
//Yes
//No
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
int CurrInd = 1;
while (true) {
if (CurrInd > InputList.Count - 1) break;
mBeforeToNodeListDict.Clear();
mAfterToNodeListDict.Clear();
SplitAct(InputList[CurrInd]);
mN = wkArr[0];
mM = wkArr[1];
for (long I = 1; I <= mN; I++) {
// 自己ループの枝
mBeforeToNodeListDict[I] = new List<long>() { I };
}
for (int I = CurrInd + 1; I <= CurrInd + mM; I++) {
SplitAct(InputList[I]);
long FromNode = wkArr[0];
long ToNode = wkArr[1];
mBeforeToNodeListDict[FromNode].Add(ToNode);
mBeforeToNodeListDict[ToNode].Add(FromNode);
}
var mSList = new List<string>();
for (long I = CurrInd + mM + 2; I <= CurrInd + mM + 1 + mN; I++) {
mSList.Add(InputList[(int)I]);
}
mW = mSList[0].Length;
mSArr = mSList.ToArray();
Solve();
CurrInd += (int)(1 + mM + 1 + mN);
}
}
static long mN;
static long mM;
static long mW;
// 隣接リスト(頂点倍加前)
static Dictionary<long, List<long>> mBeforeToNodeListDict = new Dictionary<long, List<long>>();
// 隣接リスト(頂点倍加後)
static Dictionary<long, List<long>> mAfterToNodeListDict = new Dictionary<long, List<long>>();
static string[] mSArr;
static void Solve()
{
// ノードのハッシュ値のList
var NodeHashList = new List<long>();
for (long I = 1; I <= mN; I++) {
for (long J = 1; J <= mW; J++) {
if (mSArr[I - 1][(int)J - 1] == 'o') {
NodeHashList.Add(GetHash(I, J));
}
}
}
if (NodeHashList.Count == 0) {
Console.WriteLine("No");
return;
}
// 頂点倍加後のノード[頂点倍加前のハッシュ値]
Dictionary<long, long> ZaatuDict = DeriveZaatuDict(NodeHashList);
// 頂点倍加後の隣接リストの作成
foreach (var EachPair in ZaatuDict) {
long CurrHash = EachPair.Key;
long CurrNode, CurrDay;
GetJyoutai(CurrHash, out CurrNode, out CurrDay);
long AfterNode = ZaatuDict[CurrHash];
long NextDay = CurrDay + 1;
if (NextDay > mW) NextDay = 1;
if (mBeforeToNodeListDict.ContainsKey(CurrNode)) {
foreach (long EachToNode in mBeforeToNodeListDict[CurrNode]) {
if (mSArr[EachToNode - 1][(int)NextDay - 1] == 'o') {
if (mAfterToNodeListDict.ContainsKey(AfterNode) == false) {
mAfterToNodeListDict[AfterNode] = new List<long>();
}
long AfterHash = GetHash(EachToNode, NextDay);
mAfterToNodeListDict[AfterNode].Add(ZaatuDict[AfterHash]);
}
}
}
}
long MinNode = ZaatuDict.Values.Min();
long MaxNode = ZaatuDict.Values.Max();
bool Result = DirectedGraphHasCycle_Class.HasCycle(MinNode, MaxNode, mAfterToNodeListDict);
if (Result) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
//////////////////////////////////////////////////////////////////////////
// 列挙を引数として、座標圧縮し、座圧後の値[座圧前の値]なDictを返す
//////////////////////////////////////////////////////////////////////////
static Dictionary<long, long> DeriveZaatuDict(IEnumerable<long> pEnum)
{
var ZaatuDict = new Dictionary<long, long>();
var ValSet = new HashSet<long>(pEnum);
long No = 0;
foreach (long EachVal in ValSet.OrderBy(pX => pX)) {
ZaatuDict[EachVal] = No;
No++;
}
return ZaatuDict;
}
static long GetHash(long pNode, long pDay)
{
return pNode * 100 + pDay;
}
static void GetJyoutai(long pHash, out long pNode, out long pDay)
{
pNode = pHash / 100;
pDay = pHash % 100;
}
}
#region DirectedGraphHasCycle_Class
// 有向グラフの閉路有無の判定クラス
internal class DirectedGraphHasCycle_Class
{
private static long mMinNode;
private static long mMaxNode;
private static Dictionary<long, List<long>> mToNodeListDict;
private static long[] mDegreeArr;
private static HashSet<long> mVisitedSet;
// 最小のノードID,最大のノードID,隣接グラフを引数とし、閉路の有無を返す
internal static bool HasCycle(long pMinNode, long pMaxNode,
Dictionary<long, List<long>> pToNodeListDict)
{
mMinNode = pMinNode;
mMaxNode = pMaxNode;
mToNodeListDict = pToNodeListDict;
mVisitedSet = new HashSet<long>();
// 入次数を配列で管理
mDegreeArr = new long[mMaxNode + 1];
foreach (var EachPair in mToNodeListDict) {
foreach (long EachToNode in EachPair.Value) {
mDegreeArr[EachToNode]++;
}
}
// 入次数が0で、未訪問ノードから深さ優先探索
for (long I = mMinNode; I <= mMaxNode; I++) {
if (mDegreeArr[I] > 0) continue;
if (mVisitedSet.Contains(I)) continue;
HasCycleHelperExecDFS(I);
}
long NodeCnt = pMaxNode - pMinNode + 1;
return NodeCnt > mVisitedSet.Count;
}
// HasCycleのヘルパメソッドで、深さ優先探索を行う
private struct JyoutaiDef_HasCycle
{
internal long CurrNode;
}
private static void HasCycleHelperExecDFS(long pStaNode)
{
JyoutaiDef_HasCycle WillPush;
WillPush.CurrNode = pStaNode;
var Stk = new Stack<JyoutaiDef_HasCycle>();
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef_HasCycle Popped = Stk.Pop();
long CurrNode = Popped.CurrNode;
mVisitedSet.Add(CurrNode);
if (mToNodeListDict.ContainsKey(CurrNode) == false) {
continue;
}
foreach (int EachToNode in mToNodeListDict[CurrNode]) {
// 入次数はデクリメント
mDegreeArr[EachToNode]--;
// 入次数が0でなかったら訪問しない
if (mDegreeArr[EachToNode] > 0) continue;
// 再訪防止
if (mVisitedSet.Add(EachToNode) == false) continue;
WillPush.CurrNode = EachToNode;
Stk.Push(WillPush);
}
}
}
}
#endregion