For the remainder of the editorial, we'll let ~\text{deg}(x)~ denote the degree of node ~x~.

Since the graph is a tree, there exists a unique path from node ~1~ to ~N~. Observe that in order for Alice to always reach node ~N~, this path must be a line graph. That is, ~\text{deg}(1) = 1~ and every intermediate node on the path must have degree ~2~.

Why is this? Consider what happens if Alice arrives at a node ~n \ne N~ with ~\text{deg}(n) \ne 2~. If ~\text{deg}(n) = 1~, Alice is at a dead end and can't continue. If ~\text{deg}(n) \ge 3~, Alice chooses between two edges, of which only one of them is on the path to node ~N~. No matter how Alice reaches node ~n~, there is always the possibility of Alice not taking the edge on the path to node ~N~.

Once we determine if the path satisfies the above requirements, any assignment of edge weights should suffice since Alice's path is already predetermined.

~\mathcal{O}(N)~

Build a graph where every node can reach node ~N~.

In this subtask, Alice always chooses between ~2~ edges at each node.

Consider a directed acyclic graph ~G~ of maximal size with the following properties:

• Node ~N~ is in ~G~ and has an outdegree of ~0~
• Every node ~x \in G~ excluding node ~N~ has an outdegree of exactly ~2~

It follows that if Alice starts at a node in ~G~, she can always be forced to reach node ~N~ since we can set the ~2~ outgoing edges to be the min and max edge at her current node. Furthermore, if Alice doesn't start in ~G~, we cannot guarantee that Alice can always reach node ~N~. Why? Since no matter how she got to that node, she will choose between ~2~ edges, of which at most ~1~ of them takes her into ~G~. This means she can always take an edge to some node not in ~G~. This results in an infinite loop, so Alice can never reach node ~N~.

Thus, we want to determine if node ~1~ is in ~G~. This inspires us to run our own version of topological sort.

We try to construct ~G~, which initially only contains node ~N~. On each iteration, we find a node ~x~ that has at least ~2~ edges connecting to nodes in ~G~. If such an ~x~ exists, we add it and the ~2~ edges we used to ~G~, where the ~2~ edges become outgoing edges from ~x~. We repeat this process until node ~1~ is in ~G~ or there are no more nodes to add.

How can we assign edge weights to maintain these properties? When we add the ~2~ edges to ~G~, we can set their weights to be the minimum and maximum unused edge weights (call them ~a~ and ~b~ respectively with initial values of ~1~ and ~M~). This works because when we label the remaining edges that connect to node ~x~, they will have a weight strictly between ~a~ and ~b~. Hence Alice will still pick the same edges, no matter how she arrived at node ~x~.

If node ~1~ is in ~G~ after running the "topological sort", we simply label the remaining edges with weights in the interval ~[a,b]~ and we're done. Otherwise, there is no solution.

~\mathcal{O}(N+M)~

What happens if Alice visits node ~1~ again? When would this make a difference?

In this subtask, the number of edges Alice chooses at each node can vary. We let ~c(x)~ represent the number of edges Alice could take if she was at node ~x~. We have:

$$\displaystyle c(x) = \begin{cases} \min(\text{deg}(x), 2) & \text{if } x = 1 \\ \min(\text{deg}(x)-1, 2) & \text{otherwise} \end{cases}$$

To accomodate this, we modify the second requirement of ~G~ so that every node ~x \in G, x \ne N~ has an outdegree of exactly ~c(x)~.

We first run the same process described in subtask 2 but with some slight modifications to account for when ~c(x) \ne 2~. If this does not yield a solution, there is one remaining case to check for. To see it, we make the following observations:

Let's examine node ~1~ and the definition of ~c(1)~. When Alice is initially at node ~1~, ~c(1) = \min(\text{deg}(x), 2)~. However, if Alice arrives at node ~1~ again, we now have ~c(1) = \min(\text{deg}(1)-1, 2)~. In particular, the value of ~c(1)~ changes if ~\text{deg}(1) = 1~ or ~\text{deg}(1) = 2~. If ~\text{deg}(1) = 1~, Alice will stop at node ~1~ so this doesn't work. If ~\text{deg}(1) = 2~, there are two cases. Let ~g(x)~ denote the number of edges that connect a node ~x \notin G~ to a node in ~G~. If ~g(1) = 0~, there is still no solution. However, if ~g(1) = 1~, a solution may exist. Starting from node ~1~, Alice could either take the edge that leads to ~G~ or take the other edge. If Alice takes the latter edge, it is possible for Alice to eventually be forced to either take an edge that goes into ~G~ or take this edge back to node ~1~, which forces her into ~G~.

To check for this case, we again run the "topological sort" described in subtask 2, except this time we define ~c(1)~ to be ~\min(\text{deg}(1)-1, 2) = 1~. Furthermore, we let ~\text{ins}(x)~ denote the order of when node ~x~ was added to ~G~. Thus, ~G~ has the following additional properties:

• ~\text{ins}(N) = 1~
• For all ~x \in G~, the ~c(x)~ outgoing edges from node ~x~ connect to nodes with lower ~\text{ins}~ values.

We claim that a solution exists if and only if the following conditions hold:

• There exists an edge ~e~ connecting nodes ~u~ and ~v~, where ~u,v \in G~ and ~e \notin G~. WLOG ~\text{ins}(u) < \text{ins}(v)~.
• Let ~\{s_i\}_{i \in \mathbb{N}}~ represent the sequence of nodes on a path of length ~k~ from node ~1~ to node ~u~ (~s_1 = 1~ and ~s_k = u~), where ~\text{ins}(s_1) < \text{ins}(s_2) < \ldots < \text{ins}(s_k)~.
  Then let ~\{p_i\}_{i \in \mathbb{N}}~ denote the sequence of edges on this path, where ~p_i~ is the edge she takes to get from node ~s_i~ to ~s_{i+1}~. This path must exist and ~\{s_i\}, \{p_i\} \in G~.

In addition, we have a process of determining such ~\{s_i\}, \{p_i\}~, if they exist.

Using the process outlined in the above proof, we can find a possible ~\{s_i\}~ and ~\{p_i\}~ by performing a DFS traversal starting from node ~1~. Implementation is left as an exercise to the reader. If such ~\{s_i\}~ and ~\{p_i\}~ exist, we rerun "topological sort" in order to relabel the edges. The following modifications are made:

• Initialize ~b~ (recall ~b~ is the maximum unused edge weight) as ~M-k+1~, since we reserve ~M-k+2,\ldots,M~ for labelling edges in ~\{p_i\}~.
• ~c(1) = \min(\text{deg}(1)-1, 2) = 1~
• If the current node ~x = s_i~ for some ~i \ge 2~, we know that one of the outgoing edges is ~p_{i-1}~. Set the weight of ~p_{i-1}~ to be ~M-i+1~. If ~c(x) = 2~, set the other edge to be the minimum unused edge. After labelling, the edges ~p_1, p_2, \ldots, p_{i-2}, p_{i-1}, e~ will have weights of ~M, M-1, \ldots, M-k+3, M-k+2, M-k+1~ respectively.

This assignment of edge weights guarantees that Alice must always reach node ~N~, the proof of which is left as an exercise for the reader.

Time Complexity: ~\mathcal{O}(N+M)~