import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

import java.util.StringTokenizer;


class Edge {

int start, end;

int weight;


public Edge(int start, int end, int weight) {

this.start = start;

this.end = end;

this.weight = weight;

}

}


class Node<T> extends ArrayList<T> {

public static Node[] Tree;

public int nodeNo;

public int parentNo;

public int rank;


public void makeSet(int x) {

nodeNo = x;

parentNo = x;

rank = 0;

}


public int findSet() {


Stack<Integer> nodeStack = new Stack<>();


nodeStack.add(nodeNo); // 검색 노드 조건

Node moveNode = Tree[nodeNo];

while (moveNode.nodeNo != moveNode.parentNo) { // 부모 노드 조건

moveNode = Tree[moveNode.parentNo];

nodeStack.add(parentNo);

}


if (nodeStack.size() > 1) { // 찾은 부모가 있다면

int represent = moveNode.nodeNo;


while (!nodeStack.isEmpty()) { // 부모노드를 가르키도록

Tree[nodeStack.pop()].parentNo = represent;

}

}


return moveNode.nodeNo;

}


public void unionSet(Node<T> node) {

Node first = Tree[this.nodeNo];

Node second = Tree[node.nodeNo];

int f = first.findSet();

int s = second.findSet();

if (f == s) {

return;

}


first = Tree[f];

second = Tree[s];


if (first.rank > second.rank) {

second.parentNo = first.nodeNo;

} else {

first.parentNo = second.nodeNo;

if (this.rank == node.rank) {

node.rank++;

}

}

}


}


class Solution {


static int DATA_SIZE;

static Node<Edge>[] tree;

static Boolean isFound;

static int[] visited;

static int[] distance;

static boolean Debug = true;


public static void main(String args[]) throws Exception {


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "input (29).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in));

}


StringTokenizer st;

int start, end, weight;

int testNo = Integer.parseInt(br.readLine());

for (int T = 1; T <= 6; T++) {

st = new StringTokenizer(br.readLine());

int nodeNum = Integer.parseInt(st.nextToken());

int taskNum = Integer.parseInt(st.nextToken());


StringBuffer sb = new StringBuffer();

System.out.print(String.format("#%d", T, nodeNum, taskNum));

log("");


tree = new Node[nodeNum + 1];

visited = new int[nodeNum + 1];

distance = new int[nodeNum + 1];


Node.Tree = tree;

for (int i = 0; i < tree.length; i++) {

tree[i] = new Node<Edge>();

tree[i].makeSet(i);

}

// [방법2]

ArrayList<Integer> representList = new ArrayList<>();


for (int i = 0; i < taskNum; i++) {

st = new StringTokenizer(br.readLine());

switch (st.nextToken()) {

case "!":

start = Integer.parseInt(st.nextToken());

end = Integer.parseInt(st.nextToken());

weight = Integer.parseInt(st.nextToken());


tree[start].add(new Edge(start, end, weight));

tree[end].add(new Edge(end, start, -1 * weight));

tree[start].unionSet(tree[end]);

break;

case "?":

start = Integer.parseInt(st.nextToken());

end = Integer.parseInt(st.nextToken());


// findPath(start, end);

int a = tree[start].findSet();

int b = tree[end].findSet();

if (a == b) {

// [방법2 ] 무게의 상대값을 기록하여 재활용하기

// if(!representList.contains((Integer) a)) {

// representList.add(a);

// visited = new int[nodeNum + 1];

// distance = new int[nodeNum + 1];

// }

int w_end = findWeight(end);

int w_start = findWeight(start);

int answer = w_end - w_start;


sb.append(String.format(" %d", answer));

} else {

sb.append(" UNKOWN");

}

break;

}

}


System.out.println(sb.toString());

}


}


private static int findWeight(int nodeNo) {

if (visited[nodeNo] == 1) {

log(String.format("3. distance[%d] = %d", nodeNo, distance[nodeNo]));

return distance[nodeNo];

}


// 연결된 노드를 찾는다.

int subParent = 0;

Queue<Integer> que = new LinkedList();

que.add(nodeNo);

Stack<Integer> visiting = new Stack();


while (!que.isEmpty()) {

int reStart = que.poll();

log(String.format("nodeNo:%d    reStart: %d", nodeNo, reStart));

for (Edge line : tree[reStart]) {

log(String.format("visited[%d] = %d", line.end, visited[line.end]));

if (visited[line.end] == 1 || line.end == tree[nodeNo].parentNo) {

// 무게가 기록된 연결된 노드를 찾음 || 부모노드

subParent = line.end;

break;

}

que.add(line.end);

visited[line.end] = 1;

visiting.add(line.end);

}

}


for (int i : visiting) {

visited[i] = 0;

}

que = new LinkedList();

que.add(subParent);

log("subParent 진입: " + subParent);

while (!que.isEmpty()) {

int reStart = que.poll();

for (Edge line : tree[reStart]) {

if (visited[line.end] == 1) {

continue;

}

// que.add(line.end);

que.add(line.end);

visited[line.end] = 1;

distance[line.end] = distance[line.start] + line.weight;

log(String.format("2. distance[%d] = %d", line.end, distance[line.end]));


if (line.end == nodeNo) {

return distance[line.end];

}

}

}


return -1;

}

private static void log(String input) {

if (true) {

System.out.println(input);

}

}


}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
 
class Solution {
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int T = 1; T <= 10; T++) {
 
            // [input] 데이터 입력
            int dataSize = Integer.parseInt(br.readLine());
            String[] originData = br.readLine().trim().split(" ");
            int commandSize = Integer.parseInt(br.readLine());
            String[] commandData = br.readLine().trim().split(" ");
 
            LinkedList<Integer> ticket = new LinkedList<>();
 
            for (int i = 0; i < originData.length; i++) {
                ticket.add(Integer.parseInt(originData[i]));
            }
 
            int cnt = 0;
            while (cnt < commandData.length) {
                String Command = commandData[cnt++];
                 
                int commandIndex = -1;
                if(!Command.equals("A")) {
                    commandIndex = Integer.parseInt(commandData[cnt++]);
                }
                 
                int Valuecount = Integer.parseInt(commandData[cnt++]);
 
                if(Command.equals("I")) {
                    int insertValue;
                    for (int j = 0; j < Valuecount; j++) {
                        insertValue = Integer.parseInt(commandData[cnt++]);
                        ticket.add(commandIndex++, insertValue);
                    }
                }else if(Command.equals("D")) {
                    for (int j = 0; j < Valuecount; j++) {
                        ticket.remove(commandIndex);
                    }
                }else {
                    int addValue;
                    for (int j = 0; j < Valuecount; j++) {
                        addValue = Integer.parseInt(commandData[cnt++]);
                        ticket.add(addValue);
                    }
                }
                 
            }
 
            String result = String.format("#%d", T);
            for (int i = 0; i < 10; i++) {
                result += String.format(" %d", ticket.get(i));
            }
             
            System.out.println(result);
        }
 
    }
 
}


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
 
class Solution {
 
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int T = 1; T <= 10; T++) {
 
            Stack<Character> operStack = new Stack<>();
            Stack<Character> postStack = new Stack<>();
             
            Stack<Integer> calStack = new Stack<>();
 
            // [input] CaseNo DataLen
            int testLen = Integer.parseInt(br.readLine());
 
            // [input] 데이터 입력 ex. "(3+5+(4+3*6))", "3*2*6*(2+3)+4+1+5*7*8"
            String readLine = br.readLine();
             
            // Part1. 후위연산으로 변환
            for (int i = 0; i < testLen; i++) {
                char input = readLine.charAt(i);
                 
                if(input == '(') {
                    operStack.push(input);
                }else if(input == ')') {
                    while(operStack.peek()!='(') { // 연산자 스택에는 괄호가 pair로 존재
                        // 괄호 안에 연산자가 남아있는 연산자 처리 (우선순위가 높은 연산자, 혹
                        postStack.push(operStack.pop());
                    }
                    operStack.pop(); // ( ) 까지 연산을 끝냈으므로  '('을 날림
                }else if(input >= '0' && input <='9') {
                    postStack.push(input);
                }else {
                    // 연산자가 2번 연달아오기 직전 5 + 6 * 7 + 8
                    // post: [5,6,7] oper: [+,*] input:'+' => post: [5,6,7,*,+] oper[+]
                     
                    // case1(While 통과). 우선순위가 낮거나 같은 연산자가 온 경우, 연산자 스택의 pop하여 후위연산 배열에 넣는다.
                    while(!operStack.isEmpty() && priority(input) >= priority(operStack.peek())) {
                        postStack.push(operStack.pop());
                        if(operStack.isEmpty()) {
                            break;
                        }
                    }
                    // case2(While 무시). 우선순위가 높은 연산자가 input으로 왔을 때는, 연산자스택의 값을 pop하지 않는다.
                     
                    operStack.push(input); // 최근 연산자는 스택에 저장
                }
            }
             
            // 괄호가 없는 input 값이 주어졌다면, 마지막에 스택에는 마지막 연산자가 남아있다.
            while(!operStack.isEmpty()) {
                postStack.push(operStack.pop());
            }
             
             
            // Part2. 계산과정
            int x,y;
            int length = postStack.size();
            Character[] postArr = new Character[length];
            postStack.toArray(postArr);
             
            for(int i=0; i<length; i++) {
                char item = postArr[i];
                // System.out.print(item); 후위연산 변환 디버깅
                if(item >= '0' && item <= '9') {
                    calStack.push(item-'0');
                }else if(item == '*') {
                    x = calStack.pop();
                    y = calStack.pop();
                    calStack.push(x*y);
                }else if(item == '+') {
                    x = calStack.pop();
                    y = calStack.pop();
                    calStack.push(x+y);
                }
            }
 
            System.out.println(String.format("#%d %d", T, calStack.pop()));
        }
 
    }
 
    // 연산자 우선 순위 (값이 낮을 수록 우선순위가 높다)
     
    private static int priority(char c) {
        switch(c) {
        case '(':   return 5; // 괄호가 로직에 영향을 주지 않도록 큰 값을 부여
        case '*':   return 1;
        case '-':   return 2
        case '+':   return 2;
        default : return -1;
        }
    }
 
}


import java.util.Scanner;
import java.util.Stack;
 
class Solution {
 
    public static void main(String args[]) throws Exception {
 
        Scanner sc = new Scanner(System.in);
        int[] pair = new int[256]; // 아스키코드
         
        pair['('] = ')';
        pair['['] = ']';
        pair['{'] = '}';
        pair['<'] = '>';
         
        for (int T = 1; T <= 10; T++) {
 
            Stack<Character> stack = new Stack();
            boolean possible = true;
 
            // [input] Test 번호
            int inputLen = Integer.parseInt(sc.nextLine());
             
            // [input] 데이터 입력 & 풀이
            String line = sc.nextLine();
            for (int i = 0; i < inputLen; i++) {
                 
                char input = line.charAt(i);
                // 괄호시작
                if(input == '(' ||input == '[' ||input == '{' ||input == '<')
                {
                    stack.push(input);
                }
                 
                // 괄호끝
                if(input == ')' ||input == ']' ||input == '}' ||input == '>')
                {
                    if