G. Google Maps Does Not Work Here
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You live in a city with a mysterious transportation network consisting of $$$n$$$ locations and $$$m$$$ bi-directional roads. For the $$$i$$$-th road ($$$1\leq i \leq m$$$), the time taken to travel across it is $$$2^{i-1}$$$ minutes.

Alice is new to the city and is getting ready for her road trips. However, to her horror, Google Maps is not available in this city!

Alice turns to you, an aspiring competitive programmer. Alice's house is located at location $$$1$$$. For every location $$$v$$$ ($$$2\leq v \leq n$$$), please help Alice find the minimum travel time from location $$$1$$$ to location $$$v$$$, and output that time modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t \leq 10^3$$$), the number of test cases. For each test case,

  • The first line consists of two integers $$$n$$$ and $$$m$$$ ($$$2\leq n \leq 2\times 10^5$$$, $$$1\leq m \leq 5\times 10^5$$$), denoting the number of nodes $$$n$$$, the number of bi-directional roads $$$m$$$.
  • The following $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1\leq u,v\leq n$$$, $$$u\neq v$$$), denoting a bi-directional road between locations $$$u$$$ and $$$v$$$. The $$$i$$$-th road listed in the input takes $$$2^{i-1}$$$ minutes to travel across.
Additional constraints on input:
  • The sum of $$$n$$$ over all test cases will not exceed $$$2\times 10^5$$$.
  • The sum of $$$m$$$ over all test cases will not exceed $$$5\times 10^5$$$.
  • The transportation network is a simple graph, with no multiple edges or self-loops.
Output

$$$t$$$ lines. For each test case, output one line containing $$$n-1$$$ integers $$$d_2, d_3,\cdots, d_n$$$, where $$$d_i$$$ is defined by:

  • If at least one path exists from location $$$1$$$ to location $$$i$$$, then $$$d_i$$$ should be the minimum possible travel time from location $$$1$$$ to location $$$i$$$, modulo $$$998244353$$$. Note that the travel time itself should be minimized before taking the result modulo $$$998244353$$$.
  • Otherwise, $$$d_i$$$ should be -1.
Example
Input
1
6 7
2 3
3 4
2 4
4 5
2 5
1 5
1 2
Output
43 42 40 32 -1
Note

There is $$$1$$$ test case. The figure below provides a visualisation.

Illustration of the sample test case

The minimum travel time routes from location $$$1$$$ are as follows:

  • To location $$$2$$$: $$$1 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 2$$$. The total travel time is $$$2^5 + 2^3 + 2^1 + 2^0 = 32 + 8 + 2 + 1 = 43$$$ minutes. Therefore, $$$d_2 = 43 \bmod 998244353 = 43$$$.

  • To location $$$3$$$: $$$1 \rightarrow 5 \rightarrow 4 \rightarrow 3$$$. The total travel time is $$$2^5 + 2^3 + 2^1 = 32 + 8 + 2 = 42$$$ minutes. Therefore, $$$d_3 = 42 \bmod 998244353 = 42$$$.

  • To location $$$4$$$: $$$1 \rightarrow 5 \rightarrow 4$$$. The total travel time is $$$$$$ 2^5 + 2^3 = 32 + 8 = 40 $$$$$$ Therefore, $$$d_4 = 40 \bmod 998244353 = 40$$$.

  • To location $$$5$$$: $$$$$$ 1 \rightarrow 5 $$$$$$ The total travel time is $$$$$$ 2^5 = 32 $$$$$$ Therefore, $$$d_5 = 32 \bmod 998244353 = 32$$$.

  • Location $$$6$$$ is unreachable from location $$$1$$$, so $$$d_6 = -1$$$.