Böyük divar
Kral Lyudovikin iki oğlu var. Onlar bir-birindən nifrət edirlər və kral, öz ölümündən sonra ölkəsinin dəhşətli müharibələrlə məhv olacağından qorxur. Buna görə də, Lyudovik ölkəsini iki hissəyə bölmək qərarına gəldi ki, hər bir hissədə oğullarından biri hakim olsun. O, oğullarını A və B şəhərlərində taxta oturtdu və bu şəhərlər arasında yolun olmaması üçün mümkün olan ən az sayda divar tikmək istəyir.
Lyudovikin ölkəsini sadələşdirilmiş şəkildə m×n ölçülü düzbucaqlı kimi təsəvvür etmək olar. Bu düzbucağın bəzi hüceyrələrində dağlar var, digərlərində isə sərbəst hərəkət etmək mümkündür. Bundan əlavə, bəzi hüceyrələr divar tikintisi üçün əlverişlidir, digərlərində isə tikinti mümkün deyil.
Ölkə daxilində səyahət edərkən, yalnız heç birində dağ və ya tikilmiş divar olmayan qonşu hüceyrəyə hərəkət etmək mümkündür.
Giriş verilənləri
Giriş faylının birinci sətirində m və n (1 ≤ m, n ≤ 50) ədədləri verilir. İkinci sətirdə k və l ədədləri verilir, burada 0 ≤ k, l, k + l ≤ m·n-2, k - dağların yerləşdiyi hüceyrələrin sayı, l - divar tikilə bilən hüceyrələrin sayı. Təbii ki, dağlarda divar tikmək mümkün deyil. Növbəti k sətir dağların yerləşdiyi hüceyrələrin koordinatlarını x_i və y_i göstərir, onlardan sonra isə divar tikilə bilən hüceyrələrin koordinatlarını göstərən l sətir gəlir - x_j və y_j. Son iki sətir müvafiq olaraq A (x_A və y_A) və B (x_B və y_B) şəhərlərinin koordinatlarını ehtiva edir. Bu k+l+2 sətirdə təsvir olunan hüceyrələr arasında iki eyni hüceyrə yoxdur. Zəmanət verilir ki, 1 ≤ x_i, x_j, x_A, x_B ≤ m və 1 ≤ y_i, y_j, y_A, y_B ≤ n.
Çıxış verilənləri
Çıxış faylının birinci sətirində tikilməli olan divar parçalarının minimal sayı F göstərilməlidir. Növbəti F sətirdə tikinti variantlarından biri göstərilməlidir.
Əgər lazımi tikintini həyata keçirmək mümkün deyilsə, çıxış faylında yeganə -1 ədədi göstərilməlidir.