农夫john最近在研究如果发生重大事故如何让农场里的奶牛逃离问题.他想要确信在紧急情况下所有的奶牛都有一个安全逃离方案.因为在紧急情况下奶牛们都会失去观察和判断能力所以最近john一直在教奶牛们逃离的方法他的方法很简单就是任何时候都只向北方或东方逃离北方是行坐标减1的方向东方是列坐标加1的方向.奶牛们虽笨不过这一点事关自己的生命所以他们牢记在心而且也一定会这么做.当然也会出问题奶牛们在逃离的方向上会横冲直撞为了阻止奶牛之间互相冲撞造成伤害john要求任何一个奶牛的逃离路线不能经过其它奶牛的初始位置.一个逃离方案是安全的如果它能够满足上面的要求反之它就是不安全的.奶牛们所在的土地农场被划分成了r行和c列的一个矩形地图.奶牛们都待在这个矩形中的某一个位置.请帮助john确定给定的一个地图上是否存在一个安全的逃离方案.比如下面列举的两种情形左边的例子表示了一个能够安全逃离的地图因为没有任何一个奶牛的逃离路线上包括其他奶牛.右边的例子表示了一个不安全的地图因为位于41的奶牛不论是向东逃离还是向北逃离它的路线上都会有别的奶牛从这个图中