public class prog_2_타겟넘버 {

	static int answer = 0;
	
	static public void dfs(int numbers[], int idx, int sum, int target) {
		//기저 조건
		if(idx == numbers.length) {
			if(sum == target)
				answer ++;
		}
		
		else if(idx<numbers.length) {
			dfs(numbers,idx+1, sum+numbers[idx], target);
			dfs(numbers,idx+1, sum-numbers[idx], target);
		}
		
	}
	
	
	static public int solution(int[] numbers, int target) {
		
		dfs(numbers,0,0,target);
		
		return answer;
	}
	
	public static void main(String[] args) {
		int n[] = {1,1,1,1,1}; int target = 3;
		
		System.out.println(solution(n,target));
	}
}

	//시간 초과........!! (답은 맞음)
	static public int fib(int n) {
		int answer = 0;

		if(n == 0)
			return 0;
		
		if(n == 1)
			return 1;
		
		answer = fib(n-1)%1234567 + fib(n-2)%1234567;
		
		return answer %1234567;
	}
	
	
	  static public int solution(int n) {
	      int answer = 0;
	      
	      if(n == 1)
	    	  return 1;
	      
	      int a = 0; // n-1 값 넣기
	      int b = 1; // n-2 값 넣기
	      
	      for(int i=2; i<=n; i++) {

	    	  answer = a + b;
	    	  
	    	  a = b% 1234567;
	    	  b = answer% 1234567;
	      } // a= b; b = a+b; 를 하니까 b = b+b 가 되었는데.. 그것도 모르고 계속 저렇게 함...
	      
	      return answer % 1234567;
	  }
	
	public static void main(String[] args) {
		System.out.println(solution(3));
		System.out.println(fib(3));
	}

    static public int[] solution(int[] progresses, int[] speeds) {
    	
    	LinkedList<Integer> list = new LinkedList<Integer>();
    	Queue<Integer> qu = new LinkedList<Integer>();
    	int idx = 0;
    	int day = 0;
    	
    	
    	for(int i=0; i<progresses.length; i++)
    		qu.offer(progresses[i]);
    	
    	while(!qu.isEmpty()) {
    		day++;
    		
    		int answer = 0;

    		
    		while(!qu.isEmpty() && qu.peek() + speeds[idx]*day >=100){
    			answer++;
    			idx++;
    			qu.poll();

    		}
    		
    		if(answer != 0)
    			list.add(answer);
    		
    	}//while
    	
    	return list.stream().mapToInt(i->i).toArray();
    }

package Dfs_Bfs;

import java.util.*;

public class beak_Dfs와Bfs {
	
	public static void dfs(int arr[][], boolean check[], int v) {
		check[v] = true;
		
		System.out.print(v + " ");
		
		for(int i=1;i<arr.length;i++) {
				if(i==v)
					continue;
				
				if(arr[v][i] == 1 && check[i] == false) {
					//1. check[i] = true; 두번 걸어주면 안된다
					dfs(arr, check, i);
				}
		}//for
		
	}
	
	public static void bfs(int arr[][], int v) {
		Queue<Integer> qu = new LinkedList<Integer>();
		boolean check[] = new boolean[arr.length+1]; // false로 초기화
		
		qu.offer(v);
		check[v] = true;
		
		while(!qu.isEmpty()) {
			int x = qu.poll();
			
			System.out.print(x + " ");
			
			for(int i=1;i<arr.length; i++) {
				if(i == x)
					continue;

				if(arr[x][i] == 1 && check[i]== false) {
					qu.offer(i);
					check[i] = true;
				}
			}//for
			
		}//while
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); // n*n 행렬
		int m = sc.nextInt(); //몇개의 간선이 연결되어 있는지
		int v = sc.nextInt(); //몇번째 행부터 시작할건지
		
		int arr[][] = new int[n+1][n+1];
		
        //2
		for(int i=0; i<m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			arr[a][b]=1;
			arr[b][a]=1;
		}
			
		boolean check[] = new boolean[arr.length+1]; // false로 초기화
		
		dfs(arr, check, v);
		System.out.println("");
		bfs(arr, v);
	}
}

    static public int solution(int board[][]){
        int arr[][] = new int[board.length+1][board[0].length+1];
    	int answer = 0;
        
    	for(int i=1;i<arr.length; i++) {
    		for(int j=1; j<arr[0].length; j++){
    			if(board[i-1][j-1] == 1)
    				arr[i][j] = 1;
    		}
    	}
    	
        for(int i=1; i<arr.length; i++) {
        	for(int j=1; j<arr[0].length; j++) {
        		if(arr[i][j]==1) {
        			int min = Math.min(arr[i-1][j], Math.min(arr[i][j-1], arr[i-1][j-1]));
        			arr[i][j] = min+1;
        			answer = Math.max(answer, arr[i][j]);
        		}
        	}	
        }
        
        return answer * answer;
    }

static public int doRight(int b[][], int i, int j) {
	int r=0;
	for(int k = j; k<b[0].length; k++) {
		if(b[i][k] == 1)
			r++;
		else
			break;
	}

	return r;
}

static public int doDown(int b[][],int i, int j){
	int d=1;
	for(int k = i; k<b.length; k++) {
		if(b[k][j] == 1)
			d++;
		else
			break;
	}		
	
	return d;
}

static public int solution(int board[][]){
    //board의 각 값마다 Point r과 d 생성
    int answer = 0;
    
    for(int i=0;i<board.length; i++) {
    	for(int j=0;j<board[0].length; j++) {
    		if(board[i][j] == 0)
    			continue;
    		
    		int right = doRight(board,i,j);
    		int down = doDown(board,i,j);
    		
        	if(right == down)
        		answer = Math.max(answer, right*down);
    	}
    	
    }
    
    return answer;
}