Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գրաֆի գունավորում

Ձեզ տրված է գրաֆ, որն ունի v гագաթներ և e կողեր, ինչպես նաև c հասանելի գույներ։ Ձեր խնդիրն է որոշել, թե արդյոք հնարավոր է գրաֆը գունավորել օգտագործելով տրված c գույները այնպես, որ որևէ երկու հարակից գագաթներ նույն գույնը չունենան։

Մուտք

Մուտքի առաջին տողում տրված են երեք ամբողջ թվեր v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) և c (1 ≤ c ≤ 10), որոնք, համապատասխանաբար, ցույց են տալիս գագաթների քանակը, կողերի քանակը և հասանելի գույների քանակը։

Հաջորդ e տողերում ներկայացված են գրաֆի կողերը։ Յուրաքանչյուր տող պարունակում է երկու ամբողջ թիվ a և b (1 ≤ a, b ≤ n, a ≠ b), որոնք ցույց են տալիս, որ գոյություն ունի կող գագաթ a-ի և գագաթ b-ի միջև։

Ելք

Եթե հնարավոր է գրաֆը գունավորել այնպես, որ որևէ երկու հարակից գագաթներ նույն գույնը չունենան, տպեք YES, հակառակ դեպքում տպեք NO։

Օրինակներ

Мուտք

Ելք

3 3 3
1 2
2 3
3 1

YES

3 3 2
1 2
2 3
3 1

NO

4 4 2
1 2
2 3
3 4
4 1

YES

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue