from collections import deque

def shortest_distance(graph, src):
    n = len(graph)
    dist = [float('inf')] * n
    dist[src] = 0

    q = deque([src])

    while q:
        curr = q.popleft()
        for neighbor in graph[curr]:
            if dist[neighbor] == float('inf'):
                dist[neighbor] = dist[curr] + 1
                q.append(neighbor)

    return dist


graph = [
    [1, 2],   # 0
    [3],      # 1
    [4],      # 2
    [5],      # 3
    [3],      # 4
    []        # 5
]

print(shortest_distance(graph, 0))
    

import java.util.*;

class Solution {
    static int[] shortestDistance(List> graph, int src) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        Queue q = new LinkedList<>();
        q.add(src);

        while (!q.isEmpty()) {
            int curr = q.poll();
            for (int neighbor : graph.get(curr)) {
                if (dist[neighbor] == Integer.MAX_VALUE) {
                    dist[neighbor] = dist[curr] + 1;
                    q.add(neighbor);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        List> graph = new ArrayList<>();

        graph.add(Arrays.asList(1, 2));
        graph.add(Arrays.asList(3));
        graph.add(Arrays.asList(4));
        graph.add(Arrays.asList(5));
        graph.add(Arrays.asList(3));
        graph.add(new ArrayList<>());

        System.out.println(Arrays.toString(shortestDistance(graph, 0)));
    }
}
  

#include <bits/stdc++.h>
using namespace std;

vector shortestDistance(vector>& graph, int src) {
    int n = graph.size();
    vector dist(n, INT_MAX);
    dist[src] = 0;

    queue q;
    q.push(src);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int neighbor : graph[curr]) {
            if (dist[neighbor] == INT_MAX) {
                dist[neighbor] = dist[curr] + 1;
                q.push(neighbor);
            }
        }
    }
    return dist;
}

int main() {
    vector> graph = {
        {1, 2},
        {3},
        {4},
        {5},
        {3},
        {}
    };

    vector res = shortestDistance(graph, 0);
    for (int x : res) cout << x << " ";
}

#include <stdio.h>
#include <limits.h>

int graph[6][2] = {
    {1, 2},
    {3},
    {4},
    {5},
    {3},
    {}
};

int size[] = {2, 1, 1, 1, 1, 0};

int main() {
    int n = 6, src = 0;
    int dist[6];

    for (int i = 0; i < n; i++)
        dist[i] = INT_MAX;

    dist[src] = 0;

    int queue[6], front = 0, rear = 0;
    queue[rear++] = src;

    while (front < rear) {
        int curr = queue[front++];

        for (int i = 0; i < size[curr]; i++) {
            int neighbor = graph[curr][i];
            if (dist[neighbor] == INT_MAX) {
                dist[neighbor] = dist[curr] + 1;
                queue[rear++] = neighbor;
            }
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", dist[i]);

    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    static int[] ShortestDistance(List[] graph, int src) {
        int n = graph.Length;
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;

        Queue q = new Queue();
        q.Enqueue(src);

        while (q.Count > 0) {
            int curr = q.Dequeue();
            foreach (int neighbor in graph[curr]) {
                if (dist[neighbor] == int.MaxValue) {
                    dist[neighbor] = dist[curr] + 1;
                    q.Enqueue(neighbor);
                }
            }
        }
        return dist;
    }

    static void Main() {
        List[] graph = new List[] {
            new List{1, 2},
            new List{3},
            new List{4},
            new List{5},
            new List{3},
            new List()
        };

        var result = ShortestDistance(graph, 0);
        Console.WriteLine(string.Join(" ", result));
    }
}