Ստուգել, թե արդյոք գրաֆը երկմասյա է
Գրաֆը կոչվում է երկմասյա, եթե կարելի է այն ներկել երկու գույներով այնպես, որ հարակից (կից) որևէ երկու գագաթներ չունենան նույն գույնը:
Երկմասյա լինելը պարզելը թույլ է տալիս բացահայտել որոշակի կառուցվածքներ և հատկություններ, ինչը նպաստում է արդյունավետ խնդիրների լուծմանը տարբեր ոլորտներում, օրինակ՝ ժամանակացույցերի կառուցում, ռեսուրսների բաշխում և հակասությունների կարգավորում: Բացի այդ, երկմասյա գրաֆերը հնարավորություն են տալիս օգտագործել ավելի պարզ ալգորիթմներ և օպտիմալացումներ այնպիսի դեպքերում, ինչպիսիք են 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