for(int i=1; i<= N; i++) // inddegree 0 인 노드 큐에 삽입
		{
			if(degree[i] == 0) que.add(i); 
		}
		solve();
		if(!flag) // 사이클 발생 안한 경우 
		{
			for(int i=0; i< temp.size(); i++)
			{
				System.out.println(temp.get(i));
			}
		}
		
	}
	public static void solve()
	{
		for(int i=0; i< N; i++)
		{
			if(que.isEmpty()) // N 번 돌지 못하고 끝이 나는 것은 사이클 발생 
			{
				System.out.println(0);
				flag = true;
				return;
			}
			
			int n = que.poll();
			
			temp.add(n);
			
			for(int next : adj.get(n))
			{
				degree[next]--;         //연결된 노드 indegree --
				if(degree[next] == 0) // indegree 0 인 노드는 큐에 삽입 
				{
					que.add(next);
				}
			}
		}
	}

정점 A가 루트라면
==> 자식 수가 2개 이상이면 단절짐이다.
정점 A가 루트가 아니라면
==> A번 정점에서 자식 노드들이 정점 A를 거치지 않고 정점 A보다 빠른 방문번호를 가진 정점으로 갈 수 없다면 단절점

==>한번의 dfs 로 답을 구할수 있기 때문에 O(N + M) 

public class baek11266 {

	static int V, E, number;
	static boolean[] cut = new boolean[10005]; // 단절점 여부 확인 배열 ! 
	static int[] order = new int[10005]; // 방문 순서 기록 !! 
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException {
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		number =0; // 방문 순서 기록 할 숫자 

		for(int i=1; i<= V; i++)
		{
			if(order[i] > 0) continue;
			dfs(i, 0);
		}
		
		int cnt =0;
		for(int i=1; i<= V; i++)
		{
			if(cut[i]) cnt++;
		}
		bw.write(cnt+"\n");
		for(int i=1; i<= V; i++)
		{
			if(cut[i]) 
			{
				bw.write(i+" ");
			}
		}
		bw.flush();
	}
	public static int dfs(int cur, int p)
	{
		order[cur] = ++number; // 방문순서 지정 
		int ret = order[cur];
		int child = 0; // root 자식 수가 2개 확인하기 위함 
		for(int next : adj.get(cur))
		{
                         if( next == p ) continue;
			if(order[next] > 0) // 이미 방문한 지점이라면 가장 작은 순서 찾아서 업데이트 
			{
				ret = min(ret, order[next]);
				continue;
			}
			
			child++;
			
			int prev = dfs(next, cur);
			
			if(p != 0 && prev >= order[cur]) {
				cut[cur] = true; // 단절점 
			}
			ret = min(ret, prev);
		}
		
		if(p ==0 && child >= 2) cut[cur] = true;
		
		return ret;
	}
}

public class Main {

	static int N, K, number;
	static int[] order = new int[100005];
	static ArrayList<Node> result = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException {
		
		for(int i=1; i<= N; i++)
		{
			if(order[i] > 0) continue;
			dfs(i, 0);
		}
	}
	public static int dfs(int cur, int p)
	{
		order[cur] = ++number;
		int ret = order[cur];
		
		for(int next : adj.get(cur))
		{
			if(next == p) continue;
			
			if(order[next] > 0)
			{
				ret = min(ret, order[next]);
				continue;
			}
			
			int prev = dfs(next, cur);
			
			if(prev > order[cur])
			{
				result.add(new Node(min(cur, next), max(cur, next)));
			}
			
			ret = min(prev, ret);
		}
		
		return ret;
	}
}

public static int[][] map = new int[1002][1002]; // 인접 행렬
public static int[] visited = new int[1002]; // 방문 기록 
public static void dfs(int v) {
	
	if(visited[v] == 1 ) return; // base case 
	visited[v] = 1; // 방문 체크
	System.out.print(v+" ");
	for(int i= 1; i<= V ; i++) {
		if(map[v][i] == 1) { 
			dfs(i); //  다음 노드로 이동
		}
	}
	
}
public static void bfs(int v) {
	Queue<Integer> que = new LinkedList<Integer>();
	que.add(v); // 시작점 
	visited[v]=1;
	
	while(!que.isEmpty()) {
		int num = que.peek();
		System.out.print(num+" ");
		que.poll();
		
		for(int i= 1; i<= V ; i++) {
			if(map[num][i] == 1 && visited[i] == 0) { // 방문 기록이 없다면
				visited[i] = 1;
				que.add(i);
			}
		}
	}
}

public static int ccw(Point a, Point b, Point c)
{
	long op = ( (a.dx*b.dy)+(b.dx*c.dy)+(c.dx*a.dy) - (a.dy*b.dx) + (b.dy*c.dx)+(c.dy*a.dx) );
	if(op > 0) return 1; // 반시계 방향
	else if(op < 0) return -1; // 시계 방향
	else return 0; // 세점이 평행
}

1) 점 B의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다.
2) 점 B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점 B의 좌표보다 크다.

public static boolean isCross(long tx, long ty)
{
	int crossCnt = 0;
	long mindy =0, maxdy =0;
	for(int i=0; i< N; i++)
	{
		Point p1 = p[i];
		Point p2 = p[(i+1) % N];
			
		mindy = min(p1.dy, p2.dy);
		maxdy = max(p1.dy, p2.dy);
			
		if(mindy <= ty && maxdy >= ty) // 선분 y 좌표 사이에 있는지 확인 
		{
				 
			long tmp = p2.dy - p1.dy; // 분모가 0 일 경우 제외 
			if(tmp == 0) continue;
			// 점과 직선사이의 수선의 발 좌표 공식
			long target = (ty - p1.dy)*(p2.dx - p1.dx) / (p2.dy - p1.dy) + p1.dx;
				
			if(tx < target) crossCnt++;
		}
	}
	if(crossCnt % 2 != 0) return true;
	else return false;
}

public class baek10272 {

	static final double INF = 2e9;
	static int N;
	static double[][] point = new double[550][2];
	static double[][] dp = new double[550][550]; 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int testCase = Integer.parseInt(st.nextToken());
		for(int n=1; n <= testCase; n++)
		{
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			int dx =0, dy =0;
			for(int i=1; i<= N; i++)
			{
				st = new StringTokenizer(br.readLine());
				dx = Integer.parseInt(st.nextToken());
				dy = Integer.parseInt(st.nextToken());
				point[i][0] = dx; point[i][1] = dy;
				for(int j=1; j<= N; j++)
				{
					dp[i][j] = INF;
				}
			}
			
			dp[1][1] = 0; // 똑같은점 있음 안됨 
			dp[1][2] = dis(1,2); // i < j 처음 이동시켜 놓고 시작 
			for(int i=1; i < N; i++)
			{
				for(int j = i+1; j < N; j++) // 1 ~ N-1 까지 이동 
				{
					int k = j + 1; // k : 다음 방문할 곳 / 
					// i에서 이동할 경우 => dp[k][j] = dis(i,k) + dp[i][j]
					// j에서 이동할 경우 => dp[i][k] = dis(j,k) + dp[i][j]
					dp[j][k] = min(dp[j][k], dis(i,k) + dp[i][j]);
					dp[i][k] = min(dp[i][k], dis(j,k) + dp[i][j]);
				}
			}
			double ans = INF;
			for(int i=1; i < N; i++) // N-1 ~ 에서 N 
			{
				ans = min(ans, dp[i][N] + dis(i,N));
			}
			System.out.println(ans);
		}
	}
	public static double min(double a, double b) { return a > b ? b : a; }
	public static double dis(int a, int b)
	{
		return Math.sqrt( (point[a][0]-point[b][0])*(point[a][0]-point[b][0]) + (point[a][1]-point[b][1])*(point[a][1]-point[b][1]) );
	}
}

for(int i = 0; i < N-1; i++)
{
	int min = i;  
	for(int j = i + 1; j < N; j++)
	{
	      if(data[min] > data[j]) min = j; // 가장 작은 값 찾아가기
	}
	int temp = data[min];  // 두번째 for 문이 끝난 후 가장 작은 값과 i 를 swap
	data[min] = data[i];
	data[i] = temp;
}

int j=0;
for(int i=1; i< N; i++) // 두번째 인덱스 부터 시작 
{
	j= i -1;
	int target = data[i]; // 삽입할 숫자 
	while(j >= 0 && data[j] > target) // target 위치 찾기 
	{
		data[j+1] = data[j]; // target 보다 큰 숫자 앞으로 한칸 씩 당기기 
		j--;
	}
	data[j+1] = target; // 자리 삽입 
}

for(int i=0; i< N-1; i++)
{	
	for(int j = 0; j< N - i -1; j++)
	{
		if(data[j] > data[j+1])
		{
			int temp = data[j];
			data[j] = data[j+1];
			data[j+1] = temp;
		}
	}
}

public class quickSort {
	static int N;
	static int[] data = new int[1000005];
	public static void main(String[] args) throws IOException {
		qSort(0, N-1);
	}
	public static void qSort(int left, int right)
	{
		if(left >= right) return;
		
		int pivot = partition(left, right);
		qSort(left, pivot-1);
		qSort(pivot+1, right);
	}
	public static int partition(int left, int right) // pivot 
	{
	    int mid = (left + right) / 2;            ////////// 중요!!! 중간값과 처음값 swap
            swap(left, mid);                   ////////// 이 과정이 있어야 n^2 피할수 있다
		
		int j = left ; // 처음은 pivot 의 위치 ! 
		int pivot = data[left];
		for(int i= left+1; i<= right; i++)
		{
			if(data[i] < pivot) 
			{
			      j++; // 왼쪽에는 pivot 보다 작은 값들로 바뀌게 됨 !
                              swap(i, j);
			}
		}
                swap(j, left);
		
		return j;
	}
}

public class mergeSort {
	static int N;
	static int[] data = new int[1000005];
	static int[] temp = new int[1000005];
	public static void main(String[] args) throws IOException {
		mSort(0, N-1);
	}
	public static void mSort(int left, int right)
	{
		if(left == right) return;
		
		int mid = (left + right) / 2;
		mSort(left, mid);
		mSort(mid+1, right);
		merge(left, mid, right);
	}
	public static void merge(int left,int mid, int right)
	{
		for(int i= left; i<= right; i++)
			temp[i] = data[i];
		
		int i, j, k; 
		i = k = left; //temp 첫번째  시작 인덱스 i, data 시작 인덱스 k 
		j= mid+1; // temp 두번째 시작 인덱스 k
		
		while(i<= mid && j <= right)
		{
			if(temp[i] <= temp[j]) data[k++] = temp[i++];
			else data[k++] = temp[j++];
		}
		
		// 남은 배열은 그대로 넣기 
		while(i<= mid)
			data[k++] = temp[i++];
		while(j <= right)
			data[k++] = temp[j++];
		
	}
}

public class heapSort {

	static int N;
	static int[] data = new int[1000005];
	public static void main(String[] args) throws IOException {
		hSort(N);
	}
	public static void hSort(int n)
	{
		for(int i = n/2; i >=1; i--) // 자식을 가진 부모를 뒤에서 부터 업데이트 ! ( 처음 힙 만들기 !)
		{
			heapify(n, i);
		}
		
		for(int i= n; i>=2 ; i--)
		{
			swap(1, i); // 정렬된 가장 큰 값을 맨뒤 요소와 swap 
			heapify(i-1, 1); // 1 번부터 다시 힙 정렬 / 이때 전체 n 범위를 하나씩 줄여나감 ! 
		}
		
	}
	public static void heapify(int n, int i) // 힙 속성에 맞게 구성 
	{
		int p, left, right;
		p = i; // 노드의 자식노드들 중 큰 값을 올리기 위한 부모노드 인덱스 설정 
		left = i*2; // 왼쪽 자식
		right = i*2 +1; // 오른쪽 자식
		
		if(left <= n && data[p] < data[left]) p = left; // 두 자식들 중 큰 값 찾기 
		if(right <= n && data[p] < data[right]) p = right;
		
		if(p != i) // 값이 다르다는 얘기는 두 자식들 중 부모노드보다 큰값이 있어서 업데이트 필요하단 얘기 
		{
			swap(p, i);
			heapify(n, p); // 바뀐 값 자식들도 내려가면서 확인하기 위해 재귀 
		}
	}
	public static void swap(int a, int b)
	{
		int temp = data[a];
		data[a] = data[b];
		data[b] = temp;
		
	}
}

s = 1
while(N > s) s *=2; 
==> N이 10일땐 시작인덱스 16   ( 1 , 2 ,4 ,8 , 16 )

public class baek11375 {

	static int N, M, result;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
	static int[] visit = new int[1005];
	static int[] match = new int[1005];
	public static void main(String[] args) throws IOException {
		
		int result = bmatch();
		System.out.println(result);
	}
	public static int bmatch()
	{
		int ret = 0;
		for(int i=1; i<= N; i++) // 모든 직원들에 대해서 매칭 시도 
		{
			for(int j=1; j<= N; j++) visit[j] = 0;
			if(dfs(i) == 1) ret++; // 직원과 일이 매칭 된다면 카운트 
		}
		return ret;
	}
	public static int dfs(int cur)
	{
		if(visit[cur] == 1) return 0; // 방문한 직원 매칭 불가 
		visit[cur] = 1;
		
		for(int next : adj.get(cur))
		{
			// 매칭한 적이 없거나 매칭 되어 있다면 매칭 된 직원에게 되돌아 가서 다른 일이 가능한지 확인 작업 
			if(match[next] == 0 || dfs(match[next]) == 1)
			{
				match[next] = cur; // 매칭이 된다면 1 리턴 
				return 1;
			}
		}
		
		return 0;
	}
}

public static int bmatch()
{
	int ret =0;
	
	for(int i=1; i<= N; i++)
	{
		for(int j=1; j<= 2; j++)
		{
			for(int k=1; k<= N; k++) visit[k] = 0;
			if(dfs(i) == 1) ret++;
		}
		
	}
	return ret;
}

public static int bmatch()
{
	int ret = 0, count = 0;
	
	for(int i=1; i<= N; i++)
	{
		for(int j=1; j<= N; j++) visit[j] = 0;
		if(dfs(i) == 1) ret++;
	}
	
	for(int i=1; i<= N; i++)
	{
		for(int j=1; j<= N; j++) visit[j] = 0;
		if(dfs(i) == 1) {
			ret++;
			count++;
		}
		if(count == K) break;
	}
	return ret;
}

for(int i=1; i<= N; i++)
{
	num = Integer.parseInt(st.nextToken());
	data[i] = num;
			
	Node first = null, last = null;
	while(!que.isEmpty()) // 조건 만족할때 가지 데크 뒤 빼기 ////////빼는 구간 
	{
		last = que.peekLast();
				
		if(last.num >= num) que.pollLast();
		else break;
	}
	que.addLast(new Node(num, i));
			
	int target = 0;
	while(!que.isEmpty()) ///////////////////////////////// 넣는 구간
	{
		first = que.peekFirst();
		last = que.peekLast();
				
		target = first.num;
		if(last.idx - first.idx < X)
		{
			break;
		}
		que.pollFirst();
	}
}

static int V, E, S;  // 정점의 갯수, 간선의 갯수,시작 점 
static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>(); // 인접 리스트
static final int MAX = 20001, INF = 300005 * 10;
static int[] dis = new int[MAX];

// 인접 리스트 정점 갯수만큼 할당 해주고 인접리스트 연결 할 것 
// dis 배열 모두 INF 로 초기화 해주고 시작점 0으로 놓고 시작 !
public static void solve()
{
	PriorityQueue<Node> que = new PriorityQueue<>(new Mysort());
	que.add(new Node(S,0)); // 시작점 
	dis[S] = 0;
	
	while(!que.isEmpty())
	{
		Node n = que.poll();
		
		if(n.cost > dis[n.dx]) continue;
		
		for(Node next : adj.get(n.dx)) // 연결된 다음 노드들을 보면서 최단경로 탐색 
		{
			// 현재 노드에서 다음 노드로 가는 가중치를 더한 값이 dis[next.dx] 보다 작으면 그 경로가 최단 경로가 되니 업데이트 
			if(dis[next.dx] > next.cost + dis[n.dx])  
			{
				dis[next.dx] = next.cost + dis[n.dx];
				que.add(new Node(next.dx, dis[next.dx]));
			}
		}
	}
}

/**
 * 타임머신 (벨만 포드 알고리즘 ) : V개의 정점과 E개의 간선을 가진 가중 그래프에서
 * 출발정점에서 다른 모든 정점까지의 치단경로를 구하는 알고리즘
 * 최소 간선의 갯수 V-1 ==> 즉, V번째 모든 간선을 확인하였을때 거래배열이 갱신된다면 음수 사이클 확인 가능하다 
 * O(V*E)
 *
 */
public class Main {

	static int N, M;
	static int[][] data = new int[6001][3]; // input 간선 표 
	static int[] d = new int[501]; // cost 정보 배열 
	static final int INF = 6005*10000; 
	public static void main(String[] args) throws IOException {
		int dx,dy,cost;
		for(int i=1; i<= M; i++)
		{
			data[i][0] = dx; data[i][1] = dy; data[i][2] = cost; 
		}
		
		for(int i=1; i<= N; i++)
		{
			d[i] = INF;
		}
		d[1] = 0; // 1번 도시에서 출발 
		for(int i=1; i<= N-1; i++) // 사이클 없이 모든 노드를 연결할수 있는 최소 간선의 갯수 N-1 
		{
			for(int j=1; j<= M; j++) // 모든 간선 표 확인 
			{
				if(d[data[j][0]] != INF && d[data[j][1]] > d[data[j][0]]+ data[j][2]) 
				{
					d[data[j][1]] = d[data[j][0]]+ data[j][2]; // 더 적은 비용으로 이동할수 있는 거리 찾음 
				}
			}
		}
		
		for(int j=1; j<= M; j++) // 사이클이 존재하는지 존재 하는 방법 !  
		{
			if(d[data[j][0]] != INF && d[data[j][1]] > d[data[j][0]]+ data[j][2]) 
			{
				System.out.println(-1);
				return; // 바로 종료 
			}
		}
		
		for(int i=2; i<= N; i++)
		{
			if(d[i] == INF) System.out.println(-1);
			else System.out.println(d[i]);
		}
	}
}

for(int i=1; i<= N; i++)
{
	for(int j=0; j < i; j++)
	{
		if(data[i] > data[j] && dp[i] < dp[j] + 1)
		{
			dp[i] = dp[j] + 1;
		}
	}
	result = max(result, dp[i]);
}
System.out.println(result);

size = 1;
dp[1] = data[1];
for(int i=2; i<= N; i++)
{
	if(data[i] > dp[size]) // dp 맨뒤에 있는 자리와 비교하여 더 큰값이면 이어 붙이기  
	{
		dp[++size] = data[i];
	}
	else if(data[i] < dp[size])
	{
		int tdx = lower_bound(1,size,data[i]);
		dp[tdx] = data[i];
		}
	}
}
System.out.println(size);

public class baek14002 {

	static int N;
	static int[] data = new int[1005];
	static int[] dp = new int[1005];
	static Node[] ans = new Node[1005];
	static Deque<Integer> que = new ArrayDeque<>();
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<= N; i++)
		{
			data[i] = Integer.parseInt(st.nextToken());
			ans[i] = new Node(-1,-1);
		}
		
		dp[1] = data[1];
		ans[1].dx = 1; // 실제 인덱스 1로 처음 시작 
		ans[1].dy = dp[1]; // 실제 값 
		int size = 1;
		for(int i=2; i<= N; i++)
		{
			if(dp[size] < data[i])
			{
				dp[++size] = data[i];
				ans[i].dx = size;
				ans[i].dy = data[i];
			}
			else {
				int idx = lower_bound(1, size, data[i]);
				dp[idx] = data[i];
				ans[i].dx = idx;
				ans[i].dy = data[i];
			}
		}
		System.out.println(size);
		// 인덱스 i=2 부터 계속 해서 업데이트 해왔으므로
		// 맨뒤 인덱스 부터 찾아 나감 
		int t = size;
		for(int i = N; i > 0; i--)
		{
			if(t == ans[i].dx)
			{
				que.addLast(ans[i].dy);
				t--;
			}
		}
		
		while(!que.isEmpty())
		{
			int num = que.pollLast();
			System.out.print(num+" ");
		}
	}
	static class Node {
		int dx, dy;
		Node(int a, int b) {
			dx=a; dy=b;
		}
	}
}

public class Main {

	static int N, start, result;
	static final int max_node = 500005;
	static ArrayList<Node> arr = new ArrayList<>();
	static int[] tree = new int[4*max_node];
	static int[] dp = new int[max_node];
	static Deque<Integer> que = new ArrayDeque<>();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		N = Integer.parseInt(st.nextToken());
		start = 1; result = 0;
		int chk = 0; // 트리의 시작 인덱스를 찾기 위한 최대 노드 값 
		
		int dx = 0, dy = 0;
		for(int i=1; i<= N; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			arr.add(new Node(dy,dx));
			chk = max(chk, dx);
		}
		
		while(chk > start) start *= 2;
		Collections.sort(arr, new mySort());
		
		for(Node cur : arr)
		{
			int cnt = query(1, cur.idx); // 1 ~ i-1 까지의 최대 lis 
			update(cur.idx, cnt+1);
			result = max(result, cnt+1);
			dp[cur.idx] = cnt+1;
		}
		bw.write( (N-result) +"\n");
		int size = result;
		for(int i = chk; i > 0; i--)
		{
			if(dp[i] == 0) continue;
			if(dp[i] == size) {
				size--;
				continue;
			}
			que.addLast(i);
		}
		while(!que.isEmpty())
		{
			int num = que.pollLast();
			bw.write(num+"\n");
		}
		bw.flush();
	}
	public static void update(int idx, int num)
	{
		int s = start + idx - 1;
		
		while(s > 0)
		{
			if(tree[s] < num)
			{
				tree[s] = num;
				s /= 2;
			}
			else break;
		}
	}
	public static int query(int sdx, int edx)
	{
		int ret = 0;
		int s = start + sdx - 1;
		int e = start + edx - 1;
		
		while(s <= e)
		{
			if(s % 2 == 1)
			{
				if( ret < tree[s])
				{
					ret = tree[s];
				}
			}
			
			if(e % 2 == 0)
			{
				if( ret < tree[e])
				{
					ret = tree[e];
				}
			}
			
			s = (s+1) / 2;
			e = (e-1) / 2;
		}
		return ret;
	}
	public static int max(int a, int b)
	{
		return a > b ? a : b;
	}
	static class mySort implements Comparator<Node>{ // 값에 대한 오름차순으로 정렬 하고 동일한 값이 있을 때는 인덱스가 큰 값 기준으로 내림 차순 정렬 
		@Override
		public int compare(Node a, Node b) {
			// TODO Auto-generated method stub
			if(a.num < b.num) return -1;
			else if(a.num > b.num) return 1;
			else {
				if(a.idx > b.idx) return -1;
				else if(a.idx < b.idx) return 1;
				else return 0;
			}
		}
	}
	static class Node {
		int num, idx;
		Node(int a, int b){
			num=a; idx=b;
		}
	}
}

public static long pow(long a, long b)
{
	long k =0;
	if ( b == 0 ) return 1;
		
	else if(b % 2 == 0) { // 거듭제곱이 짝수일 때 
		k = pow(a, b/2);
		return (k * k) ;
	}
	else {                         // 거듭제곱이 홀수일 때
		k = pow(a, (b-1)/2);
		return (a * k *k) ;
	}
}

package com.company.etc;

class NodeList {
	private Node head; // 맨 처음 
	private Node tail; // 맨 끝 
	private int size; // 노드 갯수 
	
	private class Node{
		int data;
		Node next; // 노드의 다음 노드를 가르킴 
		
		public Node(int data)
		{
			this.data = data;
		}
	}
	
	public void addFirst(int data) // 맨 앞 노드 추가 
	{
		Node newNode = new Node(data); // 노드 생성 
		
		newNode.next = head; // 새로 만든 노드를 이전에 헤드 였던에랑 연결!!!
		
		head = newNode; // haed가 새로 만들어진 노드를 가르키도록 ! 
		
		if(head.next == null)
		{
			tail = head; // 현재 노드가 하나밖에 없어서 head 의 다음이 없다면 그곳이 tail 자리도 되니까 
		}
		
		size++;
	}
	public void addLast(int data)
	{
		Node newNode = new Node(data);
		
		if(size == 0) {
			addFirst(data);
		}
		
		tail.next = newNode; // 이전 tail 의 노드 값과 새로운 노드 연결 
		tail = newNode; // tail 을 새로운 노드로 갱신 
		size++;
	}
	public Node node(int index) // 특정 인덱스 노드 찾아가기 
	{
		Node target = head;
		for(int i=0; i< index; i++)
		{
			target = target.next;
		}
		return target;
	}
	public void add(int index, int data) // 특정 인덱스 노드에 삽입 
	{
		if(size ==0) {
			addFirst(data);
		}
		else 
		{
			Node preNode = node(index-1); // 그전 노드 가져오기 
			Node nextNode = preNode.next; // 그 다음 노드 가져오기 
			
			Node newNode = new Node(data); // 중간에 삽입할 노드 
			preNode.next = newNode; // 이전 노드랑 연결 
			newNode.next = nextNode; // 새로만든 노드를 다음 노드와 연결 
			size++;
			
			if(newNode.next == null ) // 다음 노드가 없다는건 해당 노드가 끝 이니까 tail 로 갱신 
			{
				tail = newNode;
			}
		}
	}
	public int removeFirst() { // 가지고 있던 데이터 리턴이 원칙 
		
		Node temp = head; // 헤드가 가르키고 있는 첫번째 값을 임시로 저장 (삭제전)
		
		head = temp.next; // 헤드를 다음 노드를 가르키게 
		
		int deleteDate = temp.data; // 삭제 시킬 데이터 
		temp = null; // 삭제 
		
		size--;
		
		return deleteDate;
	}
	public int remove(int k) {
		
		if(k ==0) {
			return removeFirst();
		}
		Node temp = node(k-1); // 삭제시킬 바로 이전 노드 가져오기 
		
		Node todoDelete = temp.next; // 삭제할 노드 
		
		temp.next = temp.next.next; // 삭제 할 노드 다음 노드 
		
		int returnData = todoDelete.data;
		
		if(todoDelete == tail)
		{
			tail = temp; // 이전 노드로 갱신 
		}
		
		size--;
		todoDelete = null;
		return returnData;
	}
	public int removeLast()
	{
		return remove(size-1);
	}
	public String toString() {
		
		if(head == null) {
			return "[ ]";
		}
		
		Node temp = head;
		
		String str ="[";
		
		while(temp.next != null)
		{
			str += temp.data + ",";
			temp = temp.next;
		}
		str += temp.data;
		return str+"]";
	}
}

public class LinkedList {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		NodeList list = new NodeList();
		list.addFirst(10);
		list.addFirst(20);
		list.addLast(30);
		System.out.println(list.removeFirst());
		System.out.println(list);
	}

}

value = scanner.nextInt();
int i;
for(i=2 ;i< value; i++)
{
	if( value % i == 0) break; // 소수 아님
}
if(i == value) // 소수!

	public static int isPrime(int value) {
		if(value <= 1) return 0;
		
		for(int i=2; i * i <= value ; i++)
		{
			if(value % i ==0) return 0;
		}
		return 1;
	}

for(int i =2; i<= 1000000; i++)
{
	if(map[i] == 0 ) continue;
	isPrime[index++] = i;
	for(int j= i+i; j<= 1000000; j += i)
	{
		if(map[j] ==0) continue;
		map[j] = 0;
	}
}

public static int N;
	public static int[] arr = new int[1000001];
	public static int start, end;
	public static void isPrime() { // 소수 판별 함수  
		for(int i =2; i * i<= end; i++) {
			if( arr[i] == 0 ) continue;
			for(int j = i+i; j<= end; j+=i) {
				arr[j] =0;
			}
		}
	}
	public static void init() {
		for(int i = 2; i<=end; i++) {
			arr[i] =i;
		}
	}

public class Shift {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int number =1; // 0000 0001
		System.out.println("원래 숫자 : "+ number); // 1 출력  
		
		number = number << 1; // 0000 0010
		System.out.println("왼쪽으로 1칸 쉬프트 : "+ number);// 2 출력  
		
		number = number << 2; // 0000 1000
		System.out.println("왼쪽으로 2칸 쉬프트 : "+ number);// 8 출력  
		
		number = number >> 1; // 0000 0100
		System.out.println("오른쪽으로 1칸 쉬프트 : "+ number);// 4출력  	
	}
}

public class Subset {
	
	public static int[] arr = {1,2,3};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int N = arr.length; // 배열 전체 길이  
		for(int i=0; i< (1 << N); i++) // 0 ~ 7 
		{
			for(int j=0; j < N; j++) // 원소의 갯수만큼 for문 
			{
				if( ( i&(1<<j) ) != 0 )// i의 j 번째 bit가 1인지 아닌지 확인
				{
					System.out.print(arr[j]+" ");
				}
			}
			System.out.println();
		}
	}
}
출력 결과 
(공집합)
1
2
1 2
3
1 3
2 3
1 2 3

static class Node {
		int dx, dy;
		Node(int a, int b) {
			dx=a; dy=b;
		}
		
		@Override
		public boolean equals(Object obj) {
			if(obj instanceof Node) {
				Node n = (Node)obj;
				if(dx == n.dx && dy == n.dy) return true;
			}
			return false;
		}
		@Override
		public int hashCode() {
			// TODO Auto-generated method stub
			return Objects.hash(dx,dy);
		}
	}

static class Node {
		int dx;
		Node(int a) {
			dx=a;
		}
		
		@Override
		public boolean equals(Object obj) {
			if(obj instanceof Node) {
				Node n = (Node)obj;
				if(dx == n.dx ) return true;
			}
			return false;
		}
		@Override
		public int hashCode() {
			// TODO Auto-generated method stub
			return dx;
		}
	}

최대 공약수는 a , b 둘 다 나누어떨어질수 있는 수 중에서 가장 큰 값이므로 1 ~ min(a,b)
를 전부 for 문 돌며 확인 하는 방법

여기서 시간을 조금더 줄이려면 for 문을 1부터 말고 뒤에서 부터 돌리게 된다면 가장 처음 발견 한
수가 최대 공약수!

하지만 서로서인 경우는 어차피 끝까지 가야하므로 똑같은 시간 복잡도

for(int i=1; i<= N; i++) // base case
{
	sn[i] = s.charAt(i-1);
	L[i][0] = 0;
}
for(int i=1; i<= M; i++) // base case 
{
	tm[i] = t.charAt(i-1);
	L[0][i] = 0;
}
for(int i=1; i<= N; i++)
{
	for(int j=1; j<= M; j++)
	{
		if(sn[i] == tm[j]) // 같다면 
		{
			L[i][j] = L[i-1][j-1] + 1;
		}
		else // 다르다면 둘중 큰값으로 
		{
			L[i][j] = max(L[i-1][j], L[i][j-1]);
		}
	}
}
System.out.println(L[N][M]);

public class baek9252 {

	static int N, M;
	static char[] sn = new char[4005];
	static char[] tm = new char[4005];
	static String s, t, result;
	static int[][] L = new int[4005][4005]; // LCS 길이 
	static int[][] S = new int[4005][4005]; // LCS 문자 추적하기 위한 배열  
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s = t = "";
		s = br.readLine();
		t = br.readLine();
		result = "";
		
		N = s.length();
		M = t.length();
		
		for(int i=1; i<= N; i++) // base case
		{
			sn[i] = s.charAt(i-1);
			L[i][0] = 0;
		}
		for(int i=1; i<= M; i++) // base case 
		{
			tm[i] = t.charAt(i-1);
			L[0][i] = 0;
		}
		for(int i=1; i<= N; i++)
		{
			for(int j=1; j<= M; j++)
			{
				if(sn[i] == tm[j]) 
				{
					L[i][j] = L[i-1][j-1] + 1;
					S[i][j] = 0;
				}
				else
				{
					L[i][j] = max(L[i-1][j], L[i][j-1]);
					if(L[i][j] == L[i][j-1]) { // 왼쪽에서 왔다면 1로 체킹 
						S[i][j] = 1;
					}
					else { // 오른쪽에서 왔다면 2로 체킹 
						S[i][j] = 2;
					}
				}
			}
		}
		solve(N, M);
		System.out.println(L[N][M]);
		System.out.println(result);
		
	}
	public static void solve(int dx, int dy)
	{
		if(!isRange(dx, dy)) return;
		
		if(S[dx][dy] == 0)
		{
			solve(dx-1,dy-1);
			result += sn[dx];
		}
		else if(S[dx][dy] == 1) solve(dx,dy-1);
		else if(S[dx][dy] == 2) solve(dx-1, dy);
	}

-> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다.
      A*(B*C) = (A*B)*C
 그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.

public class Circular_Queue {
    
    int rear = 0;            //최초 0에서부터 시작
    int front = 0;            //최초 0에서부터 시작
    int maxsize = 0;        //배열의 크기
    int[] circular_Queue;          //배열
    
    public Circular_Queue(int maxsize)
    {
        this.maxsize = maxsize;
        circular_Queue = new int[this.maxsize];
    }
    
    public boolean Isempty()    //배열이 공백 상태인지 체크하는 메서드입니다.
    {
        if(rear == front)
        {
            return true;
        }
        return false;
    }
    public boolean Isfull()        //배열이 포화 상태인지 체크하는 메서드입니다.
    {
        if((rear+1)%maxsize == front)
        {
            return true;
        }
        return false;
    }
    
    public void EnQueue(int num)
    {
        if(Isfull())            //배열이 포화상태일경우
        {
            System.out.println("큐가 가득 찼습니다");
        }
        else                //배열이 포화상태가 아닐경우
        {
            rear = (rear+1) % maxsize;
            circular_Queue[rear]=num;
        }
    }
    
public int DeQueue()
    {
        if(Isempty())         //배열이 공백상태이면 -1반환
        {
            return -1;
        }
        else                 //배열이 공백상태가 아니라면
        {
            front = (front+1)%maxsize;
            return circular_Queue[front];
        }
    }
}

public class LinkedQueue{
    Node front;
    Node rear;
    public class Node {
        int data;
        Node next;
    }
    public LinkedQueue() {
        front = null;
        rear = null;
    }    
    
    @Override
    public boolean isEmpty() {
        return (front==null);
    }
 
    @Override
    public void enQueue(int item) {
        QueueNode node = new QueueNode(item);
 
        if(isEmpty()){ // 처음 만든 경우는 font rear 같은 노드로 설정
            front = node;
            rear = node;
        }else{
            rear.next = node;
            rear = node;
        }
    }
 
    @Override
    public char deQueue() {
        if(isEmpty()){
            System.out.println("큐의 내용이 존재하지 않습니다.");
            return 0;
        }else{
            int item = front.item;
            front = front.next;
            if(front==null){ // 삭제전 front 랑 rear 같은 위치에 있었던 경우 해당 노드가 삭제됬으니 rear null
                rear=null;
            }
            return item;
        }
    }

public class baek11437 {

	static int N, M;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	static int[] parent = new int[50005];
	static int[] depth = new int[50005];
	public static void main(String[] args) throws IOException {

		int dx=0, dy=0;
		for(int i=1; i<= N-1; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			adj.get(dx).add(dy);
			adj.get(dy).add(dx);
		}
		
		dfs(1,1,0); // parent, depth 배열 완성하기 
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=1; i<= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			int xDepth = depth[dx];
			int yDepth = depth[dy]; // 각각의 depth 가져와서 확인!
			
			while(xDepth > yDepth) // x 가 클 경우 낮춰주면서 부모노드로 이동 
			{
				dx = parent[dx];
				xDepth--;
			}
			
			while(xDepth < yDepth)
			{
				dy = parent[dy];
				yDepth--;
			}
			
			while( dx != dy ) // 같은 depth 일때 둘다 부모노드로 올라가면서 찾기 
			{
				dx = parent[dx];
				dy = parent[dy];
			}
			
			System.out.println(dx);
		}
	}
	public static void dfs(int cur, int d, int p) // 현재 노드, 깊이, 부모 노드 
	{
		depth[cur] = d;
		parent[cur] = p;
		for(int next : adj.get(cur))
		{
			if(next != p) // 해당 노드에서 depth 가 더 깊은 곳으로만 이동 / 부모노드로 이동하지 않는다
			{
				dfs(next, d+1, cur); // 다음 depth 로 이동 / 현재 노드가 부모 노드가 됨 
			}
		}
	}
}

public class baek11438 {

	static int N, M, max_level;
	static final int MAX_NODE = 100005;
	static int[] depth = new int[MAX_NODE]; // 노드의 깊이(레벨) 
	static int[][] parent = new int[MAX_NODE][20]; // parent[x][y] :: x 의 2^y번째 조상을 의미  
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(); 
	public static void main(String[] args) throws IOException {

		max_level = 0;
		int result =1;
		while(result < N) // max_level 구하기 
		{
			result *= 2;
			max_level++;
		}
		
		int dx =0, dy=0;
		
		depth[0] = -1; // 루트 노드 깊이를 0으로 만들어 주기 위해 ! 
		makeTree(1,0); // 트리 만들기 !! 
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=1; i<= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			if(depth[dx] != depth[dy]) // 두 노드의 깊이가 다를 경우 같게 맞춰 줘야함 
			{
				if(depth[dx] > depth[dy]) // dy 의 깊이가 더 크다라고 가정하고 끌어올린후 깊이를 같게 만든다 
				{ 
					int tmp = dx;
					dx = dy;
					dy = tmp;
				}
				
				for(int k = max_level; k >= 0; k--)
				{
					if(depth[dx] <= depth[parent[dy][k]])
						dy = parent[dy][k];
				}
			}
			
			int lca = dx;
			
			if(dx != dy)
			{
				for(int k = max_level; k >= 0; k--)
				{
					if(parent[dx][k] != parent[dy][k])
					{
						dx = parent[dx][k];
						dy = parent[dy][k];
					}
					lca = parent[dx][k];
				}
			}
			bw.write(lca+"\n");
		}
		bw.flush();
	}
	public static void makeTree(int cur, int p)
	{
		depth[cur] = depth[p] + 1; // 부모 노드의 깊이에서 +1 ==> 현재 노드 깊이 
		parent[cur][0] = p; // 바로 위 부모 노드 
		
		/*
		  	Node 의 2^i 번째 조상은 tmp 의 2^(i-1) 번째 조상의 2^(i-1)번째 조상과 
		  	같다는 의미
		  	예 ) i =3 일때
		  	Node의 8번째 조상은 tmp(Node의 4번째 조상)의 4번째 조상과 같다.
		  	i=4 일때는 Node 16번째 조상은 Node 의 8번째 조상(tmp)의 8번째와 같다.
		 */
		for(int i=1; i<= max_level; i++)
		{
			int tmp = parent[cur][i-1];
			parent[cur][i] = parent[tmp][i-1];
		}
		
		for(int next : adj.get(cur)) // 자식 노드 내려가면서 확인 
		{
			if(next != p) // 사이클 방지 아래로만 내려가기 
			{
				makeTree(next, cur);
			}
		}
	}
	
}

public class Main {

	static int N, M, max_level;
	static int max_node = 40005;
	static int[][] par = new int[max_node][20];
	static int[] depth = new int[max_node];
	static int[] cost = new int[max_node];
	static ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>();
	public static void main(String[] args) throws IOException {

		max_level = 0;
		int mul = 1;
		while(N > mul) { // 확인 
			mul *= 2;
			max_level++;
		}
		
		int dx = 0, dy = 0, c = 0;
		for(int i=1; i<= N-1; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			adj.get(dx).add(new Node(dy, c));
			adj.get(dy).add(new Node(dx, c));
		}
		depth[0] = -1;
		dfs(1, 0, 0);
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=1; i<= M; i++)
		{
			st = new StringTokenizer(br.readLine());
			dx = Integer.parseInt(st.nextToken());
			dy = Integer.parseInt(st.nextToken());
			
			int result = 0;
			int rdx = dx, rdy = dy;
			if(depth[dx] != depth[dy])
			{
				if(depth[dx] > depth[dy])
				{
					int tmp = dx;
					dx = dy;
					dy = tmp;
				}
				
				for(int k = max_level; k >= 0; k--)
				{
					if(depth[dx] <= depth[par[dy][k]]) {
						dy = par[dy][k];
					}
				}
			}
			
			int lca = dx;
			
			if(dx != dy)
			{
				for(int k = max_level; k >= 0; k--)
				{
					if(par[dx][k] != par[dy][k])
					{
						dx = par[dx][k];
						dy = par[dy][k];
					}
					lca = par[dx][k];
				}
			}
			
			result = ( cost[rdx] + cost[rdy] ) - ( 2 * cost[lca] );
			bw.write(result+"\n");
		}
		bw.flush();
	}
	public static void dfs(int cur, int p, int c)
	{
		depth[cur] = depth[p] + 1;
		cost[cur] = c;
		par[cur][0] = p;
		
		int tmp = 0;
		for(int i=1; i<= max_level; i++)
		{
			tmp = par[cur][i-1];
			par[cur][i] = par[tmp][i-1];
		}
		
		for(Node next : adj.get(cur))
		{
			if(next.dx != p)
			{
				dfs(next.dx, cur, next.cost + c);
			}
		}
	}
}