Համիլտոնյան շրջանցում
Ձեզ տրված է անուղղորդ գրաֆ, որն ունի
n գագաթ և e կող: Ձեր խնդիրն է պարզել, թե արդյոք այդ գրաֆում գոյություն ունի Համիլտոնյան շրջանցում (Hamiltonian cycle):💡
Համիլտոնյան շրջանցումը ուղի է, որն սկսվում և ավարտվում է նույն գագաթում՝ այցելելով յուրաքանչյուր գագաթը խստորեն մեկ անգամ:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n (1 ≤ n ≤ 20) և e (0 ≤ e ≤ ), որոնք սահմանում են գրաֆի գագաթների և կողերի քանակները, համապատասխանաբար:Հաջորդ
e տողերից յուրաքանչյուրում տրված են երկու ամբողջ թվեր a և b (1 ≤ a, b ≤ n, a ≠ b), որոնք ցույց են տալիս, որ գագաթ a-ն կապված է գագաթ b-ի հետ:Ելք
Եթե գրաֆում կա Համիլտոնյան ուղի կամ շրջանցում, տպեք
YES, հակառակ դեպքում տպեք NO:Օրինակներ
Մուտք | Ելք |
3 3
1 2
2 3
3 1 | YES |
4 4
1 2
2 3
3 1
2 4 | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB