탐사 기록

$N$개의 정점으로 이루어진 트리가 있다. 정점에는 $1,2,\cdots,N$의 번호가 붙어 있고, 루트는 $1$번 정점이다.

$i$번 정점에는 높이 $H_i$인 빌딩이 있다. 모든 높이는 음이 아닌 정수이며, 다음 조건을 만족한다.

• $H_1=0$이다.
• 간선으로 직접 연결된 두 정점의 빌딩 높이 차는 정확히 $1$이다.

탐사 로봇이 정점 $u$에서 정점 $v$까지 두 정점을 잇는 단순 경로를 따라 이동한다고 하자. 로봇이 높이가 $1$ 증가하는 방향으로 간선 하나를 이동하면 배터리를 $1$만큼 사용한다. 높이가 $1$ 감소하는 방향으로 이동하면 배터리가 $1$만큼 충전된다. 이동 중 배터리의 양은 항상 $0$ 이상이어야 한다.

$A(u,v)$를 $u$에서 $v$까지 이동할 수 있게 하는 초기 배터리 양의 최솟값으로 정의한다. 초기 배터리를 정확히 $A(u,v)$로 두었을 때, 배터리가 처음으로 $0$이 되는 정점을 라 한다. 출발 정점 에서의 배터리도 이 정의에 포함된다. 같은 이동에서 에 도착했을 때 남아 있는 배터리의 양을 라 한다.

과거에 수행한 $M$개의 탐사 기록이 남아 있다. 각 기록은 어떤 두 정점 $u,v$에 대한 $A(u,v)$, $B(u,v)$, $$의 값을 나타낸다.

주어진 모든 기록과 모순되지 않는 빌딩 높이 $H_1,H_2,\cdots,H_N$을 하나 구하여라. 그런 높이 배정이 존재하지 않으면 이를 판별하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 한 줄을 출력한다.

조건을 만족하는 높이 배정이 존재하면 다음 형식으로 $N$개의 정수를 출력한다.

$H_1\ H_2\ \cdots\ H_N$

• $1 \le T \le 500$.
• $1 \le N \le 8\,000$.
• $0 \le M \le 8\,000$.