Két játékos egy bábuval felváltva lépked egy irányított gráf csúcsain. Aki olyan csúcsra lép, amelyből nem indul ki él, vesztett. Ha a bábu harmadszor kerül ugyanarra a mezőre, a játék eredménye döntetlen. Írjunk programot, ami a gráf mindegyik csúcsáról eldönti, hogy onnan indulva mi a legjobb eredmény, amit a kezdő biztosan el tud érni.
A programot a parancssorból fogjuk futtatni két paraméterrel, amelyek az input, illetve output fájl nevét tartalmazzák. Az input fájl fogja tartalmazni a gráfot. Az output fájlban kell felsorolni, hogy az egyes mezők nyerők vagy vesztők.
Az input fájl első sorában a csúcsok és az élek száma ($n\mathrm{,}m$) fog állni. A csúcsokat számozzuk $1$-től $n$-ig. A további $m$ sor egy-egy irányított él kezdő-, illetve végpontjának sorszámát tartalmazza. Az output fájl $n$ sorból álljon; az $i$-edik sor tartalma legyen N, D vagy V attól függően, hogy az $i$-edik csúcsból indulva a kezdő játékosnak nyerő stratégiája van, mindkét játékosnak van döntetlen stratégiája, vagy a második játékosnak van nyerő stratégiája.
Feltételezhetjük, hogy a gráfnak legfeljebb $1000000$ csúcsa és legfeljebb $50000000$ éle van.
Példa: a programot az s13 graf.txt eredmeny.txt paranccsal futtatjuk.