安全逃离(数据有误)
题目背景
**注意本题数据有误,请暂时不要提交**
题目描述
农夫`john`最近在研究如果发生重大事故,如何让农场里的奶牛逃离问题。他想要确信在紧急情况下,所有的奶牛都有一个安全逃离方案。因为在紧急情况下,奶牛们都会失去观察和判断能力,所以最近`john`一直在教奶牛们逃离的方法,他的方法很简单,就是任何时候都只向北方或东方逃离,北方是行坐标减1的方向,东方是列坐标加1的方向。奶牛们虽笨,不过这一点事关自己的生命,所以他们牢记在心,而且也一定会这么做。
当然也会出问题,奶牛们在逃离的方向上会横冲直撞,为了阻止奶牛之间互相冲撞造成伤害,`john`要求任何一个奶牛的逃离路线不能经过其它奶牛的初始位置。一个逃离方案是安全的如果它能够满足上面的要求,反之它就是不安全的。
奶牛们所在的土地(农场)被划分成了$r$行和$c$列的一个矩形地图。奶牛们都待在这个矩形中的某一个位置。
请帮助`john`确定给定的一个地图上是否存在一个安全的逃离方案。
比如,下面的两个图:
左边的例子表示了一个能够安全逃离的地图,因为没有任何一个奶牛的逃离路线上包括其他奶牛。右边的例子表示了一个不安全的地图,因为位于$(4,1)$的奶牛不论是向东逃离还是向北逃离,它的路线上都会有别的奶牛,从这个图中拿掉任意一头奶牛,这个地图都会变成安全的。
```plain
安全 不安全
- ||||C-- C.....
- ||||C-- ^.....
- |C||C-- |.....
- CC++--- C-->C.
- ..CCC-- ......
```
`C` 表示奶牛,直线表示逃离路线。
输入输出格式
输入格式
第$1$行:两个整数$r,c$,用1个空格隔开,表示矩形的行数和列数(均 $\le 50$)。
第$2$行:一个整数$n$,表示奶牛的个数($ \le 100$)。
第$3$到$n+2$行:共$n$行,每行有$2$个整数,之间用$1$个空格隔开,分别表示这头奶牛所在的行和列。
输出格式
如果这块土地是安全的,输出 $0$。
如果移走任意一头奶牛这块土地还是不安全,输出 $-1$。如果移走一头奶牛就可以使这块土地安全,应从小到大输出所有符合要求的奶牛的编号,每个编号占一行。
输入输出样例
输入样例 #1
5 5
5
1 1
2 4
3 1
2 2
2 1
输出样例 #1
1
5