Problem
Graf terarah berwajaran diberikan. Ia diperlukan untuk menentukan sama ada ia mengandungi kitaran berat negatif. Ia dijamin bahawa semua bucu graf boleh dicapai dari yang pertama.
Input:
Baris pertama fail input mengandungi dua nombor asli n dan m — bilangan bucu dan tepi graf masing-masing ( n ≤ 1 111, m ≤ 11 111).
M baris seterusnya mengandungi perihalan tepi, satu setiap baris. Nombor tepi i diterangkan oleh tiga nombor bi, ei dan wi — nombor hujung rusuk dan beratnya, masing-masing (1 ≤ bi, ei ≤ n, &tolak;100 000 ≤ wi ≤ 100 . Ambil perhatian bahawa graf boleh mempunyai berbilang tepi dan gelung.
Output:
Baris pertama fail output harus mengandungi ya jika graf mengandungi kitaran berat negatif dan tidak — sebaliknya.
Contoh
| # |
Input |
Output |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| ya |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| tidak |