Trong một mạng lưới cổng dịch chuyển không gian gồm \(N\) tọa độ và \(M\) liên kết một chiều, có một số cổng dịch chuyển thời gian mang trọng số âm (cho phép quay ngược thời gian).

Hãy tìm một chu trình âm bất kỳ (chu trình quay ngược thời gian vô hạn) có thể đi tới được từ tọa độ xuất phát \(S\). Nếu có, in ra YES kèm theo danh sách các cổng theo thứ tự di chuyển tạo nên chu trình đó. Nếu không có, in ra NO.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N, M\) và \(S\) (\(1 \le N \le 1000\), \(1 \le M \le 5000\), \(1 \le S \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(-1000 \le w \le 1000\)) mô tả cổng dịch chuyển một chiều từ \(u\) đến \(v\) làm thay đổi thời gian đi \(w\) đơn vị.

Kết quả ra

• Dòng đầu tiên in ra YES nếu tồn tại chu trình âm hoặc NO nếu không tồn tại.
• Nếu in ra YES, dòng thứ hai chứa danh sách các đỉnh thuộc chu trình âm theo đúng thứ tự đi qua (đỉnh đầu và đỉnh cuối của chu trình phải trùng nhau). Nếu có nhiều chu trình âm, bạn có thể in ra bất kỳ chu trình nào hợp lệ.

Ví dụ

Input

4 4 1
1 2 2
2 3 -5
3 2 1
3 4 3

Output

YES
2 3 2