Lexicographically Smallest Path Concatenation

You are given an undirected graph with n nodes and m edges. Each node is identified by a 6‐digit string starting from 000000 for node 0, 000001 for node 1, and so on up to the node n−1. It is guaranteed that n ≤ 10⁶, so the 6‐digit representation is always valid.

For every node except node 000000, you must find a simple path (i.e. no repeated nodes) from node 000000 such that when you concatenate the 6‐digit labels of all nodes along the path, the resulting string is the lexicographically smallest among all possible simple paths from 000000 to that node. The lexicographical comparison is defined as follows: if one string is a prefix of the other, then the shorter string is considered smaller; otherwise, the first position at which the two strings differ determines the order (the one with the smaller digit at that position is considered smaller).

Since outputting the entire path is cumbersome, you only need to interpret the concatenated string as an integer and output its value modulo 998244353. If a node is unreachable from node 000000, output -1 for that node.

Note: The 6-digit string for a node v is obtained by formatting the integer v with leading zeros (for example, node 1 is represented as 000001).

inputFormat

The first line contains two integers n and m — the number of nodes and edges respectively.

Each of the next m lines contains two integers u and v (0 ≤ u, v < n), representing an undirected edge between nodes u and v.

outputFormat

Output n − 1 space‐separated integers. For each node from 1 to n − 1, print the integer (obtained by interpreting the lexicographically smallest concatenated path as a number) modulo 998244353. If a node is unreachable, print -1 for that node.

sample

3 2
0 1
1 2

1 1000002