在一片神秘的大陆上，存在一个由N个城堡和M条秘密通道组成的古老帝国。每个城堡都有一个独特的编号，从1到N。每条秘密通道也有自己的编号，从1到M。第i条通道（1 ≤i ≤M）连接城堡s_{i}和城堡t_{i}，并且其长度为1单位。

注意秘密通道都是单向的。

一天，古老帝国的国王决定对所有通道进行检查，以确保它们的安全性。他希望知道，如果某条通道因突发事件而无法通行，那么从帝国的起点城堡1到终点城堡N的最短距离是多少。如果在某条通道无法通行的情况下，无法从起点城堡到达终点城堡，那么他希望得到一个标记-1。

具体来说，对于每条通道i（1 ≤i ≤M），你需要计算并告知国王，如果该通道无法通行时，从起点城堡1到终点城堡N的最短距离。如果无法从起点城堡1到达终点城堡N，请输出-1。

这个任务至关重要，因为它不仅关系到帝国的安全，也关系到国王的威信和人民的幸福。你能帮助国王完成这个任务吗？

输入第一行，两个正整数N和M

接下来M行，每行两个整数s_{i}和t_{i}，表示每条单向的秘密通道。

对于每条通道i（1 ≤i ≤M），你需要计算并告知国王，如果该通道无法通行时，从起点城堡1到终点城堡N的最短距离。

如果无法从起点城堡1到达终点城堡N，请输出-1。

对于20\%的数据满足：2 ≤N ≤10

对于40\%的数据满足：2 ≤N ≤80

对于100\%的数据满足：2 ≤N ≤300,1 ≤M ≤N \times (N-1),1 ≤s_{i}, t_{i} ≤N,s_{i} ≠t_{i}

对于任意的i ≠j，(s_{i}, t_{i}) ≠(s_{j}, t_{j})