VariantF在Minecraft中走着走着突然迷了路。Minecraft世界中有N座房屋，他目前所在的地方是1号房屋，而VariantF的家在N号房屋。每两座房屋之间都有一条长度为1的有向道路相连，但是由于某些道路上有僵尸、骷髅射手、蜘蛛、JJ怪、末影人等怪物，或者是岩浆、湍流、悬崖等恶劣环境，所以这些道路是不能通过的。道路的连接情况用一个N*N的01矩阵表示，如果矩阵中第i行第j列是1，那么从i到j的道路可以通过，否则不能。现在VariantF想尽快回到家，你能帮他求出从1到N的最短路径吗？

输入数据的第一行是一个整数N。 接下来N行每行N个字符'0'或'1'，中间没有空格，表示描述道路连接情况的01矩阵。 Pascal选手请注意：由于本题内存限制较小，读入一行字符串可能会出现异常情况，强烈建议您使用repeat读入单个字符！ 示例读入代码如下（ch:char;为当前要读入的字符）： repeat read(ch); until (ch='0')or(ch='1');

输出一个整数，表示从1到N的最短路长度。

3
010
101
111

2

请注意本题的内存限制T_T 另外，这1MB内存中包含程序编译和头文件、类库所占的内存，您在计算程序消耗的内存时应该把这部分内存计算在内！ 在Tyvj上，编译运行一段包含主要头文件、不含任何变量的C++