Solution.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static ArrayList<Integer> bfs(ArrayList<ArrayList<Integer>> adj, int s) {
        LinkedList<Integer> q = new LinkedList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>(adj.size());
        for (int i = 0; i < adj.size(); i++) {
            result.add(0);
        }
        q.addFirst(s);

        while (q.size() > 0) {
            int current = q.pollLast();
            ArrayList<Integer> tmp = adj.get(current);
            for (int i = 0; i < tmp.size(); i++) {
                int v = tmp.get(i);
                if (result.get(v) == 0) {
                    q.addFirst(v);
                    result.set(v, result.get(current) + 6);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){

            int n = in.nextInt();
            ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(n);
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<Integer>());
            }

            int m = in.nextInt();
            for(int a1 = 0; a1 < m; a1++){
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                // First
                ArrayList<Integer> tmp = adj.get(u);
                tmp.add(v);
                adj.set(u, tmp);

                // Second
                tmp = adj.get(v);
                tmp.add(u);
                adj.set(v, tmp);
            }

            int s = in.nextInt() - 1;

            ArrayList<Integer> result = Solution.bfs(adj, s);

            for (int i = 0; i < n; i++) {
                if (i != s) {
                    if (result.get(i) == 0) {
                        System.out.print("-1 ");
                    } else {
                        System.out.print(result.get(i) + " ");
                    }
                }
            }
            System.out.print("\n");
        }
        in.close();
    }
}