TSM

가중치 있는 그래프가 주어졌을 때, 최소 스패닝 트리(MST)의 비용을 구하는 문제는 잘 알려져 있습니다. 최소 스패닝 트리의 비용이 주어졌을 때, 그래프의 간선에 가중치를 부여하는 문제를 해결하세요.

자세한 설명은 아래와 같습니다.

• 최소 스패닝 트리란, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 비용이 최소인 트리를 뜻합니다. 스패닝 트리의 비용은 트리에 포함된 간선의 가중치 합으로 정의합니다.
• 주어지는 그래프는 $N$개의 정점과 $M$개의 간선을 가진 무방향 연결 그래프입니다. 각 정점과 각 간선에는 $1$번부터 순서대로 번호가 붙어 있습니다. $i$번 간선은 $u_i$번 정점과 $v_i$번 정점을 이으며, $i$번 간선에는 $l_i$ 이상 $r_i$ 이하의 정수 가중치를 부여할 수 있습니다.
• 각 간선에 적절한 가중치를 부여해서 최소 스패닝 트리의 비용이 $K$가 되도록 만드세요.

첫 번째 줄에 그래프의 정점의 수 $N$과 간선의 수 $M$, 최소 스패닝 트리의 비용 $K$가 공백으로 구분되어 주어집니다. $(2 \le N \le 100\, 000;\ N-1 \le M \le 200\, 000;\ 0 \le K \le 10^{10})$

다음 $M$개의 줄의 $i$번째 줄에 정수 $u_i, v_i, l_i, r_i$가 공백으로 구분되어 주어집니다. $i$번 간선이 $u_i$번 정점과 $v_i$번 정점을 이으며, $i$번 간선에 $l_i$ 이상 $r_i$ 이하의 정수 가중치를 부여할 수 있음을 의미합니다. $(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 0 \le l_i \le r_i \le 100\, 000)$

주어지는 그래프는 연결 그래프이며, 서로 다른 간선은 같은 정점 쌍을 잇지 않습니다.

스패닝 트리의 비용이 $K$가 되도록 가중치를 부여할 수 있다면 첫 줄에 YES, 불가능하다면 NO를 출력합니다.YES를 출력한 경우 추가로 $M$개의 줄을 출력합니다. 그중 $i$번째 줄에는 $i$번째 간선에 부여할 가중치를 출력합니다.