【题目描述】

有 $T$ 组数据。一座魔塔有 $n$ 层和 $m$ 个双向传送梯。第 $i$ 个传送梯连接楼层 $u_i,v_i$，使用它不花时间。

在第 $x$ 层还可以花 $1$ 分钟到达 $x-1$ 或 $x+1$ 层（楼层存在时）。求从第 $1$ 层到第 $n$ 层的最少时间。

【输入格式】

$T$

$n$   $m$

$u_1$   $v_1$

$\vdots$

【输出格式】

每组输出一行最少时间。

【样例】

2
5 1
2 5
6 2
1 3
4 6

1
1

【数据范围】

• $1\le T\le10$
• $1\le n\le200000$
• $0\le m\le200000$
• 所有数据的 $n+m$ 总和不超过 $400000$