// start를 root로 하는 서브트리에 있는 단절점을 찾는다
// 반환값은 해당 서브트리의 역방향 간선으로 갈 수 있는 정점 중
// 가장 일찍 발견된 정점의 발견 시점
private static int dfs(int start, boolean root) {
    discovered[start] = ++depth;

    // 자식이 없다면 현재 점 반환
    int dfn = discovered[start];
    int dgree = 0;

    for (Integer next : path.get(start)) {
        if (discovered[next] == 0) {
            // root인 경우 단절점 판단을 자손 개수체크
            ++dgree;
            // 이 서브 트리에서 갈 수 있는 가장 높은 정점의 번호
            int low = dfs(next, false);
            // 번호가 자신 이하라면 단절점
            if (root == false && low >= discovered[start]) {
                solution[start] = true;
            }
            // root값으로 맞춰준다
            dfn = Math.min(dfn, low);
        } else {
            // 현재 횟수와 방문했던 위치와 비교.
            dfn = Math.min(dfn, discovered[next]);
        }
    }
    if (root) {
        if (dgree > 1) {
            solution[start] = true;
        }
    }
    return dfn;
}

ll mod_pow(ll x, ll n, ll mod){
    ll res = 1; 
    while (n){
        if (n&1) res = res*x%mod; // if n is odd 
        x = x*x%mod;  
        n >>= 1;  // same as n /= 2;  
    }
    return res;  
}
 

bool isPrime(int n){
    for (int i = 2; i*i <= n; i++){
        if (n%i == 0) 
            return false; 
    }
    return n != 1;  
}

// mid 가 해(x)보다 크거나,작거나 같은경우
while (left <= right) {
    mid = (left + right) / 2;
    if (mid > 해) {
        right = mid - 1;
    else if (mid < 해) {
        left = mid + 1;
    } else {
        해를 찾음!
        break
    }
}
// mid 가 해이거나 아니거나
// mid 가 해의 후보군일경우 또다른 해를 찾는다
// left == right 일경우 loop 에서 빠져나올 수 없을 수 있음으로 주의!

while (left < right) {
    mid = (left + right) / 2;
    if (f(mid) == 1) {
        // 해를 찾음
        right = mid;
    } else {
        left = mid + 1;
    }
}
System.out.println(right);
// 구현에 따라 다를 수 있다
int ans = 0;
while (left <= right) {
    mid = (left + right) / 2;
    if (f(mid) == 1) {
        ans = mid;
        right = mid-1;
    } else {
        left = mid + 1;
    }
}
System.out.println(ans);

for (V next : adj.get(curr.to)) {
    if (dist[curr.to] + next.w > dist[next.to]) {
        dist[next.to] = dist[curr.to] + next.w;
        q.add(new V(next.to, dist[next.to]));
        trace[next.to] = curr.to;
    }
}

//경로 출력은 stack을 쓰는게 깔끔
System.out.println(dist[1]);

// LIFO
Stack<Integer> st = new Stack<Integer>();
st.push(1);
st.push(trace[1]);
int last = trace[1];
while (last != 1) {
    last = trace[last];
    st.push(last);
}
while (!st.isEmpty()) {
    System.out.print(st.pop() + " ");
}
// 혹은 재귀를 이용
static void printPath(int last) {
    if (trace[last] == 1) {
        System.out.print(1 + " " + last);
        return;
    }
    printPath(trace[last]);
    System.out.print(" "+ last);
}

PriorityQueue<Edge> que = new PriorityQueue<>();
visited[start] = true;
dist[start] = 0; // INF로 초기화
que.add(new Edge(start, 0));
 
while (!que.isEmpty()) {
    int cur_index = que.peek().index;
    int cur_w = que.peek().weight;

    que.poll();

    if (dist[cur_index] < cur_w) {
        continue;
    }
    for (Edge edg: list.get(cur_index)) {
        int next_index = edg.index;
        int next_weight = edg.weight;
    
        if (next_index == cur_index) {
            continue;
        }
        if (!visited[next_index] || dist[cur_index] + next_weight < dist[next_index]) {
            dist[next_index] = dist[cur_index] + next_weight;
            visited[next_index] = true;
            que.add(new Edge(next_index, dist[next_index]));
        }
    }
}
for (int i = 1; i <= V; i++) {
    if (dist[i] == Integer.MAX_VALUE) {
        System.out.println("INF");
    } else {
        System.out.println(dist[i]);
    }
}

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 52;
const int INF = 1000000000;
 
// 정점 문자를 0~51 사이의 번호로 바꿔주는 간단한 함수
inline int CtoI(char c){
    if(c <= 'Z') return c - 'A';
    return c - 'a' + 26;
}
 
int main(){
    int N; // 간선 개수
    int c[MAX_V][MAX_V] = {0}; // c[i][j]: i에서 j로 가는 간선의 용량
    int f[MAX_V][MAX_V] = {0}; // f[i][j]: i에서 j로 현재 흐르는 유량
    vector<int> adj[MAX_V]; // 인접 리스트
 
    // 간선 정보 입력받기
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        char u, v;
        int w;
        scanf(" %c %c %d", &u, &v, &w);
        u = CtoI(u); v = CtoI(v);
        c[u][v] += w; // 같은 간선이 여러 번 들어올 수 있으므로 +=
        adj[u].push_back(v);
        adj[v].push_back(u); // 역방향 간선도 추가해줘야 함
    }
 
    // total: 총 유량, S: 소스, E: 싱크
    int total = 0, S = CtoI('A'), E = CtoI('Z');
    // 증가 경로를 못 찾을 때까지 루프
    while(1){
        // 증가 경로를 BFS로 찾음
        int prev[MAX_V];
        fill(prev, prev+MAX_V, -1);
        queue<int> Q;
        Q.push(S);
        while(!Q.empty()){
            int curr = Q.front();
            Q.pop();
            for(int next: adj[curr]){
                // c[i][j]-f[i][j] > 0: i에서 j로 유량을 흘릴 여유가 남았는가?
                // prev[next] == -1: next 정점을 아직 방문하지 않았는가?
                if(c[curr][next]-f[curr][next] > 0 && prev[next] == -1){
                    Q.push(next);
                    prev[next] = curr; // 경로를 기억하기 위해 prev 배열 사용
                    if(next == E) break; // 싱크에 도달하면 나옴
                }
            }
        }
        // 싱크로 가는 경로가 더 없으면 루프 탈출
        if(prev[E] == -1) break;
 
        // 경로상에서 가장 허용치가 낮은 곳을 찾음
        int flow = INF;
        for(int i=E; i!=S; i=prev[i])
            flow = min(flow, c[prev[i]][i]-f[prev[i]][i]);
        // 찾은 flow만큼 해당 경로에 유량 흘려줌
        for(int i=E; i!=S; i=prev[i]){
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
        // 총 유량 값 증가
        total += flow;
    }
    // 결과 출력
    printf("%d\n", total);
}