Ստուգել, թե արդյոք գրաֆը երկմասյա է
Գրաֆը կոչվում է երկմասյա, եթե կարելի է այն ներկել երկու գույներով այնպես, որ հարակից (կից) որևէ երկու գագաթներ չունենան նույն գույնը:
Երկմասյա լինելը պարզելը թույլ է տալիս բացահայտել որոշակի կառուցվածքներ և հատկություններ, ինչը նպաստում է արդյունավետ խնդիրների լուծմանը տարբեր ոլորտներում, օրինակ՝ ժամանակացույցերի կառուցում, ռեսուրսների բաշխում և հակասությունների կարգավորում: Բացի այդ, երկմասյա գրաֆերը հնարավորություն են տալիս օգտագործել ավելի պարզ ալգորիթմներ և օպտիմալացումներ այնպիսի դեպքերում, ինչպիսիք են maximum matching (առավելագույն matching) և գրաֆի ներկման (graph coloring) խնդիրները:
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով ոչ ուղղորդված գրաֆ v գագաթներով և e կողերով, պետք է ստուգի, թե արդյոք այն երկմասյա է:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր v (1 ≤ v ≤ 100000) և e (1 ≤ e ≤ 100000):
Հաջորդ e տողերից յուրաքանչյուրում տրվում է երկու ամբողջ թիվ v1, v2 (1 ≤ v1, v2 ≤ v), որոնք ցույց են տալիս, որ գագաթ v1-ը միացված է գագաթ v2-ին, և հակառակը:
Ելք
Ծրագիրը պետք է տպի Yes, եթե տրված գրաֆը երկմասյա է, հակառակ դեպքում — No:
Օրինակներ
Input | Output |
|---|---|
2 1 2 1 | Yes |
3 2 2 1 1 3 | Yes |
3 3 1 2 1 3 2 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB