{"raw_statement":[{"iden":"statement","content":"A labyrinth is the rectangular grid, each of the cells of which is either free or wall, and it's possible to move only between free cells sharing a side.\n\nConstantine and Mike are the world leaders of composing the labyrinths. Each of them has just composed one labyrinth of size n × m, and now they are blaming each other for the plagiarism. They consider that the plagiarism takes place if there exists such a path from the upper-left cell to the lower-right cell that is the shortest for both labyrinths. Resolve their conflict and say if the plagiarism took place.\n\nIn the first line two integers n and m (1 ≤ n, m ≤ 500) are written — the height and the width of the labyrinths.\n\nIn the next n lines the labyrinth composed by Constantine is written. Each of these n lines consists of m characters. Each character is equal either to «_#_», which denotes a wall, or to «_._», which denotes a free cell.\n\nThe next line is empty, and in the next n lines the labyrinth composed by Mike is written in the same format. It is guaranteed that the upper-left and the lower-right cells of both labyrinths are free.\n\nOutput «_YES_» if there exists such a path from the upper-left to the lower-right cell that is the shortest for both labyrinths. Otherwise output «_NO_».\n\n"},{"iden":"input","content":"In the first line two integers n and m (1 ≤ n, m ≤ 500) are written — the height and the width of the labyrinths.In the next n lines the labyrinth composed by Constantine is written. Each of these n lines consists of m characters. Each character is equal either to «_#_», which denotes a wall, or to «_._», which denotes a free cell.The next line is empty, and in the next n lines the labyrinth composed by Mike is written in the same format. It is guaranteed that the upper-left and the lower-right cells of both labyrinths are free."},{"iden":"output","content":"Output «_YES_» if there exists such a path from the upper-left to the lower-right cell that is the shortest for both labyrinths. Otherwise output «_NO_»."},{"iden":"examples","content":"Input3 5......#.#......  .....#.#.#.....OutputNOInput3 5......#.##.....  .....##.#......OutputYES"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 1 \\leq n, m \\leq 500 $.  \nLet $ C = (c_{i,j})_{1 \\leq i \\leq n, 1 \\leq j \\leq m} \\in \\{ \\text{`.`}, \\text{`#'} \\}^{n \\times m} $ be Constantine’s labyrinth.  \nLet $ M = (m_{i,j})_{1 \\leq i \\leq n, 1 \\leq j \\leq m} \\in \\{ \\text{`.`}, \\text{`#'} \\}^{n \\times m} $ be Mike’s labyrinth.  \nAssume $ c_{1,1} = c_{n,m} = \\text{`.`} $ and $ m_{1,1} = m_{n,m} = \\text{`.`} $.\n\nLet $ G_C = (V_C, E_C) $ be the grid graph of Constantine’s labyrinth:  \n- $ V_C = \\{ (i,j) \\mid c_{i,j} = \\text{`.`} \\} $,  \n- $ E_C = \\{ ((i,j), (i',j')) \\mid |i - i'| + |j - j'| = 1 \\} $.  \n\nLet $ G_M = (V_M, E_M) $ be the grid graph of Mike’s labyrinth, defined analogously.\n\nLet $ d_C(u,v) $ denote the shortest path distance between nodes $ u, v \\in V_C $ in $ G_C $, and $ d_M(u,v) $ analogously in $ G_M $.\n\nLet $ s = (1,1) $, $ t = (n,m) $.\n\n**Constraints**  \n1. $ s, t \\in V_C \\cap V_M $.  \n2. Both $ G_C $ and $ G_M $ are connected graphs with $ s, t \\in V_C $ and $ s, t \\in V_M $.\n\n**Objective**  \nDetermine whether:  \n$$\n\\exists \\, P \\text{ (path from } s \\text{ to } t \\text{)} \\quad \\text{such that} \\quad |P| = d_C(s,t) = d_M(s,t)\n$$  \nwhere $ |P| $ is the number of edges in path $ P $, and $ P $ is valid in both labyrinths (i.e., all cells of $ P $ are free in both $ C $ and $ M $).\n\nEquivalently:  \nIs the set of shortest paths from $ s $ to $ t $ in $ G_C $ intersecting the set of shortest paths from $ s $ to $ t $ in $ G_M $, under the constraint that all cells along the path are free in both labyrinths?\n\nOutput \"YES\" if such a path exists, \"NO\" otherwise.","simple_statement":"Two labyrinths of size n×m are given. Both have free cells ('.') and walls ('#'), and the start (top-left) and end (bottom-right) are free.\n\nFind if there exists a shortest path from top-left to bottom-right that is shortest in BOTH labyrinths at the same time.\n\nIf yes, print \"YES\". Otherwise, print \"NO\".","has_page_source":false}