{"raw_statement":[{"iden":"statement","content":"This summer's heat wave and drought unleashed devastating wildfires all across the Earth. Of course, a tiny country on the island \"Yars and Eva\" is also affected by this ecological disaster. Thanks to the well-organized actions of rescuers, all the citizens were evacuated to the nearby planets on a spaceship.\n\nTo save the country, a small fire robot was left on its territory. He managed to extinguish fire in all cities except the capital before running out of liquid. The robot can't extinguish fire anymore, so the country is still in danger at the moment.\n\nThere are n cities in the country connected by m two-way roads. Each road connects a pair of cities. There is at most one road between any pair of cities. The cities are numbered from 1 to n, with capital having the number 1.\n\nThe fire spreads very quickly. On the very first day only the capital is on fire. But with every subsequent day, the fire devours all the cities connected by a road with the cities that are already on fire. Once the fire gets to a certain city, this city will continue to stay on fire till the very end.\n\nThe robot can't extinguish the fire anymore and there are no other means of firefighting left in the country, so obviously the country is going to be burned down to the ground. And you don't have to be a hero and save it. The key thing is that the robot is going to be destroyed by fire as well, and you need to figure out who will actually pay for the loss of government property.\n\nTwo pilots, Nikolay and Vladimir, are on Earth's natural satellite. They alternately take turns controlling the robot. The pilots alternate each day. Robot's speed is equal to the speed of fire, so the robot can get to the neighboring city in a day. Each pilot does not want the robot to be destroyed on his turn. For such a valuable loss they will have to pay a huge fee to the government.\n\nOn the first day the robot is located in the capital. Nikolay controls the robot on the first day. Thus, Nikolay controls the robot on the days with odd numbers, and Vladimir controls it on the days with even numbers. Taking turn, a pilot has to move the robot from the current city to any city connected by a road with the current one. If a pilot moves the robot to a city which is on fire, the robot is destroyed.\n\nYou task is to figure out who will pay the fine for the destroyed robot, assuming both pilots act optimally.\n\nThe first line of input contains the amount of cities n and the amount of roads m in the country (2 ≤ n ≤ 1000, n - 1 ≤ m ≤ 1000). The following m lines contain description of the roads: a, b — indices of the cities connected by roads (1 ≤ a ≤ n, 1 ≤ b ≤ n, a ≠ b). The roads are bidirectional. No pair of cities will be connected by more than one road. There will be a path between any two cities.\n\nOutput the name of the pilot who will pay the fine, assuming both pilots act optimally (\"_Nikolay_\" — if it is Nikolay, \"_Vladimir_\" — if it is Vladimir).\n\nIn the first sample test, an optimal strategy for Nicolay is to send the robot to the city 3 on the first day. Vladimir then will be forced to send the robot back to the capital, so the robot will be destroyed and Vladimir will have to pay.\n\n"},{"iden":"input","content":"The first line of input contains the amount of cities n and the amount of roads m in the country (2 ≤ n ≤ 1000, n - 1 ≤ m ≤ 1000). The following m lines contain description of the roads: a, b — indices of the cities connected by roads (1 ≤ a ≤ n, 1 ≤ b ≤ n, a ≠ b). The roads are bidirectional. No pair of cities will be connected by more than one road. There will be a path between any two cities."},{"iden":"output","content":"Output the name of the pilot who will pay the fine, assuming both pilots act optimally (\"_Nikolay_\" — if it is Nikolay, \"_Vladimir_\" — if it is Vladimir)."},{"iden":"examples","content":"Input4 31 21 32 4OutputVladimirInput4 41 21 32 43 4OutputNikolayInput4 51 21 32 43 42 3OutputNikolay"},{"iden":"note","content":"In the first sample test, an optimal strategy for Nicolay is to send the robot to the city 3 on the first day. Vladimir then will be forced to send the robot back to the capital, so the robot will be destroyed and Vladimir will have to pay."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, where vertices represent cities and edges represent roads. The capital is vertex $ 1 $.  \n\nLet $ d(v) $ denote the shortest distance (in number of edges) from vertex $ v $ to the capital (vertex $ 1 $).  \n\nLet $ t \\in \\mathbb{Z}^+ $ denote the day number, starting at $ t = 1 $. On day $ t $, fire spreads to all vertices at distance $ t $ from the capital.  \n\nThe robot starts at vertex $ 1 $ on day $ 1 $. On each day $ t $, the current pilot must move the robot along one edge to an adjacent vertex. If the robot moves to a vertex $ v $ with $ d(v) \\leq t $, it is destroyed.  \n\nPilot $ N $ (Nikolay) moves on odd days ($ t $ odd), pilot $ V $ (Vladimir) on even days ($ t $ even).  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 1000 $, $ n-1 \\leq m \\leq 1000 $  \n2. Graph is connected and undirected, no multiple edges.  \n3. Fire spreads deterministically: on day $ t $, all vertices at distance $ \\leq t $ from vertex $ 1 $ are on fire.  \n4. Robot must move each day to an adjacent vertex.  \n5. Both pilots play optimally to avoid destruction on their turn.  \n\n**Objective**  \nDetermine which pilot is forced to move the robot into a burning city (i.e., a vertex $ v $ with $ d(v) \\leq t $) under optimal play. Output \"Nikolay\" if Nikolay pays, \"Vladimir\" if Vladimir pays.  \n\nEquivalently:  \nFind the minimal $ t \\geq 1 $ such that from the robot’s position on day $ t $, all adjacent vertices $ u $ satisfy $ d(u) \\leq t $. The pilot who moves on day $ t $ pays.  \n\nAlternatively, model as a two-player impartial game on the graph with state $ (v, t) $, where $ v \\in V $, $ t \\in \\mathbb{Z}^+ $, and terminal states are when all neighbors of $ v $ are on fire (i.e., $ \\forall u \\in N(v), d(u) \\leq t $). Determine the winner under optimal play with Nikolay starting.","simple_statement":"Nikolay and Vladimir take turns moving a robot on a graph of n cities and m roads. Fire starts at city 1 (the capital) on day 1 and spreads to all connected cities each day. The robot starts at city 1 on day 1. Nikolay moves first (odd days), Vladimir second (even days). Each turn, a pilot must move the robot to an adjacent city. If the robot moves into a burning city, it is destroyed and that pilot pays. Both play optimally. Who pays?","has_page_source":false}