Given an undirected graph with $n$ vertices and $m$ edges, where vertices are numbered $1 \sim n$.

Initially, there is a robot holding an item at vertex $1$. You can perform the following operations: 1. The robot places the item at an adjacent vertex; 2. The robot picks up the item from an adjacent vertex; 3. A robot not holding an item moves to an adjacent vertex that does not have an item placed on it.

Operations 1 and 2 take $1$ unit of time, while operation 3 takes $0$ time.

Find the minimum time for the robot to move to each vertex $2 \sim n$ while holding the item.

Input

The first line contains: * $T$

The following are $T$ test cases. For each test case: $n \ m$ $u_1 \ v_1$ $\dots$ $u_m \ v_m$

Output

For each test case: A single line containing $n-1$ integers, representing the minimum time to reach each vertex $2 \sim n$ while holding the item. If it is impossible to reach a vertex, output $-1$.

Examples

Input 1

4
4 4
1 2
2 3
3 4
4 1
5 5
1 2
2 3
3 4
4 5
5 1
5 6
1 2
3 2
1 3
3 5
5 4
3 4
9 12
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
3 6
6 9
9 3

Output 1

-1 2 -1
4 2 2 4
2 2 4 4
2 2 6 6 4 6 6 4

Subtasks