#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 500000;
const int MAXBIT = 18;
const int MAXLINE = 500000;
int n, nline;
vector<int> adj[MAXN];
int lineend[MAXLINE][2];
int par[MAXN], dep[MAXN];
int up[MAXN][MAXBIT + 1];
void dfsinit(int at) {
  dep[at] = par[at] == -1 ? 0 : dep[par[at]] + 1;
  up[at][0] = par[at] == -1 ? at : par[at];
  for (int k = (0); k < (MAXBIT); ++k) up[at][k + 1] = up[up[at][k]][k];
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    par[to] = at;
    dfsinit(to);
  }
}
int calcup(int a, int steps) {
  for (int k = MAXBIT; k >= 0; --k)
    if (steps & (1 << k)) a = up[a][k];
  return a;
}
int calclca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  a = calcup(a, dep[a] - dep[b]);
  if (a == b) return a;
  for (int k = MAXBIT; k >= 0; --k)
    if (up[a][k] != up[b][k]) a = up[a][k], b = up[b][k];
  return par[a];
}
int ufpar[MAXN], ufsz[MAXN], ufdiff[MAXN];
int uffind(int a) {
  if (ufpar[a] == a) return a;
  uffind(ufpar[a]);
  ufdiff[a] ^= ufdiff[ufpar[a]];
  return ufpar[a] = ufpar[ufpar[a]];
}
bool ufunite(int a, int b, int diff) {
  uffind(a), uffind(b);
  diff ^= ufdiff[a], a = ufpar[a], diff ^= ufdiff[b], b = ufpar[b];
  if (a == b) return diff == 0;
  if (ufsz[a] < ufsz[b]) swap(a, b);
  ufsz[a] += ufsz[b], ufpar[b] = a, ufdiff[b] ^= diff;
  return true;
}
int unitedep[MAXN];
bool anyedge[MAXN];
void dfsunite(int at) {
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    dfsunite(to);
    unitedep[at] = min(unitedep[at], unitedep[to]);
  }
}
int dp[MAXN];
int seenby[MAXN], mxzero[MAXN], mxone[MAXN];
int seenlst[MAXN], nseenlst;
bool dfscalc(int at, int lim) {
  if (par[at] == -1)
    for (int i = (0); i < (n); ++i) seenby[i] = -1;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    if (!dfscalc(to, lim)) return false;
  }
  nseenlst = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    uffind(to);
    int id = ufpar[to];
    if (seenby[id] != at)
      seenlst[nseenlst++] = id, seenby[id] = at, mxzero[id] = mxone[id] = 0;
    if (ufdiff[to] == 0 && anyedge[to]) mxzero[id] = max(mxzero[id], dp[to]);
    if (ufdiff[to] == 1 && anyedge[to]) mxone[id] = max(mxone[id], dp[to]);
  }
  uffind(at);
  int me = ufpar[at];
  int lo = 1, loupto = lim, hi = lim, hidownto = 1;
  for (int i = (0); i < (nseenlst); ++i) {
    int id = seenlst[i];
    int a = mxzero[id], b = mxone[id];
    if (id == me) {
      if (ufdiff[at] == 1) swap(a, b);
      lo = max(lo, a + 1);
      hi = min(hi, lim - b);
    } else {
      if (a > b) swap(a, b);
      lo = max(lo, a + 1), hi = min(hi, lim - a);
      if (lim - b < b + 1)
        loupto = min(loupto, lim - b), hidownto = max(hidownto, b + 1);
    }
  }
  loupto = min(loupto, hi);
  hidownto = max(hidownto, lo);
  bool ret;
  if (lo <= loupto) {
    dp[at] = lo;
    ret = true;
  } else if (hidownto <= hi) {
    dp[at] = hidownto;
    ret = true;
  } else
    ret = false;
  return ret;
}
int ans;
int cost[MAXN];
bool rev[MAXN];
bool swapped[MAXN];
void reconstruct(int at) {
  if (par[at] == -1)
    for (int i = (0); i < (n); ++i) seenby[i] = -1;
  cost[at] = !rev[at] ? dp[at] : ans - dp[at] + 1;
  nseenlst = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    uffind(to);
    int id = ufpar[to];
    if (seenby[id] != at)
      seenlst[nseenlst++] = id, seenby[id] = at, mxzero[id] = mxone[id] = 0;
    if (ufdiff[to] == 0 && anyedge[to]) mxzero[id] = max(mxzero[id], dp[to]);
    if (ufdiff[to] == 1 && anyedge[to]) mxone[id] = max(mxone[id], dp[to]);
  }
  uffind(at);
  int me = ufpar[at];
  for (int i = (0); i < (nseenlst); ++i) {
    int id = seenlst[i];
    int a = mxzero[id], b = mxone[id];
    swapped[id] = false;
    if (id == me && ufdiff[at] == 1) swap(a, b), swapped[id] = !swapped[id];
    if ((dp[at] <= a || dp[at] > ans - b) && id != me)
      swap(a, b), swapped[id] = !swapped[id];
    assert(dp[at] > a && dp[at] <= ans - b);
  }
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    rev[to] = rev[at] ^ swapped[ufpar[to]] ^ (ufdiff[to] == 1);
  }
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    reconstruct(to);
  }
}
bool solve() {
  par[0] = -1;
  dfsinit(0);
  for (int i = (0); i < (n); ++i)
    ufpar[i] = i, ufsz[i] = 1, ufdiff[i] = 0, unitedep[i] = dep[i],
    anyedge[i] = false;
  for (int i = (0); i < (nline); ++i) {
    int a = lineend[i][0], b = lineend[i][1];
    if (dep[a] > dep[b]) swap(a, b);
    int c = calclca(a, b);
    if (c == a) {
      unitedep[b] = min(unitedep[b], dep[c]);
    } else {
      int aa = calcup(a, dep[a] - dep[c] - 1);
      int bb = calcup(b, dep[b] - dep[c] - 1);
      if (!ufunite(aa, bb, 1)) return false;
      unitedep[a] = min(unitedep[a], dep[c]);
      unitedep[b] = min(unitedep[b], dep[c]);
    }
  }
  dfsunite(0);
  for (int i = (0); i < (n); ++i)
    if (unitedep[i] < dep[i]) anyedge[i] = true;
  for (int i = (0); i < (n); ++i)
    if (unitedep[i] < dep[i] - 1)
      if (!ufunite(i, par[i], 0)) return false;
  int lo = 1, hi = n;
  while (lo + 1 < hi) {
    int mi = lo + (hi - lo) / 2;
    if (!dfscalc(0, mi))
      lo = mi;
    else
      hi = mi;
  }
  ans = hi;
  assert(dfscalc(0, ans));
  rev[0] = false;
  reconstruct(0);
  return true;
}
void run() {
  scanf("%d%d", &n, &nline);
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i = (0); i < (n); ++i) sort(adj[i].begin(), adj[i].end());
  for (int i = (0); i < (nline); ++i)
    for (int j = (0); j < (2); ++j)
      scanf("%d", &lineend[i][j]), --lineend[i][j];
  if (!solve()) {
    printf("-1\n");
    return;
  }
  printf("%d\n", ans);
  for (int i = (0); i < (n); ++i) {
    if (i != 0) printf(" ");
    printf("%d", cost[i]);
  }
  puts("");
}
void stress() {
  for (int rep = (0); rep < (100000); ++rep) {
    n = rand() % 10 + 2;
    for (int i = (0); i < (n); ++i) adj[i].clear();
    vector<int> col(n);
    for (int i = (0); i < (n); ++i) col[i] = i;
    for (int i = (0); i < (n - 1); ++i)
      while (true) {
        int a = rand() % n, b = rand() % n;
        if (col[a] == col[b]) continue;
        int ocol = col[b];
        for (int j = (0); j < (n); ++j)
          if (col[j] == ocol) col[j] = col[a];
        adj[a].push_back(b), adj[b].push_back(a);
        break;
      }
    for (int i = (0); i < (n); ++i) sort(adj[i].begin(), adj[i].end());
    nline = rand() % 10 + 1;
    for (int i = (0); i < (nline); ++i)
      while (true) {
        int a = rand() % n, b = rand() % n;
        if (a == b) continue;
        lineend[i][0] = a, lineend[i][1] = b;
        break;
      }
    solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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

The first line contains an integers n, m (2 ≤ n, ≤ 500 000,\ 1 ≤ m ≤ 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 ≤ v_i,\ u_i ≤ n, v_i ≠ 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 ≤ a_i,\ b_i ≤ n, a_i ≠ b_i).

Output

In the first line print integer k — the maximum fare zone used.

In the next line print integers c_1, c_2, …, c_n (1 ≤ c_i ≤ 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".

Examples

Input


3 1
1 2
2 3
1 3


Output


3
1 2 3


Input


4 3
1 2
1 3
1 4
2 3
2 4
3 4


Output


-1


Input


7 5
3 4
4 2
2 5
5 1
2 6
4 7
1 3
6 7
3 7
2 1
3 6


Output


-1

Note

In the first example, line 1 → 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 500000;
const int MAXBIT = 18;
const int MAXLINE = 500000;
int n, nline;
vector<int> adj[MAXN];
int lineend[MAXLINE][2];
int par[MAXN], dep[MAXN];
int up[MAXN][MAXBIT + 1];
void dfsinit(int at) {
  dep[at] = par[at] == -1 ? 0 : dep[par[at]] + 1;
  up[at][0] = par[at] == -1 ? at : par[at];
  for (int k = (0); k < (MAXBIT); ++k) up[at][k + 1] = up[up[at][k]][k];
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    par[to] = at;
    dfsinit(to);
  }
}
int calcup(int a, int steps) {
  for (int k = MAXBIT; k >= 0; --k)
    if (steps & (1 << k)) a = up[a][k];
  return a;
}
int calclca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  a = calcup(a, dep[a] - dep[b]);
  if (a == b) return a;
  for (int k = MAXBIT; k >= 0; --k)
    if (up[a][k] != up[b][k]) a = up[a][k], b = up[b][k];
  return par[a];
}
int ufpar[MAXN], ufsz[MAXN], ufdiff[MAXN];
int uffind(int a) {
  if (ufpar[a] == a) return a;
  uffind(ufpar[a]);
  ufdiff[a] ^= ufdiff[ufpar[a]];
  return ufpar[a] = ufpar[ufpar[a]];
}
bool ufunite(int a, int b, int diff) {
  uffind(a), uffind(b);
  diff ^= ufdiff[a], a = ufpar[a], diff ^= ufdiff[b], b = ufpar[b];
  if (a == b) return diff == 0;
  if (ufsz[a] < ufsz[b]) swap(a, b);
  ufsz[a] += ufsz[b], ufpar[b] = a, ufdiff[b] ^= diff;
  return true;
}
int unitedep[MAXN];
bool anyedge[MAXN];
void dfsunite(int at) {
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    dfsunite(to);
    unitedep[at] = min(unitedep[at], unitedep[to]);
  }
}
int dp[MAXN];
int seenby[MAXN], mxzero[MAXN], mxone[MAXN];
int seenlst[MAXN], nseenlst;
bool dfscalc(int at, int lim) {
  if (par[at] == -1)
    for (int i = (0); i < (n); ++i) seenby[i] = -1;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    if (!dfscalc(to, lim)) return false;
  }
  nseenlst = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    uffind(to);
    int id = ufpar[to];
    if (seenby[id] != at)
      seenlst[nseenlst++] = id, seenby[id] = at, mxzero[id] = mxone[id] = 0;
    if (ufdiff[to] == 0 && anyedge[to]) mxzero[id] = max(mxzero[id], dp[to]);
    if (ufdiff[to] == 1 && anyedge[to]) mxone[id] = max(mxone[id], dp[to]);
  }
  uffind(at);
  int me = ufpar[at];
  int lo = 1, loupto = lim, hi = lim, hidownto = 1;
  for (int i = (0); i < (nseenlst); ++i) {
    int id = seenlst[i];
    int a = mxzero[id], b = mxone[id];
    if (id == me) {
      if (ufdiff[at] == 1) swap(a, b);
      lo = max(lo, a + 1);
      hi = min(hi, lim - b);
    } else {
      if (a > b) swap(a, b);
      lo = max(lo, a + 1), hi = min(hi, lim - a);
      if (lim - b < b + 1)
        loupto = min(loupto, lim - b), hidownto = max(hidownto, b + 1);
    }
  }
  loupto = min(loupto, hi);
  hidownto = max(hidownto, lo);
  bool ret;
  if (lo <= loupto) {
    dp[at] = lo;
    ret = true;
  } else if (hidownto <= hi) {
    dp[at] = hidownto;
    ret = true;
  } else
    ret = false;
  return ret;
}
int ans;
int cost[MAXN];
bool rev[MAXN];
bool swapped[MAXN];
void reconstruct(int at) {
  if (par[at] == -1)
    for (int i = (0); i < (n); ++i) seenby[i] = -1;
  cost[at] = !rev[at] ? dp[at] : ans - dp[at] + 1;
  nseenlst = 0;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    uffind(to);
    int id = ufpar[to];
    if (seenby[id] != at)
      seenlst[nseenlst++] = id, seenby[id] = at, mxzero[id] = mxone[id] = 0;
    if (ufdiff[to] == 0 && anyedge[to]) mxzero[id] = max(mxzero[id], dp[to]);
    if (ufdiff[to] == 1 && anyedge[to]) mxone[id] = max(mxone[id], dp[to]);
  }
  uffind(at);
  int me = ufpar[at];
  for (int i = (0); i < (nseenlst); ++i) {
    int id = seenlst[i];
    int a = mxzero[id], b = mxone[id];
    swapped[id] = false;
    if (id == me && ufdiff[at] == 1) swap(a, b), swapped[id] = !swapped[id];
    if ((dp[at] <= a || dp[at] > ans - b) && id != me)
      swap(a, b), swapped[id] = !swapped[id];
    assert(dp[at] > a && dp[at] <= ans - b);
  }
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    rev[to] = rev[at] ^ swapped[ufpar[to]] ^ (ufdiff[to] == 1);
  }
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    reconstruct(to);
  }
}
bool solve() {
  par[0] = -1;
  dfsinit(0);
  for (int i = (0); i < (n); ++i)
    ufpar[i] = i, ufsz[i] = 1, ufdiff[i] = 0, unitedep[i] = dep[i],
    anyedge[i] = false;
  for (int i = (0); i < (nline); ++i) {
    int a = lineend[i][0], b = lineend[i][1];
    if (dep[a] > dep[b]) swap(a, b);
    int c = calclca(a, b);
    if (c == a) {
      unitedep[b] = min(unitedep[b], dep[c]);
    } else {
      int aa = calcup(a, dep[a] - dep[c] - 1);
      int bb = calcup(b, dep[b] - dep[c] - 1);
      if (!ufunite(aa, bb, 1)) return false;
      unitedep[a] = min(unitedep[a], dep[c]);
      unitedep[b] = min(unitedep[b], dep[c]);
    }
  }
  dfsunite(0);
  for (int i = (0); i < (n); ++i)
    if (unitedep[i] < dep[i]) anyedge[i] = true;
  for (int i = (0); i < (n); ++i)
    if (unitedep[i] < dep[i] - 1)
      if (!ufunite(i, par[i], 0)) return false;
  int lo = 1, hi = n;
  while (lo + 1 < hi) {
    int mi = lo + (hi - lo) / 2;
    if (!dfscalc(0, mi))
      lo = mi;
    else
      hi = mi;
  }
  ans = hi;
  assert(dfscalc(0, ans));
  rev[0] = false;
  reconstruct(0);
  return true;
}
void run() {
  scanf("%d%d", &n, &nline);
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i = (0); i < (n); ++i) sort(adj[i].begin(), adj[i].end());
  for (int i = (0); i < (nline); ++i)
    for (int j = (0); j < (2); ++j)
      scanf("%d", &lineend[i][j]), --lineend[i][j];
  if (!solve()) {
    printf("-1\n");
    return;
  }
  printf("%d\n", ans);
  for (int i = (0); i < (n); ++i) {
    if (i != 0) printf(" ");
    printf("%d", cost[i]);
  }
  puts("");
}
void stress() {
  for (int rep = (0); rep < (100000); ++rep) {
    n = rand() % 10 + 2;
    for (int i = (0); i < (n); ++i) adj[i].clear();
    vector<int> col(n);
    for (int i = (0); i < (n); ++i) col[i] = i;
    for (int i = (0); i < (n - 1); ++i)
      while (true) {
        int a = rand() % n, b = rand() % n;
        if (col[a] == col[b]) continue;
        int ocol = col[b];
        for (int j = (0); j < (n); ++j)
          if (col[j] == ocol) col[j] = col[a];
        adj[a].push_back(b), adj[b].push_back(a);
        break;
      }
    for (int i = (0); i < (n); ++i) sort(adj[i].begin(), adj[i].end());
    nline = rand() % 10 + 1;
    for (int i = (0); i < (nline); ++i)
      while (true) {
        int a = rand() % n, b = rand() % n;
        if (a == b) continue;
        lineend[i][0] = a, lineend[i][1] = b;
        break;
      }
    solve();
    printf(".");
  }
}
int main() {
  run();
  return 0;
}

```