Zadanie

Aké grafy?

Počet bodov: 10, časový limit: 2000ms

V tejto úlohe si najprv prejdeme zopár definícií.

Graf \(G\) je dvojica množín \((V,E)\), kde \(V\) je množina vrcholov (čísel) a \(E\) je množina dvojíc vrcholov, teda \(E \subseteq [V]^2\) – hrana \(\{a,b\}\) zaznačuje, že vrcholy \(a\) a \(b\) sú susedné.

Hranu spájajúcu vrchol sám so sebou nazývame slučka.

Graf nazývame planárny, ak sa dá nakresliť v rovine tak, že hrany majú prienik iba na ich koncoch. Jednoduchšie povedané, vieme na papier nakresliť vrcholy ako krúžky a hrany ako lomené čiary medzi nimi tak, že sa žiadna hrana nepretína s inou hranou.

Vrcholové farbenie grafu \(G = (V,E)\) je zobrazenie \(c\ :\ V \to S\), prvkom množiny \(S\) hovoríme aj farby.

Vrcholové k-farbenie grafu \(G = (V,E)\) je také horeuvedené zobrazenie, kde \(S = \{1,2,\ldots,k\}\).

Farbenie je regulárne, ak všetky susedné vrcholy majú rôzne farby.

Chromatické číslo \(\chi(G)\) je najmenšie \(k\) také, že \(G\) má regulárne vrcholové k-farbenie.

Nakoniec si dokážeme jednu zaujímavú vetu.

Veta (Heawood): Pre každý planárny graf \(G\) (bez slučiek) platí \(\chi(G)\leq 5\).

Dôkaz (obsahuje zopár výrazov, ktoré sme si nedefinovali. Ak sa vám niektorý výraz zdá dôležitý, použite internet):

Matematickou indukciou na počet vrcholov. Každý jednoduchý planárny graf má vrchol stupňa nanajvýš 5, povedzme \(v\). Zafarbime graf \(G−v\). Tento graf má menej vrcholov ako \(G\) a teda z indukčného predpokladu platí \(\chi(G)\leq 5\). Ak existuje farba nepoužitá na suseda \(v\) v \(G\), dofarbíme \(v\). Inak môžeme predpokladať, že susedia \(v\) v G sú \(v_1,v_2,...,v_5\) v cyklickom poradí podľa vnorenia a \(v_i\) je zafarbený farbou \(i\). Graf indukovaný ľubovoľnými dvoma farbami je bipartitný. Ak komponent grafu \(G−v\), indukovaný farbami 1 a 3 obsahujúci \(v_1\) neobsahuje \(v_3\), vymeníme farby v tomto komponente a vrchol \(v\) zafarbíme farbou 1. Vypíšte, či má graf párny počet hrán. Predpokladajme teda, že komponent grafu \(G−v\), indukovaný farbami 1 a 3 obsahujúci \(v_1\) obsahuje \(v_3\). Potom existuje cesta medzi \(v_1\) a \(v_3\) taká, že jej vrcholy majú striedavo farby 1 a 3. Urobme rovnakú úvahu aj pre \(v_2\) a \(v_4\). Rovnako, komponent indukovaný farbami 2 a 4 obsahujúci \(v_2\) obsahuje aj \(v_4\) a existuje cesta medzi nimi na ktorej sa striedajú farby 2 a 4. Z rozmiestenia vrcholov \(v_1\), \(v_2\), \(v_3\), \(v_4\) a \(v\) potom vidíme, že existujú kružnice tvorené cestami medzi \(v_1\)-\(v\)-\(v_3\) a \(v_2\)-\(v\)-\(v_4\) ktoré sa križujú, čo je spor s planaritou grafu \(G\). Teda komponent indukovaný farbami 2 a 4 obsahujúci \(v_2\) neobsahuje \(v_4\). Prefarbíme tento komponent a zafarbíme \(v\) farbou 2.

Táto veta od pána Heawooda je super, avšak nám nedáva návod ako zistiť, či má daný graf \(\chi(G) = 5\). To je dosť škoda.

Vstup a výstup

V prvom riadku vstupu je číslo \(n \leq 50\) a \(m \leq 200\) – počet vrcholov a hrán grafu.

Nasledujúcich \(m\) riadkov obsahuje dve čísla \(1 \leq a_i, b_i \leq n\) - hrany grafu.

Je zaručené, že uvedený graf je jednoduchý, planárny, a bez slučiek.

Vypíšte Ano alebo Nie tak, ako bolo popísané v zadaní.

Príklady

Input:

3 3
1 2
2 3
3 1

Output:

Nie

Input:

20 30
1 2
2 3
3 4
4 5
5 1
1 6
2 8
3 10
4 12
5 14
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 6
7 17
9 18
11 19
13 20
15 16
16 17
17 18
18 19
19 20
20 16

Output:

Ano