UVA1021 Eurodiffusion

$2002$ 年 $1$ 月 $1$ 日，十二个欧洲国家放弃了本国货币，转而使用一种新货币——欧元。在欧元区内，不再有法郎、马克、里拉、荷兰盾、克朗……只有欧元。所有国家使用相同的纸币。那么硬币呢？也不完全相同。每个国家在创建自己的欧元硬币时有一定的自由度： “每个欧元硬币都有一个共同的欧洲面。在正面，成员国可以用自己的图案装饰硬币。无论硬币上印有什么图案，它都可以在 $12$ 个成员国中的任何地方使用。例如，一个法国公民可以使用印有西班牙国王头像的欧元硬币在柏林购买热狗。”（来源：http://europa.eu.int/euro/html/entry.html） $2002$ 年 $1$ 月 $1$ 日，巴黎唯一可用的欧元硬币是法国硬币。很快，第一批非法国硬币出现在巴黎。最终，人们可能会预期所有类型的硬币在十二个参与国家中均匀分布。（实际上，这并不完全正确。所有国家都会继续铸造和分发带有自己图案的硬币。因此，即使在稳定状态下，柏林也应该会有过多的德国硬币。）那么，芬兰或爱尔兰的硬币需要多长时间才能在南意大利流通？每种图案的硬币需要多长时间才能在所有地方出现？ 你必须编写一个程序来模拟欧元硬币在整个欧洲的传播，使用一个高度简化的模型。将注意力限制在单一欧元面额上。将欧洲城市表示为矩形网格中的点。每个城市最多有 $4$ 个邻居（北、东、南、西各一个）。每个城市属于一个国家，而国家是平面上的一个矩形部分。下图显示了一个包含 $3$ 个国家和 $28$ 个城市的地图。国家的图是连通的，但国家可能与非欧元国家（如瑞士或丹麦）或海洋接壤。最初，每个城市都有 $100$ 万（$1000000$）枚本国图案的硬币。每天，基于城市当天的初始余额，将一部分硬币运输到该城市的每个邻居。代表性部分定义为每 $1000$ 枚硬币中的 $1$ 枚。 当一个城市中至少存在一枚每种图案的硬币时，该城市被认为是完成的。当一个国家的所有城市都完成时，该国家被认为是完成的。你的程序必须确定每个国家完成所需的时间。

输入由多个测试用例组成。每个测试用例的第一行是国家的数量（$1 \le c \le 20$）接下来的 $c$ 行描述每个国家。国家的描述格式为：$name$ $x_1$ $y_1$ $x_h$ $y_h$ ,其中 $name$ 是至多 $25$ 个字符的单词；$x_1$ 、$y_1$ 是该国家左下角城市的坐标（最西南的城市）， $x_h$ 、$y_h$ 是该国家右上角城市的坐标（最东北的城市）。 $1 \le x_1 \le x_h \le 10$ 且 $1 \le y_1 \le y_h \le 10$。 输入的最后一个用例后跟一个 $0$.

对于每个测试用例，打印一行表示用例编号，然后为每个国家打印一行，包含国家名称和该国完成所需的天数。按完成天数对国家进行排序。如果两个国家的完成天数相同，则按名称字母顺序排序。