요금 구역 배정

2020년에 M시의 시장은 새 지하철 노선 몇 개를 개통하기로 했다. 시 예산이 매우 적어서 새 터널을 파지 않고 기존 지하철망을 쓰기로 했다.

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$가 가능한 한 작아지도록 하려 한다. 최적의 배정을 찾거나, 배정이 불가능하면 그 사실을 판정하라. 노선 방향은 출력할 필요가 없다. 어떤 방향 배정을 택해도 열차가 움직일 때마다 요금 구역이 엄격히 증가하면 그 배정은 정답이다.

일부 테스트 그룹에서는 답을 최소화할 필요가 없다. 그런 그룹에서는 유효한 배정이 존재하는지만 판정하면 된다.

첫 줄에는 정수 $n$, $m$, $t$($2 \le n \le 500000$, $1 \le m \le 500000$, $0 \le t \le 1$)가 주어진다. 각각 역의 수, 노선의 수, 매개변수 $t$다. $t = 0$이면 답을 최소화할 필요가 없다. $t = 1$이면 가장 큰 요금 구역이 가능한 한 작아야 한다.

다음 $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 \ne b_i$)가 주어진다.

첫 줄에 사용된 가장 큰 요금 구역 $k$를 출력한다. $t = 0$이면 $k$는 최소일 필요가 없다. $t = 1$이면 $k$는 가능한 가장 작은 값이어야 한다.

다음 줄에는 요금 구역 $c_1, c_2, \dots, c_n$($1 \le c_i \le k$)을 출력한다. 답이 여러 개이면 아무거나 출력해도 된다. 유효한 배정이 없으면 "-1"을 출력한다.

첫 번째 예에서 노선 $1 \rightarrow 3$은 역 1, 2, 3을 이 순서대로 지난다. 이 순서대로 요금 구역이 증가한다. 이 노선은 3개의 역을 지나므로 요금 구역이 최소 3개 필요하고, 1, 2, 3이 최적이다.

두 번째 예에서는 어떤 요금 구역 배정도 이 노선들과 맞지 않는다.