Untitled

// Di an Cuoi
package Lesson_16;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution_Di_An_Cuoi {
	static int T, N, M;
	static int map[][], index[], sumNode;
	static int arrGo[], arrBack[];
	static boolean visited[];
	
	public static void backTrack_Back(int start, int countNode){
		if(countNode > sumNode) return;
		if(start == 1){
			if(countNode < sumNode) sumNode = countNode;
			return;
		}
		
		for(int i = 0; i <= index[start]; i++){
			int temp = map[start][i];
			if(arrBack[temp] == 1) continue;
			arrBack[temp] = 1;
			if(arrGo[temp] == 1){
				backTrack_Back(temp, countNode);
			}
			else backTrack_Back(temp, countNode+1);
			arrBack[temp] = 0;
		}
	}
	
	public static void backTrack_Go(int start, int countNode){
		if(countNode > sumNode) return;
		if(start == 2){
			backTrack_Back(2, countNode);
		}
		
		for(int i = 0; i <= index[start]; i++){
			int temp = map[start][i];
			if(arrGo[temp] == 1) continue;
			arrGo[temp] = 1;
			backTrack_Go(temp, countNode + 1);
			arrGo[temp] = 0;
		}
	}
	
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Di_An_Cuoi"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			N = scanner.nextInt();
			M = scanner.nextInt();
			map = new int[M+1][N+1];
			index = new int[N+1];
			for(int i = 0; i < M; i++){
				int value = scanner.nextInt();
				map[value][index[value]++] = scanner.nextInt();
			}
			
			arrGo = new int[N+1];
			arrBack = new int[N+1];
			arrGo[1] = 1;
			arrBack[2] = 1;
			sumNode = 123456789;
			backTrack_Go(1, 1);
			System.out.println(sumNode);
		}
	}
}

// Sum it up
package Lesson_17;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Sum_It_Up {
	static int T, sum, numbers;
	static int Arr[], count;
	
	public static void backTrack(int sumNumbers, int index){
		if(sumNumbers == sum){
			count++;
			return;
		}
		
		if(index == numbers)
			return;
		
		int last = -1;
		
		for(int i = index; i < numbers; i++){
			if(sumNumbers + Arr[i] > sum) continue;
			if(Arr[i] != last){
				last = Arr[i];
				backTrack(sumNumbers + Arr[i], i+1);
			}
		}
		
//		backTrack(sumNumbers + Arr[index], index+1);
//		
//		backTrack(sumNumbers, index +1);
		
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Sum_It_Up"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			sum = scanner.nextInt();
			numbers = scanner.nextInt();
			Arr = new int[numbers];
			for(int i = 0; i < numbers; i++){
				Arr[i] = scanner.nextInt();
			}
			
			count = 0;
			backTrack(0, 0);
			if(count == 0){
				System.out.println("#" + tc + " " + -1);
			}
			else
				System.out.println("#" + tc + " " + count);
		}
	}
	
}