class Pair
{
    int first;
    int second;
    Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}

class Solution {
    public int[] shortestPath(int V, int[][] edges, int src) {
        // Step-1 create a adjancency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<>());
        }
        
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        // Step-2 Traverse through nodes starting from source node
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(src, 0));
        
        // Step-3 Create a distance matrix which will store shortest distance for each node
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[src ] = 0;
        
        // Step-4 Traverse through nodes
        while(!q.isEmpty())
        {
            Pair pair = q.poll();
            int node = pair.first;
            int dist = pair.second;
            
            // traverse through neighbour nodes
            for(int u : adj.get(node))
            {
                // if distance of neighbour node is greater than the current distance+1 then update it
                if(distance[u] > dist+1)
                {
                    distance[u] = dist+1;
                    q.add(new Pair(u, dist+1));
                }
            }
        }
        
        for(int i=0; i<V; i++)
        {
            // If a vertex is not reachable from the source, return -1 for that vertex
            if(distance[i] == Integer.MAX_VALUE)
                distance[i] = -1;
        }
        return distance;
    }
}