Marşrutun Təkrarlanması#3555
Bir şəhər yalnız bir istiqamətli küçələrdən ibarətdir, hər bir küçənin müəyyən tutumu var. Marşrutun tutumu, bu marşrut boyunca küçələrin tutumlarının minimumu kimi təyin edilir.
Nöqtə A-dan nöqtə B-yə artıqlıq nisbəti — bütün mümkün marşrutlardan eyni anda istifadə edərək bir saat ərzində nöqtə A-dan nöqtə B-yə çata bilən maksimum avtomobil sayının, bir marşrutdan istifadə edərək bir saat ərzində çata bilən maksimum avtomobil sayına nisbətidir. Minimum artıqlıq nisbəti ən böyük tutuma malik bir marşrutun tutumu ilə bərabərdir.
Girişin ilk sətri məlumat dəstlərinin sayını göstərən bir tam ədəd P (1 \le P \le 1000) ehtiva edir.
Hər bir məlumat dəsti bir neçə sətrdən ibarətdir və müsbət tam ədəd çəkilərdən ibarət istiqamətli qrafı təsvir edir.
Hər məlumat dəstinin ilk sətri ardıcıl olaraq beş boşluqla ayrılmış tam ədəd ehtiva edir: D, N, E, A və B. Burada D məlumat dəsti nömrəsidir; N (2 \le N \le 1000) qrafdakı düyünlərin sayıdır; E (E \ge 1) kənarların sayıdır; A (0 \le A < N) nöqtə A-nın indeksidir; B (0 \le B < N,\, A \ne B) nöqtə B-nin indeksidir.
Davam edən E sətrin hər biri bir kənarı təsvir edir və üç tam ədəd ilə ayrılır: U, V, W. Burada U (0 \le U < N) başlanğıc düyünü, V (0 \le V < N,\, V \ne U) son düyün, W (1 \le W \le 1000) U-dan V-yə olan yolun tutumudur (çəki).
Hər bir məlumat dəsti üçün bir sətr çıxış verilməlidir. O, məlumat dəsti nömrəsini (D), ardınca bir boşluq və sonra minimum artıqlıq nisbətini 3 onluq rəqəmdən sonra yuvarlaqlaşdırılmış şəkildə göstərməlidir.
Nümunə 1