<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

520. Fire in the Country
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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.

To 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.

There 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.

The 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.

The 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.

Two 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.

On 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.

You task is to figure out who will pay the fine for the destroyed robot, assuming both pilots act optimally.

Input
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.

Output
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).

Example(s)
sample input
sample output
4 3
1 2
1 3
2 4
Vladimir

sample input
sample output
4 4
1 2
1 3
2 4
3 4
Nikolay

sample input
sample output
4 5
1 2
1 3
2 4
3 4
2 3
Nikolay



Note
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.

<|response|>
1. Abridged Problem Statement  
We have a connected undirected graph of n cities (nodes) and m roads (edges). City 1 is the capital. Fire starts at city 1 on day 1 and spreads each day to all adjacent cities. A robot also starts at city 1 on day 1 and must move along exactly one edge per day. If it enters a city already on fire, the current pilot loses. Pilots alternate moves: Nikolay moves on odd days, Vladimir on even days. Both play optimally. Determine which pilot will lose.

2. Key Observations  
- The fire reaches each city v exactly at day = dist[v], where dist[v] is the shortest-path distance from city 1 to v.  
- On day d at city u, any neighbor v with dist[v] ≤ dist[u] is already on fire or catches fire that day; moving there is losing. The only safe moves are to neighbors v with dist[v] = dist[u] + 1.  
- These safe moves form a directed acyclic graph (DAG) of “forward” edges u→v if dist[v] = dist[u] + 1.  
- The game reduces to a token on node 1 of this DAG; players alternate moving it along one forward edge. A player with no forward move must move into fire and loses.  
- On a finite DAG, the standard win/lose DP holds: a node u is winning if there exists an outgoing edge u→v to a losing node v; otherwise u is losing.

3. Full Solution Approach  
Step 1. Read n, m and build the undirected adjacency list adj.  
Step 2. Run a BFS from node 1 to compute dist[1..n], the shortest distance to each node.  
Step 3. Build a forward-edge DAG: for each u, collect all neighbors v such that dist[v] = dist[u] + 1. Call this dag[u].  
Step 4. Define a DP array win[u] with three states: –1 (unvisited), 0 (losing), 1 (winning).  
Step 5. Recursively compute win[u] by DFS on the DAG:  
 • If any v in dag[u] has win[v] = 0, then win[u] = 1.  
 • Otherwise, win[u] = 0.  
Step 6. After computing win[1]:  
 • If win[1] = 1, the first player (Nikolay) wins, so the loser is Vladimir.  
 • If win[1] = 0, the first player loses, so the loser is Nikolay.  

Time complexity is O(n + m) for BFS, DAG construction, and DFS on the DAG. Memory is O(n + m).

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // 1) Read undirected graph
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 2) BFS from node 1 to compute dist[]
    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    // 3) Build DAG of forward edges: u -> v if dist[v] = dist[u] + 1
    vector<vector<int>> dag(n + 1);
    for (int u = 1; u <= n; u++) {
        for (int v : adj[u]) {
            if (dist[v] == dist[u] + 1) {
                dag[u].push_back(v);
            }
        }
    }

    // 4) DP array: -1 = unvisited, 0 = losing, 1 = winning
    vector<int> win(n + 1, -1);

    // 5) DFS to compute win[u]
    function<int(int)> dfs = [&](int u) -> int {
        if (win[u] != -1) return win[u];
        // Assume losing until we find a move to a losing child
        win[u] = 0;
        for (int v : dag[u]) {
            if (dfs(v) == 0) {
                win[u] = 1;
                break;
            }
        }
        return win[u];
    };

    // Compute game result from start node 1
    int startResult = dfs(1);

    // 6) Output loser name
    // If startResult = 1, Nikolay (first player) wins => loser is Vladimir
    // If startResult = 0, first player loses => loser is Nikolay
    if (startResult == 1)
        cout << "Vladimir\n";
    else
        cout << "Nikolay\n";

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
from collections import deque
sys.setrecursionlimit(10**7)

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    
    # 1) Read undirected graph
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # 2) BFS from node 1 to get dist[]
    INF = 10**9
    dist = [INF] * (n + 1)
    dist[1] = 0
    q = deque([1])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == INF:
                dist[v] = dist[u] + 1
                q.append(v)
    
    # 3) Build DAG: only edges u->v with dist[v] = dist[u] + 1
    dag = [[] for _ in range(n + 1)]
    for u in range(1, n + 1):
        for v in adj[u]:
            if dist[v] == dist[u] + 1:
                dag[u].append(v)
    
    # 4) win[u]: -1 = unvisited, 0 = losing, 1 = winning
    win = [-1] * (n + 1)
    
    # 5) DFS on DAG to fill win[]
    def dfs(u):
        if win[u] != -1:
            return win[u]
        # Assume losing
        win[u] = 0
        # If any move leads to a losing state, current is winning
        for v in dag[u]:
            if dfs(v) == 0:
                win[u] = 1
                break
        return win[u]
    
    # Compute outcome from start node 1
    start_win = dfs(1)
    
    # 6) Determine who loses
    # If start_win == 1, first player (Nikolay) wins => loser is Vladimir
    # Else loser is Nikolay
    if start_win == 1:
        print("Vladimir")
    else:
        print("Nikolay")

if __name__ == "__main__":
    main()
```