CF475B Strongly Connected City

想象有一座城市，城市中有 $n$ 条东西向的横街和 $m$ 条南北向的纵街交错，形成一个 $(n-1)×(m-1)$ 的格点网络。为了提升交通流量，市长决定将每条街道都设置为单行道。这意味着每条横街上的车流只能从西向东，或者只能从东向西。同样的，每条纵街上的车流只能从北向南，或者只能从南向北。在每个交叉口，车辆可以从横街进入纵街，也可以从纵街进入横街。 市长收到了几种设定街道方向的方案。你的任务是检查，给定的街道方向方案下，是否能够从任意一个交叉口到达另一个任意的交叉口。 上图展示了第二个样例测试中的街道方向。

第一行输入包含两个整数 $n$ 和 $m$，$(2 \leq n, m \leq 20)$，分别表示横街和纵街的数量。 第二行是一个长度为 $n$ 的字符串，只包含字符 ''，表示每条横街的行驶方向。如果第 $i$ 个字符为 ''，则该横街为从西向东。横街按从北到南的顺序给出。 第三行是一个长度为 $m$ 的字符串，只包含字符 '^' 和 'v'，表示每条纵街的行驶方向。如果第 $i$ 个字符为 '^'，则该纵街为从南向北；否则为 'v'，则该纵街为从北向南。纵街按从西到东的顺序给出。

如果市长的要求得到了满足，输出一行 "YES"；否则输出一行 "NO"。

上图显示的是第二个样例测试中街道的方向。 由 ChatGPT 5 翻译