11 人解决，36 人已尝试。
14 份提交通过，共有 183 份提交。
7.7 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
BonBon 在 ecnu 闲逛的时候被 NGB 恶魔捉走了，McFn 找到了 NGB 的巢穴–325 基地。325 基地机关重重，一不小心就会掉进陷阱被抓住 >_<. 现在 McFn 手上有一份基地构造的资料，可以知道基地中所有机关的位置。
基地是一个构造大小为 N x N 的迷宫，某些方格是机关，某些方格是安全空地。McFn 现在处在迷宫的入口 , 位置是在 (0,0) 的 , 也就是迷宫的左上角 .BonBon 被困在 (N-1,N-1) 的位置，也就是迷宫的右下角 .
由于对基地的安全设施很放心，所以 NGB 没有设置看守，但是在基地的每个角落都设置了一种特殊传感器 MST, 如果同一个物体在基地的行走的线路中转向次数太多的话，MST 就会报警 !(因为它知道你是在进行暴力回溯法搜索路径-_-)
由于不知道 MST 的具体数据，所以为了能够安全的救出 BonBon,McFn 必须尽量减少在基地迷宫的行走中转弯的次数。所以他想知道要到达 BonBon 的位置，最少需要转向的次数。
当然在入口处你可以随便选择一个方向作为初始的方向 , 不算入转向次数中 .
入口处和 BonBon 所在处的机关都被 McFn 和 BonBon 破坏了 , 所以可以忽略不计
第一行有一个整数 T，表示有 T 组测试数据
每组测试数据
第一行有两个整数 N,M.
N(2<=N<=500)，M 表示陷阱的个数 (0<=M<=1000000);
接下来有 M 行，每行有 2 个整数 xi,yi;
表示 xi,yi 这个地方有一个机关。
hint 同一个位置可能会有多个机关 !
每组测试数据输出一行，每行一个整数，要从基地入口走到 BonBon 的位置的所需要的最少转向次数。如果不存在一条路径 , 则输出 “Kryie!”.
2 3 2 1 1 1 2 3 3 1 0 1 1 1 2 input detail: .表示空格，#表示障碍 case 1: ... .## ... case 2: ... ### ...
1 Kryie!
11 人解决，36 人已尝试。
14 份提交通过，共有 183 份提交。
7.7 EMB 奖励。