WARush

Description

Input

Output

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

按照出线先后顺序依次是：

就是在2010年11月21日下午2:30分整，acm福州赛区比赛结束了。这时也证实了跟我生活了3年的同学已经晋级了acm世界总决赛，去埃及比赛的愿望终于实现了。

回想起当年刚刚认识毛杰、王瑞和郭威的时候，只是感觉他们除了韧性并没有什么过人之处。

仍然记得三年前的一个傍晚，毛杰问我acm是什么的时候，他表示想好好学习什么是计算机编程。当时我们也曾谈过自己的理想，他说，他想出国，想去MIT，也曾记得当时我跟他在一起看一篇名叫《弱校acm的奋斗史》的文章，当时看后发现当时文中人描述的集训的生活是如此的艰苦：

到了大二，我们更加努力的集训，在北京之前，我们第一次尝试了全天集训的滋味。30天90袋跑面20袋咸菜，每天4个小时的睡眠。当时我觉得我们一定会崩溃的，当我每次快要崩溃的时候，总会记起当时我们的话：“我们才大一，我们喜欢ACM，我们还有的拼，我们能拼。”于是，就奇迹一样的继续做题。
现在想起来，那真的是个奇迹，LIANG HH居然可以一个月只在床上躺了6个晚上，平均每天睡2个小时。
就这样，我们在北京的时候，绝对意外的拿了第5名的成绩，当时的感觉绝对不是语言可以形容的，当时只是在想：我们终于证明自己了。
但是，这也是要代价的，LIANGHH回来就垮了，其他的人也不是很好受。但是，队长还是决定了去印度拼一下。决定的结果是：继续集训。那些日子我不愿意再回忆，也不愿意再来一次，但是，如果我必须要再来一次的话，我相信，我不会犹豫，因为：我喜欢ACM。

不知是被这种生活所激励还是被acm的竞赛精神所鼓舞，一头钻入实验室三年后终于再见天日。老毛不但在acm收获老友情、亲情、当然还有成绩跟爱情。相信这一刻的老毛会有很多感慨，也可以想的得出远在福州他的小小的激动，然后淡然接受这个成绩。

两年前认识老郭威，对于他，刚刚开始就只有 这么个印象：拖鞋+烟+火+dota+老婆，后来慢慢熟悉的过程中发现，他的思想的高度如此之高，只能膜拜，顶礼膜拜，在无数个彻夜长谈（章月大人请谅解，我占用老不少属于您的郭大侠的时间= =#）中我的庸俗的思想慢慢升华，从这里，我学会了对我影响极大的几句话“无所谓”、“随意”、“看着办”、“不解释”……我们无话不谈，谈到重点时，会心一笑。呵呵，天才是存在的，但思想上的天才是没有的。用梦驰的话说就是：“绝版！”

王瑞小盆友，应该算是认识的早，熟悉的晚的同学，给我的第一印象应该是跟我的初中的信息技术老师差不多，人长得不算标准，但是人品是没得说，低调，稳重，实在。

我想，大多数人是没有跟他们进行过非常深入的交往的，三年的时间，每天至少12小时以上在实验室中进行学习和练习，只为acm世界总决赛，呵呵，没有多么过人的智商，只有韧性和坚持而已。另外必须有清醒的头脑。

每日惶惶而过，并不能换来真正的实力，芸芸浮生，争名逐利，流年过往，浮华退去时，真正的硬实力又有什么呢？

附上许信顺老师的一句话：“如果做科研的人每天睡觉时间超过6个小时，研究时间不足12小时，无法专注的话，这个人将会碌碌无为。”

后附：《弱校acm的奋斗史》给他们，也留给自己……

不知道什么时候，开始知道ACM；也不知道什么时候，开始喜欢上ACM。但是，我知道，我喜欢上了，而且不会后悔。我是大一的时候进的学校ACM队，那个时候，一切都是冰冷的，华东理工大学，在别人的眼里，只是每次给别人垫底的学校，次次如此。
但是，我们不甘心，我们从不甘心，当我们主力队员中的一个，一个月拼命集训，瘦了很多的时候，突然，我有一种哭的冲动。我问他，为什么？他告诉我：我喜欢ACM。也许是个傻傻的理由，但是就是这句话让我一直留在了这里，并且为了这个梦奋斗着。
也许是天资的原因，第一次，我们失败了，彻底的失败了，在上海输的好惨，也使得我们第二年的经费雪上加霜。曾经的梦想，曾经的努力，似乎在一刹那间被否定了。也就在那个时候，有人说了一句：我们只有大一，我们的路还长，于是，我就坚持了下来。
现在看看大一时候的我们，真的是什么都不会的一些人。

到了大二，我们更加努力的集训，在北京之前，我们第一次尝试了全天集训的滋味。30天90袋跑面20袋咸菜，每天4个小时的睡眠。当时我觉得我们一定会崩溃的，当我每次快要崩溃的时候，总会记起当时我们的话：“我们才大一，我们喜欢ACM，我们还有的拼，我们能拼。”于是，就奇迹一样的继续做题。
现在想起来，那真的是个奇迹，LIANG HH居然可以一个月只在床上躺了6个晚上，平均每天睡2个小时。
就这样，我们在北京的时候，绝对意外的拿了第5名的成绩，当时的感觉绝对不是语言可以形容的，当时只是在想：我们终于证明自己了。
但是，这也是要代价的，LIANGHH回来就垮了，其他的人也不是很好受。但是，队长还是决定了去印度拼一下。决定的结果是：继续集训。那些日子我不愿意再回忆，也不愿意再来一次，但是，如果我必须要再来一次的话，我相信，我不会犹豫，因为：我喜欢ACM。

在印度的出现绝对不是一个奇迹，也不是运气，里面包含了苦涩，无奈，还有很多很多，当然最多的还是欣喜。
至于总决赛么，呵呵，就是去玩玩，也没有别的意思了。

我真的希望
大家加油！！！

不是因为别的原因，因为我们都曾经迷惑，无助，我们没有别人那么强的教练，没有别人那么好的基础，但是，我们都绝对不能放弃。绝对不能，因为，当我们坐在赛场上的时候，不管你是不是愿意，在你上空飘动的始终是你的校旗，别误会，我不是说什么要“为了学校争光”，那种话是用来哄小孩子的。我只想问大家，如果是你，坐在电脑前~~，你的背后有多少人在看着你？你的身上寄托的是什么？
是希望，是所有喜欢ACM的同学对你的希望，希望有这么一天，ACM也可以象其他的东西一样被其他的人所肯定，而不是什么需要被人怜悯的东西！！！！！！！！！
是信任，是所有曾经帮助过你和被你帮助过你的人对你的信任，想想为了经费而受尽了苦的人们，想想其他曾经一起集训的队员们的信任。他们信任你，你们会是最好的。只要你们尽力了，你们就是英雄。不过，没有人同情失败的英雄吧。所以，我们必须成功。

还有，是耻辱，是一种被轻视和忽视的耻辱，不知道你们有没有这样的经历，当初我们想找一个比我们水平高的学校共同学习一下，谁知道竟然换来的是一句：“就你们？”也许你们没有遇到过想我们一样尴尬的场面，不过，我相信，这种感觉在你们心里也很深刻吧。从很多地方都能体会到。

如果，现在我们寄托了这些东西的话，谁还会告诉我：我们不该奋斗呢？

如果可以，我宁愿安静的呆在一个不为人知的小角落，平平淡淡的过了这大学四年的生活，至少不会这么累。
如果可以，我宁愿在开始的时候，就找一个可以依靠的地方，傻傻的什么都不想，幸福的过了这四年。
如果可以，我宁愿只做一个ACM的看客，静静的品味他们成功的喜悦，分担失败的痛苦。

如果可以，我宁愿早早的放弃着艰苦的训练，因为我实在不愿意再做这样一个噩梦。
如果、可以…………

但是，只是如果……
而且，决不可以！！

当我们弱校的人喜欢上ACM的时候，就应该有这种觉悟！
如果，要后退，那么，就你就不要参加ACM，因为，你不适合。ACM比的并不仅仅是写程序的水平，而更多是三个人的综合素质。没有胆小的人可以赢得ACM的青睐，没有退缩的人可以赢得比赛的胜利。我们这些人，水平本来就有限，也没有什么很出色专业教练。那么如果我们连一拼的勇气都没有了。我们还剩下什么？

如果可以，让我再次站在大一时候的海报前，我还是会小声的说：“去试试吧，也许很好玩呢~~”

谢谢大家看了这么多，是不是烦了？呵呵，最后，我只希望大家能+U，同时弱校的队员，

我希望我们能互相帮助。

大家~~~~~~~~加油~~~~~~~~~

模版的使用，Bellman-Ford算法，复杂度O(VE)，可解决负权边，判别负权回路。

额外采用Yen氏改进，但不降低渐进复杂度。还可采用队列优化成SPFA(Shortest Path Faster Algorithm)。