Adott egy ország $N$ ($1\le N\le 17$) várossal. A városok közül $M$ db kétirányú úttal van összekötve. Szeretnénk az országban minél több típusú tudományos konferenciát szervezni. Egy adott típusú konferenciát több városban is meg lehet szervezni, de egy városban legfeljebb egy konferencia szervezhető. Egy adott városból csak szomszédos városba lehet menni konferenciára, illetve természetesen az adott városban szervezett konferencia is látogatható. Szeretnénk minél több konferenciatípust szervezni, úgy, hogy bármely város lakói bármelyik típusú konferenciára elmehessenek. Például egyféle konferenciát mindig tudunk szervezni: minden városban ugyanazt a típust szervezzük meg.
A program olvassa be a standard input első sorából $N$-et és $M$-et, majd a következő $M$ sorból az egyes utakat összekötő városokat, és írja a standard output első és egyetlen sorába, a lehető legtöbb típusú konferenciák számát, amit az adott ország meg tud szervezni.