선인장 접기 Plus

이 문제는 "선인장 접기"의 어려운 버전입니다. 두 버전 간에 $l$에 대한 제약의 차이가 존재하며, 어려운 버전에서는 대응되는 $x\_i$의 값을 직접 출력해야 합니다.

선인장 그래프란 모든 간선이 최대 하나의 단순 사이클에만 포함된 무향 그래프를 의미합니다. 흐즈로는 선인장 그래프를 하나 가지고 있으며, 각 간선에는 길이가 있습니다. 두 정점 $u$, $v$를 연결하며 길이가 $l$인 간선을 순서쌍 $(u,v,l)$로 표기합니다. 문득 흐즈로는 자신의 그래프를 보다가 이러한 생각을 하게 되었습니다.

• 어떤 선인장 그래프는 적당히 접어서 1차원으로 만들 수도 있지 않을까?

이 의문을 해결하기 전, 다음의 성질을 만족하는 그래프를 접어서 1차원으로 만들 수 있다고 정의합시다.

• 각 정점 $i$에 1차원 좌표 $x\_i$를 배정하여, 각 간선 $(u,v,l)$에 대해 $|x\_u-x\_v|=l$이 성립하도록 할 수 있습니다.

이제 여러분이 해결해야 하는 문제는 다음과 같습니다. 입력으로 흐즈로가 가진 선인장 그래프가 주어집니다. 이 그래프를 접어서 1차원으로 만들 수 있는지 판단해 주세요.

첫 번째 줄에 그래프의 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 분리되어 주어집니다. ($1 \le n \le 10^5, 0 \le m \le \min(\lfloor 1.5(n-1) \rfloor,10^5)$)

두 번째 줄부터 총 $m$개의 줄에 간선의 정보가 한 줄에 하나씩 주어집니다. 그 중 $i$번째 줄에는 $i$번째 간선이 연결하는 두 정점 $u\_i$와 $v\_i$, 그리고 간선의 길이 $l\_i$이 공백으로 분리되어 주어집니다. ($1 \le u\_i,v\_i \le n$, $u \neq v$, $0 \le l\_i \le \color{red}{500}$)

주어진 그래프는 중복 간선이나 자기 자신을 향하는 간선을 포함하지 않으며, 선인장 그래프임이 보장됩니다.

그래프를 접어서 1차원으로 만들 수 있다면, 첫 번째 줄에 YES를 출력하세요.

또한, 그다음 줄에 $n$개의 정수 $x\_1,x\_2,x\_3,\cdots,x\_n$을 공백으로 분리하여 출력하세요. 그 중 $i$번째 정수는 $i$번째 정점의 좌표에 대응되며, $\[-10^9,10^9]$ 구간 내에 존재해야 합니다. 모든 간선 $(u,v,l)$에 대해 $|x\_u-x\_v|=l$이 성립하는 경우 출력을 정답으로 인정합니다. 본 문제의 제약 하에, 그래프를 접어서 1차원으로 만들 수 있다면, 각 정점에 $\[-10^9,10^9]$ 구간 내의 정수만을 대응시켜 조건을 만족시키는 방법이 존재함을 증명 가능합니다.

그래프를 접어서 1차원으로 만들 수 있지 않다면 한 줄에 NO를 출력하세요.

본 문제에서 정의하는 선인장 그래프는 연결 그래프가 아닐 수 있음에 주의하세요.