Naməlum Məkan
Siz agent B100-siniz. Gözə çarpan geyimli bir cüt sirk artisti şəhərin yolları boyunca səyahət edir və sizin missiyanız onların hara getdiyini öyrənməkdir. Bildiyimiz tək şey onların s nöqtəsindən başladığı və bir neçə mümkün təyinatdan birinə doğru getdikləridir. Onlar tələsikdirlər, buna görə də təyinatlarına gedərkən yolundan çıxmayacaqlarına əminik.
Təəssüf ki, nə qədər gözə çarpan geyinsələr də, cütlük heç yerdə görünmür. Xoşbəxtlikdən, sizin müstəsna qoxu hissiniz var. Daha dəqiq desək: burnunuz sizi heç vaxt yanıltmaz. Əslində, onların g və h kəsişmələri arasındakı yolda getdiklərini qoxuya bilirsiniz.
Əlçatmaz cütlük hara gedir? Yoxsa hələ də əmin deyilik?
İkinci nümunənin vizual təsviri. Cütlük boz dairədən iki qara dairədən birinə doğru gedir və siz onları kəsik xətt üzərində qoxuladınız, buna görə də onlar 6-ya gedə bilərlər.
Giriş verilənləri
Birinci sətirdə bir müsbət ədəd: test halların sayı, ən çox 100. Bundan sonra hər test halı üçün:
Bir sətirdə üç boşluqla ayrılmış tam ədəd n, m və t (2 ≤ n ≤ 2000, 1 ≤ m ≤ 50000 və 1 ≤ t ≤ 100): şəhərdəki kəsişmələrin sayı, bu kəsişmələr arasında olan fərdi yolların sayı və mümkün təyinatların sayı müvafiq olaraq.
Bir sətirdə üç boşluqla ayrılmış tam ədəd s, g və h (1 ≤ s, g, h ≤ n): cütlüyün başladığı kəsişmə və cütlüyün getdiyi iki kəsişmə, g ≠ h.
m sətirdə üç boşluqla ayrılmış tam ədəd a, b və d (1 ≤ a < b ≤ n və 1 ≤ d ≤ 1000), a və b kəsişmələri arasında uzunluğu d olan ikitərəfli yol olduğunu göstərir.
t sətirdə bir tam ədəd x (1 ≤ x ≤ n): mümkün təyinatlar. Bütün mümkün təyinatlar fərqlidir və onların hamısı s-dən fərqlidir.
Kəsişmələr cütü arasında ən çox bir yol var. m sətirlərdən biri g və h arasındakı yolu təsvir edir. Bu yol ən azı bir mümkün təyinat üçün ən qısa yolda olmağa zəmanətlidir.
Çıxış verilənləri
Hər test halı üçün:
Bir sətirdə bir və ya daha çox boşluqla ayrılmış tam ədəd, cütlüyün hələ də gedə biləcəyi təyinatları artan sırada göstərir.