Assigning Fares
Contest: Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 3500
Tags: dp, trees

Mayor of city M. decided to launch several new metro lines during 2020. Since the city has a very limited budget, it was decided not to dig new tunnels but to use the existing underground network.

The tunnel system of the city M. consists of $$$n$$$ metro stations. The stations are connected with $$$n - 1$$$ bidirectional tunnels. Between every two stations $$$v$$$ and $$$u$$$ there is exactly one simple path. Each metro line the mayor wants to create is a simple path between stations $$$a_i$$$ and $$$b_i$$$. Metro lines can intersects freely, that is, they can share common stations or even common tunnels. However, it's not yet decided which of two directions each line will go. More precisely, between the stations $$$a_i$$$ and $$$b_i$$$ the trains will go either from $$$a_i$$$ to $$$b_i$$$, or from $$$b_i$$$ to $$$a_i$$$, but not simultaneously.

The city $$$M$$$ uses complicated faring rules. Each station is assigned with a positive integer $$$c_i$$$ — the fare zone of the station. The cost of travel from $$$v$$$ to $$$u$$$ is defined as $$$c_u - c_v$$$ roubles. Of course, such travel only allowed in case there is a metro line, the trains on which go from $$$v$$$ to $$$u$$$. Mayor doesn't want to have any travels with a negative cost, so it was decided to assign directions of metro lines and station fare zones in such a way, that fare zones are strictly increasing during any travel on any metro line.

Mayor wants firstly assign each station a fare zone and then choose a lines direction, such that all fare zones are increasing along any line. In connection with the approaching celebration of the day of the city, the mayor wants to assign fare zones so that the maximum $$$c_i$$$ will be as low as possible. Please help mayor to design a new assignment or determine if it's impossible to do. Please note that you only need to assign the fare zones optimally, you don't need to print lines' directions. This way, you solution will be considered correct if there will be a way to assign directions of every metro line, so that the fare zones will be strictly increasing along any movement of the trains.

Input format:
The first line contains an integers $$$n$$$, $$$m$$$ ($$$2 \le n, \le 500\,000,\ 1 \le m \le 500\,000$$$) — the number of stations in the city and the number of metro lines.

Each of the following $$$n-1$$$ lines describes another metro tunnel. Each tunnel is described with integers $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i,\ u_i \le n$$$, $$$v_i \ne u_i$$$). It's guaranteed, that there is exactly one simple path between any two stations.

Each of the following $$$m$$$ lines describes another metro line. Each line is described with integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i,\ b_i \le n$$$, $$$a_i \neq b_i$$$).

Output format:
In the first line print integer $$$k$$$ — the maximum fare zone used.

In the next line print integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le k$$$)  — stations' fare zones.

In case there are several possible answers, print any of them. In case it's impossible to assign fare zones, print "-1".

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
In the first example, line $$$1 \rightarrow 3$$$ goes through the stations 1, 2, 3 in this order. In this order the fare zones of the stations are increasing. Since this line has 3 stations, at least three fare zones are needed. So the answer 1, 2, 3 is optimal.

In the second example, it's impossible to assign fare zones to be consistent with a metro lines.

Example input:
3 1
1 2
2 3
1 3

Example output:
3
1 2 3

Example input:
4 3
1 2
1 3
1 4
2 3
2 4
3 4

Example output:
-1

Editorial:
Let's assume $$$c_v$$$ is the color of vertex v. So, we need to find a coloring of tree, where $$$c_v$$$ strictly increases along every path.
First of all, if coloring exists, we can renumerate colors so that they will be in range [1, $$$n$$$]. Secondly, we can always revert our coloring, make $$$c_v \rightarrow k + 1 - c_v$$$. Also, let's do binary search to find $$$k$$$. So, now we want to check if it is possible to paint tree using $$$k$$$ colors.
Every path can be on of two directions. If we determine direction for path #0, then we also automatically determine direction for every path which has common edge with path #0. So, we can get a components of paths — if we choose one path direction, we choose every other paths direction. We can notice, that if a single component is not bipartite, answer is -1. So, for every path, we know it's component and it's orientation inside the component. It can be calculated using subtree sum — for vertexes $$$a$$$ and $$$b$$$ we make +1 for $$$a$$$, +1 for $$$b$$$, and -2 for $$$lca(a,\,b)$$$. Let's make our tree rooted and then count dp on subtrees. $$$dp_v$$$ — minimal color of $$$v$$$, if all it's subtree is colored in a correct way and edge $$$v \rightarrow parent_v$$$ goes from lower to higher color. How to calculate dp?
If we fix $$$parent_v \rightarrow v$$$ edge direction, for some edges $$$v \rightarrow to$$$ we know the orientation. It happens when they were in same component as $$$parent_v \rightarrow v$$$. For other components, we can or use $$$dp_{to}$$$ or $$$k + 1 - dp_{to}$$$ — depending on which direction of component we use. If we will try both variants and combine all the constraints, we will get two different segments $$$[l, r]$$$ and $$$[k + 1 - r, k + 1 - l]$$$, and $$$dp_v$$$ must be in one of them. It can be solved with scanline in $$$O(n \log n)$$$ time.
Now we can notice that $$$r = k + 1 - dp_{to}$$$. Let's think of segments as about two left constraints: $$$l_1$$$ and $$$l_2$$$. We have two sets $$$L$$$ and $$$R$$$. We either put $$$l_1 \rightarrow L,\ l_2 \rightarrow R$$$ or $$$l_2 \rightarrow L,\ l_1 \rightarrow R$$$.
So, we want these conditions to be done: $$$$$$\begin{cases} \max(L) \le \min(k - R) \\ \max(L) \rightarrow \min \end{cases} \rightarrow \begin{cases} \max(L) + \max(R) \le k \\ \max(L) \rightarrow \min \end{cases}$$$$$$
If we fix what is more — $$$\max(R)$$$ or $$$\max(L)$$$, we get fixed distribuition between $$$L$$$ and $$$R$$$ — max of $$$l_1$$$ and $$$l_2$$$ goes to max of two sets. Then we just need to check conditions and use best of variants. Solution will have complexity $$$O(n \log n)$$$.