Yollarda tıxaclar
N şəhərində bütün yollar ikitərəflidir. N şəhərinin yollar sistemi şəhərin hər bir nöqtəsindən ixtiyari başqasına maşınla keçməyə imkan verir, lakin avtomobillərin sayının sürətlə artması həmişə tıxac problemi yaradır, bəzi yolları ağlabatan vaxtda keçmək praktiki olaraq mümkün deyil. Avtomobil sahiblərinin israrlı xahişlərindən sonra şəhər meriyası şəhərin bir nöqtəsindən digərinə ən qısa yolla, başqa sözlə, yaranan tıxaclardan yan keçərək mümkün ən az sayda kəsişmələr keçməklə necə çatmaq haqqında sürücüləri məlumatlandıran informasiya xidməti yaratdı.
Avtomobil sürücülərinin, eləcə də, xidmət əməkdaşlarının həyatını yüngülləşdirməyə imkan verən bu qısa yolun avtomatik çəkilməsinə imkan verən proqramı yazın.
Giriş verilənləri
Birinci sətirdə aralarında boşluq işarəsi olmaqla üç tam ədəd: n, m, k (3 <= n, m <= 1000, 1 <= k <= 50); n –kəsişmələrin sayı, m –yolların sayı, k –optimal marşrut üzrə sorğunun sayı verilir. Kəsişmələrin, yolların və avtomobillərin nömrələnməsi 1-dən başlayır. Sonrakı m sayda sətirdə şəhərdəki yolların siyahısı hər bir sətirdə aralarında boşluq işarəsi olmaqla 1-dən n-dək ədədlər cütü ilə - birləşən yolların kəsişmələrinin nömrələri ilə verilir.
Daha sonra hər biri bir sorğunu təsvir edən k sayda blok gəlir. Blok aralarında boşluq işarəsi olmaqla aşağıdakı üç s, f, p (1 <= s, f, p <= m) tam ədədləri yerləşən sətirlə başlayır. s, f – uyğun olaraq avtomobilin başlanğıc məntəqənin yolu və son məqsəd olan hərəkət məntəqələrinə gedən yolun nömrələri, p –tıxacların sayıdır.
Sonrakı p sayda sətirdə tıxac problemli yolun nömrəsi olan 1-dən n-dək aralıqdan ola bilən ədəd verilir.
Çıxış verilənləri
Çıxış faylında avtomobilin ən az sayda getdiyi kəsişmələrin marşrutunu təsvir edən k sayda blok yerləşir. Blokun birinci sətrində marşrutun keçdiyi kəsişmələrin sayı olan tam ədəd verilir. İkinci sətrində aralarında boşluq işarəsi olmaqla kəsişmələrin nömrələri ardıcıllıqla(1-dən n-dək tam ədəd) verilir. Başlanğıc məntəqədən son məntəqəyə marşrutun olmasına təminat verilir.