Mavi Meşə#3602
John məşhur 'Tales of Algorithmers' adlı konsol oyununu oynayır. O, hazırda 'Blue Forest' adlı son zindanda qarşılaşır. Bu mürəkkəb zindanda ən sürətli yolu tapmaq üçün zindanın xəritəsini çəkməyə çalışır.
Zindan bir neçə mərtəbədən ibarətdir. Hər mərtəbə bağlı sadə müstəvi qraf kimi təsvir edilir. Qrafın zirvələri X-Y koordinatları ilə müəyyən olunur və kənarların uzunluğu Evklid məsafəsi ilə hesablanır. Bir zirvə tək istiqamətli keçid qapısı ilə təchiz oluna bilər. Əgər John qapıdan istifadə etməyi seçərsə, bu, onu başqa bir zirvəyə, bəlkə də fərqli bir mərtəbəyə aparır. Keçid qapısı ilə təyinat nöqtəsi arasındakı məsafə 0 olaraq qəbul edilir.
Bir zirvədə ən çox bir keçid qapısı ola bilər, lakin bəzi zirvələr bir neçə keçid qapısının təyinat nöqtəsi ola bilər.
John hər mərtəbə üçün bir xəritə hazırladığını düşünürdü, lakin bütün mərtəbələrin xəritələrini çəkdikdən sonra bir neçə səhv edə biləcəyini gördü. Ola bilsin ki, eyni mərtəbəni bir neçə dəfə çəkib və xəritələrdə bəzi keçid qapılarını qeyd etməyi unudub. Lakin o, bütün keçid qapılarını ən azı bir dəfə qeyd etdiyinə əmin idi. Beləliklə, eyni mərtəbənin xəritələri birləşdirilərsə, bütün keçid qapıları orada təsvir edilməlidir. Xoşbəxtlikdən, heç bir mərtəbə digər mərtəbələrlə eyni formaya malik deyil, buna görə də iki (və ya daha çox) xəritə birləşdirilə bilərsə, onlar eyni mərtəbənin xəritələri olmalıdır. Həmçinin, dairəvi simmetrik mərtəbə yoxdur (məsələn, müntəzəm üçbucaq və kvadrat).
Xəritə A və xəritə B yalnız döndürmə və paralel tərcümə istifadə edərək xəritə A-ya çevrilə bilirsə, birləşdirilə bilər. Xəritələrdə bəzi keçid qapıları itkin ola biləcəyi üçün birləşdirmə zamanı keçid qapılarının mövcudluğunu nəzərə almamalısınız. Əgər xəritə A və xəritə B birləşdirilə bilirsə, xəritə A-dakı bir zirvə və xəritə B-dəki müvafiq zirvə 'eyni' zirvələr hesab olunur. Başqa sözlə, xəritə B-dəki keçid qapılarını xəritə A-dakı müvafiq zirvələrdə yerləşən keçid qapıları kimi qəbul etməlisiniz. Keçid qapılarının təyinat nöqtələri də oxşar şəkildə qəbul edilməlidir. Bundan sonra xəritə B-ni unuda bilərsiniz. Zəmanət verilir ki, əgər həm xəritə A, həm də xəritə B eyni zirvələrdə olan keçid qapılarına malikdirsə, onların təyinat nöqtələri də eynidir.
Unutmayın, sizin vəzifəniz birləşdirilmiş xəritələrdən istifadə edərək zindanın girişindən çıxışına qədər ən qısa yolu tapmaqdır.
Giriş bir neçə datasetdən ibarətdir. Hər dataset aşağıdakı formatdadır.
n component_1 component_2 ... component_n sl sn dl dn
n xəritələrin sayını göstərən müsbət tam ədəddir. componenti i-ci xəritəni aşağıdakı formatda təsvir edir.
A x_1 y_1 x_2 y_2 ... x_A y_A B s_1 d_1 s_2 d_2 ... s_B d_B C sn_1 dl_1 dn_1 sn_2 dl_2 dn_2 ... sn_C dl_C dn_C
A xəritədəki zirvələrin sayını göstərir. Növbəti A sətir hər biri 2 ölçülü müstəvidə i-ci zirvənin koordinatlarını təmsil edən iki tam ədəd x_i və y_i ehtiva edir. B xəritədəki zirvələri birləşdirən kənarların sayını göstərir. Növbəti B sətir hər bir kənarın başlanğıc və son zirvəsini təmsil edən iki tam ədəd ehtiva edir. Eyni xəritədəki zirvələr 1-dən başlayaraq nömrələnir.
C keçid qapılarının sayını göstərir. Növbəti C sətir hər biri bir keçid qapısını təsvir edən üç tam ədəd ehtiva edir. Birinci ədəd keçid qapısının yerləşdiyi zirvədir. İkinci və üçüncü ədədlər keçid qapısının təyinat nöqtəsini təmsil edən xəritə və zirvənin indeksləridir. Zirvələr kimi, xəritələr də 1-dən başlayaraq nömrələnir.
Bütün xəritələrin təsvirindən sonra iki sətir gəlir. Birinci sətir sl və dl olmaqla iki tam ədəd ehtiva edir, bu da zindanın girişinin sl-ci xəritədə, dl-ci zirvədə yerləşdiyini bildirir. Sonuncu sətir iki tam ədəd sn və dn ehtiva edir, bu da çıxışın yerini oxşar şəkildə təsvir edir.
Hər datasetdəki dəyərlər aşağıdakı şərtlərə cavab verir:
1 ≤ n ≤ 50,
3 ≤ A ≤ 20,
A-1 ≤ B ≤ A(A-1)/2,
0 ≤ C ≤ A, və
-10000 ≤ x_i, y_i ≤ 10000.
Hər dataset üçün girişdən çıxışa qədər ən qısa yolun məsafəsini çap edin. Çıxış 10^{-1}-dən böyük olmayan bir mütləq səhv ehtiva etməməlidir. Əgər heç bir yol yoxdursa, -1 çap edin.
Nümunə 1