Main.java

import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

    public static void read_and_solve(InputStream in, PrintStream out) {
        Scanner s = new Scanner(in);

        int t = s.nextInt();

        for (int i = 0; i < t; i++) {
            int n = s.nextInt();

            HashMap<Integer, Vertex> vertices = new HashMap<Integer, Vertex>();

            for(int j = 0; j < n; j++) {
                vertices.put(j, new Vertex(j));
            }

            int m = s.nextInt();
            ArrayList<Edge> edges = new ArrayList<Edge>();

            int r = s.nextInt(); // best friend

            for(int j = 0; j < m; j++) {
                int u = s.nextInt();
                int v = s.nextInt();

                Vertex vertexU = vertices.get(u);
                Vertex vertexV = vertices.get(v);

                Edge e = new Edge(vertexU, vertexV);
                edges.add(e);
                vertexU.adj.add(e);
                vertexV.adj.add(e);
            }

            String result = solve(edges, vertices, r);

            out.println(result);
        }
    }

    public static void main(String[] args) {
        read_and_solve(System.in, System.out);
    }

    public static String solve(ArrayList<Edge> edges, HashMap<Integer, Vertex> vertices, int friendId) {

        for(Integer root : vertices.keySet()) {
            if(!vertices.get(root).dfsVisited) {
                dfs(vertices.get(root), edges, 1);
            }
        }

        for(Edge e : edges) {
            if(e.u.color == e.v.color) return "no";
        }

        Vertex friend = vertices.get(friendId);

        ArrayList<Vertex> collection = new ArrayList<Vertex>();

        for(Integer vertex : vertices.keySet()) {
            Vertex v = vertices.get(vertex);

            if(v.color == friend.color) {
                collection.add(v);
            }
        }


        String result = collection.toString();
        result = result.replace("[", "");
        result = result.replace("]", "");
        result = result.replace(",", "");


        return result.trim();
    }

    private static void dfs(Vertex current, ArrayList<Edge> allEdges, int currentColor) {
        current.dfsVisited = true;
        current.color = currentColor;
        int nextColor = currentColor * -1;

        for(Edge e : current.adj) {
            if(e.u == current && !e.v.dfsVisited) {
                dfs(e.v, allEdges, nextColor);
            } else if(e.v == current && !e.u.dfsVisited) {
                dfs(e.u, allEdges, nextColor);
            }
        }
    }
}

class Edge {
    Vertex u;
    Vertex v;

    public Edge(Vertex u, Vertex v) {
        this.u = u;
        this.v = v;
    }
}

class Vertex {
    int id;
    boolean dfsVisited = false;
    int color = 0; // 0: no color; 1: color 1, -1: color 2.
    ArrayList<Edge> adj;

    public Vertex(int id) {
        this.id = id;
        this.adj = new ArrayList<Edge>();
    }

    public String toString() {
        return id + "";
    }
}