Java Solution using a Graph class:

public class Solution {

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    Scanner scanner = new Scanner(System.in);
    int q = scanner.nextInt();

    while (q-- > 0){
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        Graph graph = new Graph(n);

        for (int i = 0; i < m; i++){
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph.addEdge(u, v);
        }

        int start = scanner.nextInt();
        int[] distances = graph.bfs(start);

        for (int i = 1; i <= n; i++){
            if (i != start){
                System.out.print(distances[i] + " ");
            }
        }
        System.out.println();
    }
    scanner.close();
}

}

class Graph { private final Map> adjList = new HashMap<>(); private final int numNodes;

public Graph(int numNodes){
    this.numNodes = numNodes;
    for (int i = 1; i <= numNodes; i++){
        adjList.put(i, new ArrayList<>());
    }
}

public void addEdge(int u, int v){
    adjList.get(u).add(v);
    adjList.get(v).add(u);
}

public int[] bfs(int start){
    int[] distances = new int[numNodes + 1];
    Arrays.fill(distances, -1);
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();

    queue.add(start);
    visited.add(start);
    distances[start] = 0;

    while (!queue.isEmpty()){
        int current = queue.poll();
        for (int neighbor : adjList.get(current)){
            if (!visited.contains(neighbor)){
                visited.add(neighbor);
                distances[neighbor] = distances[current] + 6;
                queue.add(neighbor);
            }
        }
    }
    return distances;
}

}

Java Solution using a Graph class:

class Graph { private final Map> adjList = new HashMap<>(); private final int numNodes;

public Graph(int numNodes){
    this.numNodes = numNodes;
    for (int i = 1; i <= numNodes; i++){
        adjList.put(i, new ArrayList<>());
    }
}

public void addEdge(int u, int v){
    adjList.get(u).add(v);
    adjList.get(v).add(u);
}

public int[] bfs(int start){
    int[] distances = new int[numNodes + 1];
    Arrays.fill(distances, -1);
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();

    queue.add(start);
    visited.add(start);
    distances[start] = 0;

    while (!queue.isEmpty()){
        int current = queue.poll();
        for (int neighbor : adjList.get(current)){
            if (!visited.contains(neighbor)){
                visited.add(neighbor);
                distances[neighbor] = distances[current] + 6;
                queue.add(neighbor);
            }
        }
    }
    return distances;
}

}

include

include

include

include

include

include

using namespace std;

class Graph { vector> adjList; int n;

public:
    Graph(int n) {
        adjList = vector<vector<int>> (n);
        this->n = n;
    }

    void add_edge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    vector<int> shortest_reach(int start) {
        vector<int> shortest_paths = vector<int>(n, -1);

        queue<int> q;
        q.push(start);
        vector<bool> visited(n);
        visited[start] = true;
        int curr_level = 1;
        while(q.size()){
            int level_size = q.size();
            while(level_size--){
                int curr_node = q.front();
                q.pop();
                for(int adj_val: adjList[curr_node]){
                    if(!visited[adj_val]){
                        shortest_paths[adj_val] = curr_level * 6;
                        visited[adj_val] = true;
                        q.push(adj_val);
                    }
                }
            }
            curr_level++;
        }
    return shortest_paths;
}

        return shortest_paths;
    }

};

"each node is labeled from 1 to n", this is in the first sentence of the description and also shown in the examples, however after spending hours to debug, I found out that in the main() function, it is decrementing the node's label so that it is actually labeled from 0 to n-1.

I just want to point this out, hopefully it will be helpful. This is for C++.

int main() { ...... // read and set edges for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; // add each edge to the graph graph.add_edge(u, v); } int startId; cin >> startId; startId--; // Find shortest reach from node s vector distances = graph.shortest_reach(startId);

Python

from collections import deque, defaultdict
class Graph:
    def __init__(self, n):
        self.n = n
        self.neighbors = defaultdict(set)
    
    def connect(self, a, b):
        self.neighbors[a].add(b)
        self.neighbors[b].add(a)

    
    def find_all_distances(self, start):
        distances = {}
        queue = deque((n, 1) for n in self.neighbors[start])
        visited = set([start])
        while queue:
            curr_node, dist_from_start = queue.popleft()
            if curr_node in visited:
                continue
            visited.add(curr_node)
            distances[curr_node] = dist_from_start * 6
            queue.extend((n, dist_from_start+1) for n in self.neighbors[curr_node])
        
        for i in range(0, self.n):
            if i == start:
                continue
            print(distances.get(i, -1), end=" ")
        print()