CF1322F.Assigning Fares

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.

城市 M 的市长决定在 2020 年开通若干条新的地铁线路。由于该市预算十分有限，因此决定不挖掘新的隧道，而是利用现有的地下网络。

城市 M 的隧道系统包含 $n$ 个地铁站，这些车站由 $n - 1$ 条双向隧道连接。任意两个车站 $v$ 和 $u$ 之间恰好存在唯一一条简单路径。市长希望开通的每条地铁线路均为连接车站 $a_i$ 与 $b_i$ 的一条简单路径。地铁线路可自由相交，即它们可以共享公共车站，甚至共享整段隧道。然而，目前尚未确定每条线路的运行方向：更准确地说，在车站 $a_i$ 与 $b_i$ 之间，列车将仅沿一个方向运行——要么从 $a_i$ 到 $b_i$，要么从 $b_i$ 到 $a_i$，但不会双向同时运行。

城市 M 采用一套复杂的票价规则。每个车站被赋予一个正整数 $c_i$，表示该车站所属的票价区。从车站 $v$ 到车站 $u$ 的旅行费用定义为 $c_u - c_v$ 卢布。当然，此类旅行仅在存在一条地铁线路、且该线路上的列车恰好从 $v$ 运行至 $u$ 时才被允许。市长不希望出现负费用的行程，因此决定以如下方式为地铁线路指定方向、并为各车站分配票价区：使得在任意一条地铁线路上，列车运行方向上的所有车站票价区严格递增。

市长希望首先为每个车站分配票价区，然后再为各条线路选定运行方向，从而确保所有线路均满足票价区严格递增的要求。值此城市庆典即将来临之际，市长希望在满足上述条件的前提下，使最大的 $c_i$ 尽可能小。请协助市长设计这一票价区分配方案，或判断该任务是否不可行。请注意：您只需最优地分配票价区，无需输出各条线路的方向。换言之，只要存在一种为所有地铁线路指定方向的方式，使得每条线路上的票价区严格递增，则您的解法即视为正确。

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$).

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500\,000$，$1 \le m \le 500\,000$）—— 分别表示城市中地铁站的数量和地铁线路的数量。

接下来的 $n-1$ 行，每行描述一条地铁隧道。每条隧道由两个整数 $v_i$、$u_i$（$1 \le v_i,\ u_i \le n$，且 $v_i \ne u_i$）描述。保证任意两个地铁站之间恰好存在一条简单路径。

接下来的 $m$ 行，每行描述一条地铁线路。每条线路由两个整数 $a_i$、$b_i$（$1 \le a_i,\ b_i \le n$，且 $a_i \neq b_i$）描述。

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".

第一行输出整数 $k$ —— 所使用的最高票价区编号。

接下来一行输出整数 $c_1, c_2, \ldots, c_n$（其中 $1 \le c_i \le k$）—— 各车站所属的票价区编号。

若存在多种可行解，输出任意一种即可。若无法分配票价区，则输出 "-1"。

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.

在第一个例子中，线路 $1 \rightarrow 3$ 按顺序经过车站 1、2、3。按此顺序，各车站的票价区号严格递增。由于该线路包含 3 个车站，因此至少需要 3 个票价区号。故答案 1, 2, 3 是最优的。

在第二个例子中，无法为车站分配票价区号，使其与地铁线路保持一致。