Qarışdırılmış ağaclar#11329
Qeyri-yönlü, əlaqəli bir qraf verilmişdir, burada təpə və kənar var. Hər kənarın başlanğıc dəyəri olan bir sayğacı var. Bir əməliyyatda istənilən təsadüfi ostov ağacı seçərək bu ağacın bütün kənarlarına eyni dəyərini əlavə edə bilərsiniz.
Məqsəd, hər kənarın sayğacının, sadə ədəd modulu üzrə onun hədəf dəyəri x_i olmasıdır. Əgər bu mümkündürsə, məqsədli konfiqurasiyaya gətirən əməliyyatlar ardıcıllığını göstərin.
Birinci sətir üç tam ədəd və p~(1 \le n \le 500, 1 \le m \le 1000, 2 \le p \le 10^9) — təpələrin sayı, kənarların sayı və modul. Məlumdur ki, sadə ədəddir.
Növbəti sətir hər biri üç tam sayı u_i, v_i, x_i~(1 \le u_i, v_i \le n, 0 \le x_i < p, u_i \ne v_i) — -ci kənarın ucları və onun hədəf dəyəri.
Qraf əlaqəlidir. Qrafda çevrimlər yoxdur, amma eyni təpələr arasında bir neçə kənar ola bilər.
Əgər hədəf dəyərlərinə çatmaq mümkün deyilsə, çıxış edin.
Əks halda, əməliyyatların sayı , və sonra onları təsvir edən sətir verin. Hər sətir müvafiq əməliyyat üçün əvvəl v~(0 \le v < p) artırmanı əks etdirən tam ədəd və onun ardınca seçilmiş ostov ağacını təşkil edən n-1 tam ədədləri e_1, e_2, \dots, e_{n-1}~(1 \le e_i \le m) göstərir.
Əməliyyatların sayı -dən çox olmamalıdır. -ni minimizasiya etmək tələb olunmur: bu məhdudiyyətlər daxilində hər hansı düzgün cavab qəbul edilir. Eyni ostov ağacını bir neçə dəfə istifadə etmək icazəlidir.
Nümunə 1
Nümunə 2
Nümunə 3