Đất nước ZZZ có ~N~ thành phố và ~M~ con đường nối chúng. Mỗi con đường là đường thường hoặc đường cao tốc. Hệ thống đường sá bảo đảm luôn có đường đi giữa hai thành phố bất kỳ.

Có ~K~ công ty, được đánh số từ ~1~ đến ~K~, nhận nhiệm vụ bảo trì các đường cao tốc. Mỗi đường cao tốc phải được giao cho đúng một công ty.

Yêu cầu

Hãy tìm một phương án phân công các đường cao tốc cho các công ty sao cho trên mọi đường đi từ thành phố ~1~ đến thành phố ~N~, phải đi qua ít nhất một đường cao tốc của mỗi công ty.

Dữ liệu

Dòng đầu chứa ba số nguyên ~N, M, K~.

~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~:

• ~u, v~ là hai đầu của một con đường.
• ~w=1~ nếu đó là đường cao tốc.
• ~w=0~ nếu đó là đường thường.

Các đường cao tốc được đánh số ~1 \dots T~ theo thứ tự xuất hiện trong dữ liệu vào, với ~T~ là số đường có ~w=1~.

Kết quả

Nếu không tồn tại phương án, in ra một dòng chứa No.

Ngược lại:

• Dòng ~1~ in Yes.
• Các dòng ~2 \dots T+1~, dòng thứ ~i+1~ in chỉ số công ty được giao cho đường cao tốc thứ ~i~.

Nếu có nhiều phương án, in ra một phương án bất kỳ.

Ví dụ

Ví dụ 1

Input

6 6 3
1 4 1
1 5 1
2 4 1
3 6 1
2 3 0
4 5 0

Output

Yes
1
1
2
3

Giải thích

Ví dụ 1

Hai đường thường nối ~2~ với ~3~, và ~4~ với ~5~.

Vì vậy, mọi đường đi từ ~1~ đến ~6~ đều phải:

• đi từ ~1~ sang thành phần ~{4,5}~ qua một trong hai đường cao tốc đầu tiên,
• đi sang thành phần ~{2,3}~ qua đường cao tốc thứ ~3~,
• đi sang ~6~ qua đường cao tốc thứ ~4~.

Do đó cách gán ~[1,1,2,3]~ là hợp lệ.

Ràng buộc và chấm điểm

Ràng buộc

~2 \le N \le 10^5~.

~1 \le M \le 2 \cdot 10^5~.

~1 \le K \le M~.

~1 \le u,v \le N~, ~u \ne v~.

Chấm điểm

• Subtask ~1~: ~6%~, ~K=1~.
• Subtask ~2~: ~12%~, ~N \le 1000~, ~M \le 3000~, số đường cao tốc không quá ~8~.
• Subtask ~3~: ~15%~, ~K=2~.
• Subtask ~4~: ~30%~, mọi cạnh đều là đường cao tốc.
• Subtask ~5~: ~37%~, không có ràng buộc bổ sung.