题目描述

给出一张有 N 个点和 M 条边的有向图，节点编号从 1 到N。

起点为 1，且每次只能去往相邻节点中编号最小的节点。

对于这样的一张图，若从起点出发，终点就已经被固定了。现在增加一个删边的操作，即可以选择若干条边将其从图上删除。

假如对于节点 1 有去往节点 3 和节点 2 的边，那么从节点 1 出发只能去往节点 2。如果我们删掉了 (1,2) 这条边，从节点 1 出发就可以去往 节点 3 了。

现在请你来计算是否可以在拿掉 x 条边之后，从节点 1 顺利到达节点 N ，若可以，输出最小的 x，否则输出“-1”。

输入格式

第一行给出一个正整数 T，代表测试数据的组数。

第一行两个以空格分隔的正整数 N,M，代表图上的节点数和边数。

接下来 M 行两个以空格分隔的正整数 a,b，表示一条从 a 到 b 的边。

1≤T≤200

1≤N≤50

0≤M≤N×(N−1)

输出格式

输出最小的 xx 或“-1”

谢谢