Raiffeisenbank 的一项重要业务任务是改进在银行、客户、取货点和其他地点之间运送卡片、贵重物品、文件等的过程。你参与了一个试点项目，计划通过使用无人机和最优路径算法来彻底改变物流世界。

你现在正在一个由 $n$ 个着陆点组成的现场训练场进行首次测试。无人机位于 1 号点，需要飞往 $n$ 号点。无人机的遥控器可以运行 $m$ 个路由程序，第 $i$ 个程序能够将无人机从 $u_i$ 点移动到 $v_i$ 点（如果无人机不在 $u_i$ 点，程序将不执行任何操作），并且它是使用第 $t_i$ 版本的无人机控制库编写的。由于这是你项目的首次测试之一，你不确定不同软件版本之间的兼容性，因此你运行的每个路由程序（除了第一个）的无人机控制库版本必须严格大于前一个程序。

在查看了路由程序的代码后，你发现可以对其进行微小的修改。具体来说，你可以选取任何程序 $i$ 并交换其起点和终点。因此，如果第 $i$ 个程序原本将无人机从 $u_i$ 点移动到 $v_i$ 点，修改后它将从 $v_i$ 点移动到 $u_i$ 点。库版本 $t_i$ 保持不变。

现在你想知道，为了使存在一个程序序列 $p_1, p_2, \dots, p_k$，按此顺序运行可以将无人机从 1 号点移动到 $n$ 号点，且满足 $t_{p_1} < t_{p_2} < t_{p_3} < \dots < t_{p_k}$，你需要修改的最少程序数量是多少。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 500\,000, 1 \le m \le 500\,000$)，分别表示训练场上的着陆点数量和路由程序数量。

接下来 $m$ 行，第 $i$ 行描述第 $i$ 个程序，包含三个整数 $u_i, v_i$ 和 $t_i$ ($1 \le u_i, v_i \le n, 1 \le t_i \le 10^9$)，表示该程序将无人机从 $u_i$ 点移动到 $v_i$ 点，并使用第 $t_i$ 版本的无人机控制库。

可能存在多个使用相同软件版本的程序。可能存在连接同一对点（在每个方向上）的多个程序。可能存在将无人机从某一点移动到其自身的程序。

保证所有测试用例中 $n$ 的总和不超过 $500\,000$。保证所有测试用例中 $m$ 的总和不超过 $500\,000$。

输出格式

如果无法通过修改程序来满足“每个后续运行的程序必须具有更大的无人机控制库版本”这一条件，从而将无人机从 1 号点移动到 $n$ 号点，则在输出的唯一一行中打印 -1。

否则，打印实现该目标所需修改的最少程序数量。

样例

样例输入 1

1
4 3
2 1 1
2 3 2
4 3 3

样例输出 1

2

样例输入 2

2
4 3
2 1 1
2 3 2
4 3 2
8 9
1 2 5
2 3 10
4 3 15
4 5 20
5 8 25
1 6 2
6 5 30
7 6 3
8 7 4

样例输出 2

-1
1