No submission language available for this problem.

题目描述

根据以上信息，我们可以得到Javaville城市可能的两种布局。我们发现：住宅1，邮局和学校的位置都已经确定了，而住宅2可以位于C0或E2，住宅3可以位于C0或E2。于是，城市中总是存在两座住宅相距6个街区（地图1中的h1与h3，地图2中的h1与h2）。但是，对于确定的两座住宅，我们可以保证的最长距离只有4个街区 (h2与h3的距离总是4个街区)。于是，我们要告诉Bill和Scott，尽管总是存在两座相距6个街区的住宅，然而最安全的建议是：一人购买住宅2，另一人购买住宅3。

下面给出所求数值的严格定义：

l        一个可行的城市布局S的直径d(S)定义为该布局中距离最远的两座住宅之间的距离。

l        对于确定的两座住宅i, j，它们的安全系数e[i, j]定义为在所有可行的城市布局中，住宅i, j之间的距离的最小值。

Bill和Scott希望你编写一个程序，根据他们所搜集到的信息，计算出D和E。其中：D =min{d(S) }；E =max{e[i, j]}。同时你还要给出最安全的购房建议，即所有满足e[i, j]=E的住宅i, j。

对于上面的例子，第一种布局的d(S₁)=6，第二种布局的d(S₂)=6。每两座住宅之间的安全系数是：e[1,2]=2，e[1,3]=2，e[2,3]=4。于是：D= min{d(S₁),d(S₂)}=6，E= max{e[1,2],e[1,3],e[2,3]}=4，最安全的购房建议是：住宅2与住宅3。

 

输入格式

第一行包含两个正整数m, n（1<=m, n<=10），分别表示东西走向的街道数目和南北走向的街道数目。第二行包含一个整数，表示所搜集到的信息条数t(1<=t<=50)。文件从第三行开始每行描述一条所搜集到的信息，每条信息都是以下两种形式之一：

       name  LOCATION  r  c

或者

       name  DISTANCE  d  name2

       这两种形式分别描述建筑物的位置和建筑物之间的距离。

其中，name和name2是仅包含数字和小写字母的字符串，长度不超过20，表示建筑的名称。r是A到J之间的大写字母，c是一个数字，表示建筑物所位于的交叉路口。d是一个正整数，表示两座建筑物之间的距离。如果建筑物名称的前五个字符是小写字母“house”，那么表示这是一座可以购买的住宅，否则表示一座非民用的建筑物。如果信息是第二种形式，那么其中的name2一定在前面的信息中出现过。

这组信息中至少包含两座可以购买的住宅，至多包含25座不同的建筑物。

 

输出格式

第一行包含两个整数，分别表示D和E，之间用一个空格隔开

5 5
6
house1 LOCATION A 0
postoffice LOCATION A 4
school DISTANCE 4 house1
house2 DISTANCE 6 postoffice
school DISTANCE 6 postoffice
house3 DISTANCE 6 postoffice

6 4