D2008

/////////////////////////////////
package d2008;

import java.util.Scanner;

public class MoiDamCuoi {
	static int t,n,m,u,v;
	static int[][] a = new int[n+1][n+1];
	static int[] visit = new int[n+1];
	static class Queue{
		int front,rear;
		int[] data = new int[90001];
		public Queue(){
			front = rear = 0;
		}
		public void enQ(int n){
			data[rear++] = n;
		}
		public int deQ(){
			return data[front++];
		}
		public int qPeek(){
			return data[front];
		}
		public boolean isEmpty(){
			if(front == rear){
				return true;
			}
			return false;
		}
	}
	public static boolean BFS(int u, int v){
		Queue q = new Queue();
		q.enQ(u);
		visit[u] = 1;
		while(!q.isEmpty()){
			int nx = q.deQ();
			for(int i = 1 ; i <= n ; i++){
				if(a[nx][i] == 1 && visit[i] == 0 ){
					visit[i] = 1;
					q.enQ(i);
				}
			}
			if(nx == v){
				return true;
			}
		}
		return false;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t ; tc++){
			n = sc.nextInt();
			m = sc.nextInt();
			u = sc.nextInt();
			v = sc.nextInt();
			a = new int[n+1][n+1];
			visit = new int[n+1];
			for(int i = 0 ; i < m ; i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x][y] = 1;
			}
			int res = 0;
			for(int i = 1 ; i <= n ; i++){
				if(i == u || i == v){
					continue;
				}
				visit = new int[n+1];
				visit[i] = 1;
				if(!BFS(u, v)){
					res++;
				}
			}
			System.out.println(res);
			System.out.println();
		}
	}

}
//////////////////
package d2008;

import java.util.Scanner;

public class DiAnCuoi {	
	static int t,n,m;
	static int[][] a = new int[n+1][n+1];
	static int[] visit = new int[n+1];
	static int res = 99999999;
	public static void Try(int k,int cnt){
		if(cnt > res ){
			return;
		}
		if(visit[1]==2){
			if(visit[2] == 1){
				res = Math.min(res, cnt);
			}
			return;
		}
		for(int i = 1 ; i <= n ; i++){
			if(a[k][i] == 1){
				if(visit[i] == 0){
					visit[i] = 1;
					Try(i, cnt+1);
					visit[i] =0;
				}
				if(visit[i] == 1){
					visit[i]++;
					Try(i, cnt);
					visit[i]--;
				}
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t; tc++){
			n = sc.nextInt();
			m = sc.nextInt();
			a = new int[n+1][n+1];
			visit = new int[n+1];
			for(int i = 0 ; i < m ; i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x][y] = 1;
			}
			
			res = 99999999;
			visit[1]=1;
			Try(1, 1);
			System.out.println(res);
		}
	}

}
////////////////////////////
package d2008;

import java.util.Scanner;

public class HugoGiaoHang {
	static int t,sx,sy,hx,hy,n;
	static int[][] a = new int[n+1][2];
	static boolean[] visit = new boolean[n+1];
	public static int cal(int x1,int y1,int x2,int y2){
		return Math.abs(x1-x2)+Math.abs(y1-y2);
	}
	static int res = 99999999;
	public static void Try(int k,int cnt,int prev){
		if(k == n+1){
			int tmp = cal(hx, hy, a[prev][0], a[prev][1]);
			if(res > cnt + tmp){
				res = cnt +tmp;
			}
		}
		if(cnt > res){
			return;
		}
		for(int i = 1 ; i <= n ; i++){
			if(visit[i] == false){
				visit[i] = true;
				int tmp = cal(a[prev][0], a[prev][1], a[i][0], a[i][1]);
				Try(k+1, cnt+tmp, i);
				visit[i] = false;
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t ; tc++){
			sx = sc.nextInt();
			sy = sc.nextInt();
			hx = sc.nextInt();
			hy = sc.nextInt();
			n = sc.nextInt();
			a = new int[n+1][2];
			a[0][0]= sx;
			a[0][1]= sy;
			visit = new boolean[n+1];
			for(int i = 1 ; i <= n ; i++){
				a[i][0] = sc.nextInt();
				a[i][1] = sc.nextInt();
			}
			res = 99999999;
			Try(1, 0, 0);
			System.out.println("Case #"+tc+" " +res);
			
		}
	}

}
//////////////////////////
package d2008;

import java.util.Scanner;

public class HugoDaoVangLevel4 {
	static int t, n, g;
	static int[][] a = new int[n][n];
	static int[][] movang = new int[g][2];
	static int res = 9999999;
	static int[][] visit = new int[n][n];
	static int[][] step = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };

	static class Queue {
		int front, rear;
		int[] data = new int[90001];

		public Queue() {
			front = rear = 0;
		}

		public void enQ(int n) {
			data[rear++] = n;
		}

		public int deQ() {
			return data[front++];
		}

		public int qPeek() {
			return data[front];
		}

		public boolean isEmpty() {
			if (front == rear) {
				return true;
			}
			return false;
		}
	}

	public static boolean checkMoVang(int r, int c) {
		for (int i = 0; i < g; i++) {
			if (movang[i][0] == r + 1 && movang[i][1] == c + 1) {
				return true;
			}
		}
		return false;
	}

	public static int solve() {
		int cnt = 0;
		for (int i = 0; i < g; i++) {
			if (visit[movang[i][0] - 1][movang[i][1] - 1] > cnt) {
				cnt = visit[movang[i][0] - 1][movang[i][1] - 1];
			}
		}
		return cnt;
	}

	public static void BFS(int r, int c) {
		Queue qx = new Queue();
		Queue qy = new Queue();
		qx.enQ(r);
		qy.enQ(c);
		visit[r][c] = 1;
		while (!qx.isEmpty() && !qy.isEmpty()) {
			int nx = qx.deQ();
			int ny = qy.deQ();
			for (int i = 0; i < 4; i++) {
				int tmpx = nx + step[i][0];
				int tmpy = ny + step[i][1];
				if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n
						&& visit[tmpx][tmpy] == 0 && a[tmpx][tmpy] == 1) {
					visit[tmpx][tmpy] = visit[nx][ny] + 1;
					qx.enQ(tmpx);
					qy.enQ(tmpy);
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			n = sc.nextInt();
			g = sc.nextInt();
			a = new int[n][n];
			movang = new int[g][2];
			visit = new int[n][n];
			for (int i = 0; i < g; i++) {
				movang[i][0] = sc.nextInt();
				movang[i][1] = sc.nextInt();
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			res = 9999999;
			int x = -1, y = -1;
			int dem = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (a[i][j] == 1 && !checkMoVang(i, j)) {
						visit = new int[n][n];
						BFS(i, j);
						int tmp = solve();
						int dem1 = 0;
						for (int k = 0; k < g; k++) {
							if (visit[movang[k][0] - 1][movang[k][1] - 1] != 0) {
								dem1++;
							}
						}
						if(dem1 == dem){
							if(res > tmp && tmp!=0){
								res = tmp;
								x = i;
								y = j;
							}
						}
						else if(dem1 > dem){
							dem = dem1;
							res = tmp;
							x = i;
							y = j;
						}
						
					}
				}
			}
			System.out.println("Case #" + tc);
			if (res == 9999999) {
				System.out.println(-1);
			} else {
				System.out.println(res-1);
				visit = new int[n][n];
				BFS(x, y);
				for (int i = 0; i < g; i++) {
					if (visit[movang[i][0] - 1][movang[i][1] - 1] == 0) {
						System.out.println(movang[i][0] + " " + movang[i][1]);
					}
				}
			}
		}
	}

}
/////////////////////////////
package d2008;

import java.util.Scanner;

public class HugoDaoVang {
	static int t,n,g;
	static int[][] a = new int[n][n];
	static int[][] movang = new int[g][2];
	static int res = 9999999;
	static int[][] visit = new int[n][n];
	static int[][] step = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
	static class Queue{
		int front,rear;
		int[] data = new int[90001];
		
		public Queue(){
			front = rear = 0;
		}
		public void enQ(int n){
			data[rear++] = n;
		}
		public int deQ(){
			return data[front++];
		}
		public int qPeek(){
			return data[front];
		}
		public boolean isEmpty(){
			if(front == rear){
				return true;
			}
			return false;
		}
	}
	public static boolean checkMoVang(int r,int c){
		for(int i = 0 ; i < g ; i++){
			if(movang[i][0] == r+1 && movang[i][1] == c+1){
				return true;
			}
		}
		return false;
	}
	public static int solve(){
		int cnt = 0;
		int dem = 0;
		for(int i = 0 ; i < g ; i++){
			if(visit[movang[i][0]-1][movang[i][1]-1] > cnt ){
				cnt = visit[movang[i][0]-1][movang[i][1]-1];
			}
			if(visit[movang[i][0]-1][movang[i][1]-1] != 0){
				dem++;
			}
		}
		if(dem == g){
			return cnt;
		}
		return 0;
	}
	public static void BFS(int r,int c){
		Queue qx = new Queue();
		Queue qy = new Queue();
		qx.enQ(r);
		qy.enQ(c);
		visit[r][c] = 0;
		while(!qx.isEmpty() && !qy.isEmpty()){
			int nx = qx.deQ();
			int ny = qy.deQ();
			for(int i = 0 ; i < 4 ; i++){
				int tmpx = nx + step[i][0];
				int tmpy = ny + step[i][1];
				if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n && visit[tmpx][tmpy] == 0 && a[tmpx][tmpy] == 1){
					visit[tmpx][tmpy] = visit[nx][ny]+1;
					qx.enQ(tmpx);
					qy.enQ(tmpy);
				}
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t ; tc++){
			n = sc.nextInt();
			g = sc.nextInt();
			a = new int[n][n];
			movang = new int[g][2];
			visit = new int[n][n];
			for(int i = 0 ; i < g ; i++){
				movang[i][0] = sc.nextInt();
				movang[i][1] = sc.nextInt();
			}
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			res = 9999999;
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					if(a[i][j] == 1 && !checkMoVang(i, j)){
						visit = new int[n][n];
						BFS(i, j);
						int tmp = solve();
						if(res > tmp && tmp!=0){
							res = tmp;
						}
					}
				}
			}
			System.out.println("Case #"+tc);
			if(res == 9999999){
				System.out.println(-1);
			}
			else{
				System.out.println(res);
			}
		}
	}

}