题目内容

某快递分拣中心有 $m$ 个分拣口，编号从 $1$ 到 $m$。包裹一开始放在 $1$ 号口，需要送到 $m$ 号口。

每个分拣口都配置了一条传送带：若包裹当前停在第 $i$ 号口，可以支付 $1$ 次跳转费用，把它送到闭区间 $[a_i,b_i]$ 内的任意一个分拣口（任意整数口位 $j$ 满足 $a_i\le j\le b_i$）。

请计算：把包裹从 $1$ 号口送到 $m$ 号口，最少需要几次跳转。若怎样跳都到不了，则视为无解。

输入描述

第一行一个整数 $g$（$1\le g\le 2\times 10^5$），表示询问组数。

接着共有 $g$ 组数据，每一组格式如下：

第一行一个整数 $m$（$1\le m\le 2\times 10^5$），表示分拣口个数。

第二行 $m$ 个整数 $a_1,a_2,\dots,a_m$。

第三行 $m$ 个整数 $b_1,b_2,\dots,b_m$。

保证对每个 $i$ 都有 $1\le a_i\le b_i\le m$，且同一文件内所有 $m$ 之和不超过 $4\times 10^5$。

输出描述

输出一行，包含 $g$ 个整数，相邻整数之间用单个空格隔开。

第 $t$ 个数表示第 $t$ 组询问的答案：最少跳转次数；若无法送达则输出 -1。

样例1

输入

3
6
2 3 5 6 6 6
4 5 6 6 6 6
4
1 1 1 4
2 2 2 4
1
1
1

输出

2 -1 0

说明

第一组：$m=6$。一条最优路线是 $1\to 3\to 6$，共跳 $2$ 次；也可走 $1\to 4\to 6$，同样是 $2$ 次。

第二组：从 $1$ 号口只能在 $\{1,2\}$ 之间往返，永远进不了 $4$ 号口，故为 -1。

第三组：起点即终点，无需跳转，答案为 $0$。