Your little sibling has a connected undirected graph of (n) vertices and (m) edges. The vertices are numbered from (1) to (n), and the edges are numbered from (1) to (m). Edge (j) connects vertices (u_j) and (v_j) with a positive integer weight of (w_j). Your little sibling coded Dijkstra's algorithm to find the shortest distances from vertex (1) to all other vertices, as shown in the pseudocode below. The array (S) records the order in which each vertex is popped from the heap for the first time. Note that even though tuples for each vertex may be pushed multiple times into the heap, each vertex is added to (S) exactly once. However, your little sibling made a big mistake. In your sibling's code, the heap always pops the maximum tuple instead of the minimum tuple. Here, the heap orders tuples lexicographically by ((\mathit{dist}, u)), with larger (\mathit{dist}) considered larger; ties are broken by larger (u). Your little sibling shares the graph structure with you, that is, all pairs of (u_j) and (v_j) ((1 \le j \le m)). However, your sibling does not share the edge weights (w_j). Instead, your sibling shares an array (S = (s_1, s_2, \ldots, s_n)) with you and asks you to reconstruct the edge weights. Your task is to find integer edge weights (w_1, w_2, \ldots, w_m) ((1 \leq w_j \leq 10^9) for all (j)) such that running your sibling's incorrect code yields the given array (S). Find any such assignment of edge weights. If no such assignment exists, report that it is impossible. The first line of input contains two integers (n) and (m) ((2 \leq n \leq 100\,000); (n-1 \leq m \leq 200\,000)). The (j)-th of the next (m) lines contains two integers (u_j) and (v_j) ((1 \leq u_j \lt v_j \leq n); ((u_j, v_j) \neq (u_k, v_k)) for all (j \neq k)). The input guarantees that the graph is connected. The next line contains $$$