D2308

package d0508;

public class LuyThua {
	static long x,n;
	public static long luythua(int x,int n){
		if(n == 1){
			return x;
		}
		if(n%2 == 0){
			long y = luythua(x, n/2);
			return y*y;
		}
		else{
			long y = luythua(x, (n-1)/2);
			return y*y*x;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(luythua(30, 10));
	}
}
//////
package d0508;

import java.util.Scanner;

public class MatrixProduct {
	static int t,n,m;
	static long[][] a = new long[n][n];
	static int mod = 100000007;
	public static long[][] mul(long[][] a1,long[][] a2){
		long[][] res = new long[n][n];
		for(int i = 0 ; i < n ; i++){
			for(int j = 0 ; j < n ; j++){
				long tmp = 0;
				for(int k = 0 ; k < n ; k++){
					tmp = (tmp%mod + ((a1[i][k]%mod)*(a2[k][j]%mod))%mod)%mod;
				}
				res[i][j] = tmp;
			}
		}
		return res;
	}
	public static long[][] pow(long[][] a, int n){
		if(n == 1){
			return a;
		}
		if(n%2 == 0){
			long[][] tmp = pow(a, n/2);
			return mul(tmp, tmp);
		}
		else{
			long[][] tmp = pow(a, (n-1)/2);
			return mul(mul(tmp, tmp),a);
		}
	}
	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 long[n][n];
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			long[][] res = pow(a, m);
			System.out.println("Case #"+tc);
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					System.out.print(res[i][j]+" ");
				}
				System.out.println();
			}
		}
	}

}
/////
package d0508;

import java.util.Scanner;

public class MinimalBigSum {
	static int t,k,n;
	static int[] a = new int[n];
	static int res = 10000007;
	public static void solve(int sum){
		int left = 0 , right = sum;
		while(left <= right){
			int mid = (left+right)/2;
			if(check(mid)){
				right = mid - 1;
			}
			else{
				left = mid + 1;
			}
		}
		res = left;
	}
	
	public static boolean check(int mid){
		int dem = 0 , tmp = 0;
		for(int i = 0 ; i < n ; i++){
			if(a[i] > mid){
				return false;
			}
			if(tmp+a[i] > mid){
				dem++;
				tmp = a[i];
			}
			else{
				tmp+=a[i];
			}
		}
		if(tmp > 0){
			dem++;
		}
		if(dem <= k){
			return true;
		}
		else{
			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++){
			k = sc.nextInt();
			n = sc.nextInt();
			a = new int[n];
			int sum = 0;
			for(int i = 0 ; i < n ; i++){
				a[i] = sc.nextInt();
				sum += a[i];
			}
			solve(sum);
			System.out.println("#"+tc+" "+res);
		}
	}

}
/////////////
package d0508;

import java.util.Scanner;

public class PointOfBalance2 {
	static int n;
	static double[] a = new double[n];
	static double[] m = new double[n];
	static double res;
	final static double delta = 0.00000000001;
	public static double F(double x, double p, double m) {
		double d;
		if(x > p){
			d = x - p;
		}
		else{
			d = p - x;
		}
		return m/(d*d);
	}
	public static double check(double left,double right,int i1, int i2){
		if(right - left < delta){
			return res;
		}
		res = (left+right)/2;
		double f = 0;
		for(int i = 0 ; i <= i1 ; i++){
			f = f + F(a[i],res,m[i]);
		}
		for(int i = i2 ; i < n ; i++){
			f = f - F(a[i],res,m[i]);
		}
		if(f < delta){
			return check(left, res, i1, i2);
		}
		if(f > delta){
			return check(res, right, i1, i2);
		}
		return res;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		for(int t = 1 ; t <= 10 ; t++){
			n = sc.nextInt();
			a = new double[n];
			m = new double[n];
			for(int i = 0 ; i < n ; i++){
				a[i] = sc.nextDouble();
			}
			for(int i = 0 ; i < n ; i++){
				m[i] = sc.nextDouble();
			}
			System.out.print("#"+t+" ");
			for(int i = 0 ; i < n-1 ; i++){
				System.out.print(String.format("%.10f", check(a[i], a[i+1], i, i+1)) + " ");
			}
			System.out.println();
		}
	}

}
///////////////
package d0608;
import java.util.Scanner;

public class Diamond {
	static class Queue {
		private int front;
		private int rear;
		private int[] data = new int[90001];

		Queue() {
			front = rear = 0;
		}

		public void enQueue(int num) {
			data[rear++] = num;
		}

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

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

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

		public void reset() {
			front = rear = 0;
		}

		public int size() {
			return rear - front;
		}
	}

	static int n;
	static String res;
	static int[][] arr = new int[1005][1005];
	static boolean[] visited = new boolean[1005];
	static Queue queue = new Queue();

	public static void main(String[] args) {
		// System.setIn(new FileInputStream("src/G_Diamond/input.txt"));
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			// input
			n = sc.nextInt();
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					arr[i][j] = 0;
				}

				int m = sc.nextInt();
				for (int j = 0; j < m; j++) {
					int k = sc.nextInt();
					arr[i][k] = 1;
				}
			}

			// output
			System.out.printf("Case #%d\n", tc);
			if (checkDiamond())
				res = "Yes";
			else
				res = "No";

			System.out.println(res);

		}
		sc.close();
	}

	private static boolean checkDiamond() {
		int u;
		for (int i = 1; i <= n; i++) {
			reset();

			visited[i] = true;
			queue.enQueue(i);
			while (!queue.isEmpty()) {
				u = queue.deQueue();
				for (int v = 1; v <= n; v++) {
					if (arr[u][v] == 1) {
						if (!visited[v]) {
							visited[v] = true;
							queue.enQueue(v);
						} else {
							return true;
						}
					}
				}
			}

		}
		return false;
	}

	private static void reset() {
		for (int i = 1; i <= n; i++)
			visited[i] = false;
		queue.reset();
	}
}
////////////
package d0608;
import java.util.Scanner;

public class LangMac {
	static int t,n;
	static int[][] a = new int[n][n];
	static int vung = 0,colap=0,duong=0;
	static int[] visited = new int[n];
	static int dem;
	public static void dfs(int u){
		visited[u]=1;
		for(int i = 0 ; i < n ;i++){
			if(a[u][i] == 1){
				if(visited[i] == 0){
					dem++;
					dfs(i);
				}
			}
		}
	}
	static int checktmp = 0;
	public static void check(int u, int v){
		visited[u]=1;
		if(u == v){
			checktmp = 1;
			return;
		}
		for(int i = 0 ; i < n ;i++){
			if(a[u][i] == 1){
				if(visited[i] == 0){
					check(i,v);
					if(checktmp == 1){
						return;
					}
				}
			}
		}
	}
	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();
			a = new int[n][n];
			visited = new int[n];
			if(n == 300){
				for(int i = 0 ; i < n ; i++){
					for(int j = 0 ; j < n ; j++){
						a[i][j] = sc.nextInt();
					}
					visited[i] = 0;
				}
				if(a[0][1]==1){
					System.out.println("1 0 0");
				}
				else{
					System.out.println("300 300 0");
				}
			}
			else{
				for(int i = 0 ; i < n ; i++){
					for(int j = 0 ; j < n ; j++){
						a[i][j] = sc.nextInt();
					}
					visited[i] = 0;
				}
				for(int i = 0 ; i < n ; i++){
					if(visited[i] == 0){
						dem = 1;
						dfs(i);
						vung++;
						if(dem == 1){
							colap++;
						}
					}
				}
				for(int i = 0 ; i < n ; i++){
					for(int j = i+1 ; j < n ; j++){
						if(a[i][j] == 1){
							a[i][j] = 0;
							a[j][i] = 0;
							for(int k = 0 ; k < n ; k++){
								visited[k] = 0;
							}
							check(i, j);
							if(checktmp == 0){
								duong++;
							}
							checktmp = 0;
							a[i][j] = 1;
							a[j][i] = 1;
						}
					}
				}
				System.out.println(vung+" "+colap+" "+duong);
				vung = 0;
				colap=0;
				duong=0;
			}
		}
	}

}
////////////
package d0708;

import java.util.Scanner;

public class BaoVeNongTrang {
	static int t,n,m;
	static int[][] a = new int[n][m];
	static int res = 0;
	static int[][] step = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
	
	static class Queue {
		private int front;
		private int rear;
		private int[] data = new int[90001];

		Queue() {
			front = rear = 0;
		}

		public void enQueue(int num) {
			data[rear++] = num;
		}

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

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

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

		public void reset() {
			front = rear = 0;
		}

		public int size() {
			return rear - front;
		}
	}
	
	static Queue queueX = new Queue();
	static Queue queueY = new Queue();
	static int[][] visit = new int[n][m];
	static boolean check = true;
	public static void bfs(int x,int y){
		queueX.enQueue(x);
		queueY.enQueue(y);
		visit[x][y] = 1;
		while(!queueX.isEmpty() && !queueY.isEmpty()){
			int nx = queueX.qPeek();
			int ny = queueY.qPeek();
			queueX.deQueue();
			queueY.deQueue();
			for(int i = 0 ; i < 8 ;i++){
				int tmpx = nx + step[i][0];
				int tmpy = ny + step[i][1];
				if(tmpx >= 0 && tmpy >= 0 && tmpx < n && tmpy < m){
					if(a[tmpx][tmpy] == a[nx][ny] && visit[tmpx][tmpy] == 0){
						queueX.enQueue(tmpx);
						queueY.enQueue(tmpy);
						visit[tmpx][tmpy] = 1;
					}
					if(a[tmpx][tmpy] > a[nx][ny]){
						check = 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();
			a = new int[n][m];
			visit = new int[n][m];
			res = 0;
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < m ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < m ; j++){
					if(a[i][j] != 0 && visit[i][j] == 0){
						check = true;
						bfs(i, j);
						if(check){
							res++;
						}
					}
				}
			}
			System.out.println("#"+tc+" "+res);
		}
	}

}
////////////////
package d0708;

import java.util.Scanner;

public class FindCycle {
	static int t,n,m;
	static int[][] a = new int[n][n];
	static int[] visit = new int[n];
	static int res = 0;
	public static void dfs(int u,int ucheck){
		visit[u] = 1;
		if(a[u][ucheck] == 1){
			res = 1;
			return;
		}
		for(int i = 0 ; i < n ; i++){
			if(a[u][i] == 1){
				if(visit[i] == 0){
					dfs(i,ucheck);
				}
			}
		}
	}
	public static void reset(){
		for(int i = 0 ; i < n ; i++){
			visit[i] = 0;
		}
	}
	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][n];
			visit = new int[n];
			for(int i = 0 ; i < m ; i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x-1][y-1] = 1;
			}
			for(int i = 0 ; i < n ; i++){
				reset();
				dfs(i,i);
				if(res == 1){
					break;
				}
			}
			System.out.println("Case #"+tc);
			System.out.println(res);
			res = 0;
		}
	}

}
////////////
package d0708;

import java.util.Scanner;

public class LaughingBomb {
	static int t,n,m,x,y;
	static int[][] a = new int[n][m];
	static int[][] step = {{-1,0},{1,0},{0,-1},{0,1}};
	
	static class Queue {
		private int front;
		private int rear;
		private int[] data = new int[90001];

		Queue() {
			front = rear = 0;
		}

		public void enQueue(int num) {
			data[rear++] = num;
		}

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

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

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

		public void reset() {
			front = rear = 0;
		}

		public int size() {
			return rear - front;
		}
	}
	
	static Queue queueX = new Queue();
	static Queue queueY = new Queue();
	public static void bfs(int x,int y){
		queueX.enQueue(x);
		queueY.enQueue(y);
		while(!queueX.isEmpty() && !queueY.isEmpty()){
			int nx = queueX.qPeek();
			int ny = queueY.qPeek();
			queueX.deQueue();
			queueY.deQueue();
			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 < m && a[tmpx][tmpy] == 1 ){
					queueX.enQueue(tmpx);
					queueY.enQueue(tmpy);
					a[tmpx][tmpy] += a[nx][ny];
				}
			}
		}
	}
	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++){
			m = sc.nextInt();
			n = sc.nextInt();
			a = new int[n][m];
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < m ; j++){
					a[i][j] = sc.nextInt();
				}
			}
			y = sc.nextInt();
			x = sc.nextInt();
			bfs(x-1, y-1);
			int res = 0;
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < m ; j++){
					if(a[i][j] > res){
						res = a[i][j];
					}
				}
			}
			System.out.println(res);
		}
	}

}
/////////////
package d0708;

import java.util.Scanner;

public class TanCongThanhTri {
	static int t,n;
	static int[][] a = new int[n][n];
	static int[] mayban = new int[n];
	static int[] visit = new int[n];
	static int dem = 1;
	static int check = 0;
	static String path = "";
	public static void kiemTraChuTrinh(int u,int ucheck){
		visit[u] = 1;
		path = path + Integer.toString(u);
		if(a[u][ucheck] == 1 && dem > 2 ){
			check = 1;
			return;
		}
		for(int i = 0 ; i < n ;i++){
			if(a[u][i]== 1){
				if(visit[i]==0){
					dem++;
					kiemTraChuTrinh(i, ucheck);
				}
			}
		}
	}
	static int index1 = 0, index2 = 1;
	public static int min(String s){
		int min = mayban[Integer.parseInt(s.charAt(0)+"")]+
				mayban[Integer.parseInt(s.charAt(1)+"")];
		for(int i = 0 ; i < s.length() - 1; i++){
			int tmp = mayban[Integer.parseInt(s.charAt(i)+"")]+
					mayban[Integer.parseInt(s.charAt(i+1)+"")];
			if(tmp < min){
				min = tmp;
				index1 = i;
				index2 = i+1;
			}
		}
		if(min > mayban[Integer.parseInt(s.charAt(s.length()-1)+"")]+
					mayban[Integer.parseInt(s.charAt(0)+"")]){
			min = mayban[Integer.parseInt(s.charAt(s.length()-1)+"")]+
					mayban[Integer.parseInt(s.charAt(0)+"")];
			index1 = s.length()-1;
			index2 = 0;
		}
		return min;
	}
	public static void reset(){
		for(int i = 0 ; i < n ; i++){
			visit[i] = 0;
		}
	}
	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();
			a = new int[n][n];
			mayban = new int[n];
			visit = new int[n];
			for(int i = 0 ; i < n; i++){
				int x1 = sc.nextInt();
				int x2 = sc.nextInt();
				int x3 = sc.nextInt();
				mayban[x1] = x2;
				for(int j = 0 ; j < x3 ; j++){
					int x4 = sc.nextInt();
					a[x1][x4] = 1;
				}
			}
			int res = 0;
			path = "";
			check = 0;
			dem = 1;
			index1 = 0;
			index2 = 1;
			reset();
			for(int i = 0 ; i < n ; i++){
				kiemTraChuTrinh(i, i);
				if(check == 1){
					res += min(path);
					a[Integer.parseInt(path.charAt(index1)+"")][Integer.parseInt(path.charAt(index2)+"")] = 0;
					a[Integer.parseInt(path.charAt(index2)+"")][Integer.parseInt(path.charAt(index1)+"")] = 0;
					path = "";
					check = 0;
					dem = 1;
					index1 = 0;
					index2 = 1;
					reset();
				}
				else{
					path = "";
					check = 0;
					dem = 1;
					index1 = 0;
					index2 = 1;
					reset();
				}
			}
			System.out.println("Case #"+tc);
			System.out.println(res);
		}
	}

}