Second Good Path - Repovive Standard Round 4 | Repovive

11D. Second Good Path

2000 pts1s256 MB

You are given a connected undirected graph with $n$ vertices and $m$ edges.

The edges are indexed from $1$ to $m$ in the order they are given.

A path from vertex $1$ to vertex $v$ is called good if it has the minimum possible number of edges among all paths from vertex $1$ to vertex $v$ .

Two good paths ending at the same vertex are compared lexicographically by the sequence of edge indices along the path from vertex $1$ to that vertex.

For each vertex $v$ , find the second smallest good path ending at $v$ . If it exists, output the sum of the indices of the edges used in that path. Otherwise, output $-1$ .

For vertex $1$ , the answer is always $-1$ .

There may be multiple edges between the same pair of vertices. Self-loops are not allowed.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n - 1 \le m \le 2 \times 10^5$
$1 \le u_i, v_i \le n$
$u_i \ne v_i$
The graph is connected
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_n \end{array} \right\} \times t

Samples

Input

Case 1

2 1
1 2

Case 2

Case 3

Case 4

Case 5

Explanation

Case 1

For vertex $2$ , the shortest paths have length $1$ . There is only one good path: edge-index sequence $[1]$ , with vertex sequence $1 \to 2$ . Therefore, there is no second good path.

Case 2

For vertex $2$ , the shortest paths have length $1$ . The first good path has edge-index sequence $[1]$ , and the second one has edge-index sequence $[2]$ . Both have vertex sequence $1 \to 2$ , because the two edges are parallel. So the answer for vertex $2$ is $2$ .

For vertex $3$ , the shortest paths have length $2$ . The first good path has edge-index sequence $[1, 3]$ , with vertex sequence $1 \to 2 \to 3$ . The second one has edge-index sequence $[2, 3]$ , also with vertex sequence $1 \to 2 \to 3$ . So the answer for vertex $3$ is $2+3=5$ .

Case 3

For vertex $4$ , the shortest paths have length $2$ . The first good path has edge-index sequence $[1, 3]$ , with vertex sequence $1 \to 2 \to 4$ . The second one has edge-index sequence $[2, 4]$ , with vertex sequence $1 \to 3 \to 4$ . So the answer for vertex $4$ is $2+4=6$ .

Case 4

For vertex $4$ , the first two good paths have edge-index sequences $[1, 3]$ and $[2, 4]$ , so the answer is $2+4=6$ .

For vertex $5$ , the first two good paths have edge-index sequences $[1, 5]$ and $[2, 6]$ , so the answer is $2+6=8$ .

Case 5

For vertex $2$ , the first two good paths have edge-index sequences $[1]$ and $[2]$ , so the answer is $2$ .

For vertex $4$ , the first two good paths have edge-index sequences $[1, 3]$ and $[1, 4]$ , so the answer is $1+4=5$ .

For vertex $5$ , the first two good paths have edge-index sequences $[1, 3, 7]$ and $[1, 4, 7]$ , so the answer is $1+4+7=12$ .

For vertex $6$ , there is only one good path, with edge-index sequence $[5, 8]$ , so the answer is $-1$ .

Output

Case 1

-1 -1

Case 2

-1 2 5

Case 3

-1 -1 -1 6

Case 4

-1 -1 -1 6 8

Case 5

-1 2 -1 5 12 -1

You are given a connected undirected graph with $n$ vertices and $m$ edges.

The edges are indexed from $1$ to $m$ in the order they are given.

A path from vertex $1$ to vertex $v$ is called good if it has the minimum possible number of edges among all paths from vertex $1$ to vertex $v$ .

Two good paths ending at the same vertex are compared lexicographically by the sequence of edge indices along the path from vertex $1$ to that vertex.

For each vertex $v$ , find the second smallest good path ending at $v$ . If it exists, output the sum of the indices of the edges used in that path. Otherwise, output $-1$ .

For vertex $1$ , the answer is always $-1$ .

There may be multiple edges between the same pair of vertices. Self-loops are not allowed.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n - 1 \le m \le 2 \times 10^5$
$1 \le u_i, v_i \le n$
$u_i \ne v_i$
The graph is connected
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $m$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} ans_1 \quad ans_2 \quad \cdots \quad ans_n \end{array} \right\} \times t

For vertex $2$ , the shortest paths have length $1$ . There is only one good path: edge-index sequence $[1]$ , with vertex sequence $1 \to 2$ . Therefore, there is no second good path.

For vertex $4$ , the first two good paths have edge-index sequences $[1, 3]$ and $[2, 4]$ , so the answer is $2+4=6$ .

For vertex $5$ , the first two good paths have edge-index sequences $[1, 5]$ and $[2, 6]$ , so the answer is $2+6=8$ .

For vertex $2$ , the first two good paths have edge-index sequences $[1]$ and $[2]$ , so the answer is $2$ .

For vertex $4$ , the first two good paths have edge-index sequences $[1, 3]$ and $[1, 4]$ , so the answer is $1+4=5$ .

For vertex $5$ , the first two good paths have edge-index sequences $[1, 3, 7]$ and $[1, 4, 7]$ , so the answer is $1+4+7=12$ .

For vertex $6$ , there is only one good path, with edge-index sequence $[5, 8]$ , so the answer is $-1$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

11D. Second Good Path

Constraints

Input

Output

Samples

11D. Second Good Path

Constraints

Input

Output

Samples