PS3

// Copy paste this Java Template and save it as "HospitalRenovation.java"
import java.util.*;
import java.io.*;

// write your matric number here: A0155700N
// write your name here: Soh Zi Quan
// write list of collaborators here:
// year 2018 hash code: xrVYbth32e6GM6jXHLKb (do NOT delete this line) <- generate a new hash code

class HospitalRenovation {
  private int V; // number of vertices in the graph (number of rooms in the hospital)
  private int[][] AdjMatrix; // the graph (the hospital)
  private int[] RatingScore; // the weight of each vertex (rating score of each room)

  int [] visited, p;

  public HospitalRenovation() {

  }

  int [] dfs(int start, int[][] mat){
    visited = new int[V];
    p = new int[V];
    for (int i=0;i<V;i++){
      visited[i] = 0;
      p[i] = -1;
    }
    p[start] = 0;
    dfsrec(start, mat);

    return p;
  }

  void dfsrec(int u, int[][] mat){
    int [] neighbours = new int[V];
    for (int i=0;i<V;i++){
      neighbours[i] = -1;
    }
    visited[u] = 1;
    for (int i=0;i<V;i++){
      if (mat[u][i] != 0){
        neighbours[i] = i;
      }
    }

    for (int i=0;i<V;i++){
      if (neighbours[i] != -1 && visited[neighbours[i]] == 0){
        p[neighbours[i]] = u;
        dfsrec(neighbours[i], mat);
      }
    }
  }

  void printMat(int[][] arr){
    for (int i=0;i<arr.length;i++){
      String ln = "";
      for (int j=0;j<arr[0].length;j++){
        ln += arr[i][j] + " ";
      }
      System.out.println(ln);
    }
    System.out.println();
  }

  int Query() {
    int [] critical = new int[V];
    int ans = -1;

    for (int i=0;i<V;i++){
      critical[i] = -1;
    }


    for (int i=0;i<V;i++){
      int [] dfs;
      int start;
      //Perform DFS on copies of the graph with the ith vertex missing.
      int EditedAdjMatrix[] [] = new int[V][V];
      for (int j=0;j<V;j++) {
        for (int k=0;k<V;k++){
          if (i == j || i == k)
            EditedAdjMatrix[j][k] = 0;
          else
            EditedAdjMatrix[j][k] = AdjMatrix[j][k];
        }
      }
      //printMat(EditedAdjMatrix);
      if (i == 0)
        start = 1;
      else
        start = 0;

      dfs = dfs(start, EditedAdjMatrix);
      /*
      String line = "";
      for (int j=0;j<V;j++){
        line += dfs[j]+" ";
      }
      System.out.println(line);
      */

      for (int j=0;j<V;j++){
        if (i != j && start != j && dfs[j] == -1){
          critical[i] = i;
          break;
        }
      }
    }
    /*
    String l = "";
    for (int i=0;i<V;i++){
      l += critical[i]+" ";
    }
    System.out.println(l);
    */
    for (int i=0;i<V;i++){
      if (critical[i] != -1 && (ans == -1 || RatingScore[critical[i]] < ans)){
        ans = RatingScore[critical[i]];
      }
    }

    return ans;
  }

  void run() throws Exception {
    // for this PS3, you can alter this method as you see fit

    FileInputStream is = new FileInputStream(new File("C:/Users/Ziquan/Documents/School/CS2010/codecrunch/PS3/in3.txt"));
    System.setIn(is);

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int TC = Integer.parseInt(br.readLine()); // there will be several test cases
    while (TC-- > 0) {
      br.readLine(); // ignore dummy blank line
      V = Integer.parseInt(br.readLine());

      StringTokenizer st = new StringTokenizer(br.readLine());
      // read rating scores, A (index 0), B (index 1), C (index 2), ..., until the V-th index
      RatingScore = new int[V];
      for (int i = 0; i < V; i++)
        RatingScore[i] = Integer.parseInt(st.nextToken());

      // clear the graph and read in a new graph as Adjacency Matrix
      AdjMatrix = new int[V][V];
      for (int i = 0; i < V; i++) {
        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        while (k-- > 0) {
          int j = Integer.parseInt(st.nextToken());
          AdjMatrix[i][j] = 1; // edge weight is always 1 (the weight is on vertices now)
        }
      }

      pr.println(Query());
    }
    pr.close();
  }

  public static void main(String[] args) throws Exception {
    // do not alter this method
    HospitalRenovation ps3 = new HospitalRenovation();
    ps3.run();
  }
}



class IntegerPair implements Comparable < IntegerPair > {
  Integer _first, _second;

  public IntegerPair(Integer f, Integer s) {
    _first = f;
    _second = s;
  }

  public int compareTo(IntegerPair o) {
    if (!this.first().equals(o.first()))
      return this.first() - o.first();
    else
      return this.second() - o.second();
  }

  Integer first() { return _first; }
  Integer second() { return _second; }
}