#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/11/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Second Good Path - Repovive Standard Round 4 | Repovive | 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$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

11D. Second Good Path

Constraints

Input

Output

Samples

11D. Second Good Path

Constraints

Input

Output

Samples