Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Prepared by Ibrahim Mesecan.
Të lidhura?
Përktheu: Kamila Hasanbega
English
Në një grafik G, dy pika u dhe v janë quajtur të lidhura në qoftë G përmban një rrugë nga u në v. Përndryshe, ato quhen jo te lidhura .Nëse dy pika janë të lidhura me nje segment me gjatesi 1 , dmth nga nje lidhje e vetme, pikat quhet se jane ngjitur. Një grafik quhet i lidhur në qoftë se çdo cift pikash në grafik është e lidhur.
Në figurën në të majtë , është një grafik me një drejtim me 3 pika dhe një lidhje; midis pikave 2 dhe 5. Kur grafiku është i nje drejtimi , dhe ka një lidhje nga u në v, do të thotë se ka edhe një lidhje nga v në u. Kështu, ne kemi një lidhje 2-5 do të thotë se kemi edhe një lidhje 5-2. Por nuk ka asnjë lidhje te 1 me ndonjë pikë tjetër.
Shkruaj një program që do të lexojë numrin e pikave dhe lidhjet mes tyre nga input. Dhe pastaj, programi do të zbulojë nëse ka rrugë mes dy pikave të dhëna.
Input
Linja e parë ka dy numra n (2 ≤ n ≤ 20 ) dhe e (1 ≤ e ≤ 400 ),
ku n është numri i pikave dhe e është numri i lidhjeve mes tyre.
Rreshtat e mëposhtëm do të përmbajnë dy numra u dhe v ku 1 ≤ u, v ≤ n. Dhe, u është pika e fillimit, v është destinacioni. Që do të thotë u është ngjitur me v (egziston nje lidhje nga u tek v). Në rreshtin e fundit, do të ketë dy numrat a dhe b (1 ≤ a, b ≤ n ), të cilat paraqesin fillimin dhe destionation për të cilën ju jeni duke pare nqs egziston nje lidhje midis tyre apo jo.
Output
Ju do të shfaqni një rresht të vetëm ku do të shfaqet "YES", në qoftë se ka një lidhje midis a dhe b në të kundërt do të shfaqet "NO".
Shënim i rëndësishëm: Shifrat e mëposhtme janë vetëm për ilustrim te ushtrimit . Në dosjen input ju do të keni vetëm numra si u shpjeguan me sipër.
Shembull input I
4 3
4 2
1 3
3 4
1 2
| |
Shembull output I
YES
Shembull input II
4 4
1 3
1 4
3 4
2 1
3 2
|
|
Shembull output II
YES
Для отправки решений необходимо выполнить вход.
|