← 返回题目列表

Codeforces · 475/B

B. 紧密相连的城市

中文机器翻译题面 查看原题

想象一个城市,有 n 条水平街道与 m 条垂直街道交叉,形成 (n - 1) × (m - 1) 网格。为了增加交通流量,市长决定将每条街道都改为单行道。这意味着在每条水平街道上,交通仅从西向东或仅从东向西移动。此外,在每条垂直街道上,交通仅从北向南或仅从南向北移动。可以在交叉路口从垂直街道进入水平街道,反之亦然。

市长收到了一些街道方向图。您的任务是检查是否可以从建议的街道方向模式中的任何其他路口到达任何路口。

输入

输入的第一行包含两个整数n和m,(2≤n,m≤20),表示水平街道数量和垂直街道数量。

第二行包含一个长度为n的字符串,由字符“<”和“>”组成,表示每条水平街道的方向。如果第 i 个字符等于“<”,则街道从东向西,否则,街道从西向东。街道按从北到南的顺序列出。

第三行包含长度为m的字符串,由字符“^”和“v”组成,表示每条垂直街道的方向。如果第 i 个字符等于 '^',则街道从南到北,否则街道从北到南。街道按从西到东的顺序列出。

输出

如果给定的模式满足市长的标准,则打印包含“YES”的单行,否则打印包含“NO”的单行。

示例

输入 #1

3 3
><>
v^v

输出 #1

NO

输入 #2

4 6
<><>
v^v^v^

输出 #2

YES

注意

上图显示了第二个示例测试用例中的街道方向。