공통조상

#include <stdio.h>
#define SZ 10001
 
struct Node{
    int parent = 0;
    int left = 0;
    int right = 0;
};
 
int t, V, E, s1, s2, max_idx;
 
int count_node(Node tree[], int node){
    int ans = 1;
 
    if (tree[node].left != 0) ans += count_node(tree, tree[node].left);
    if (tree[node].right != 0) ans += count_node(tree, tree[node].right);
 
    return ans;
}
 
int main(){
    //freopen("input.txt", "r", stdin);
 
    scanf("%d", &t);
 
    for (int tc = 1; tc <= t; tc++){
        Node tree[SZ];
        bool check[SZ] = { false, };
        scanf("%d %d %d %d", &V, &E, &s1, &s2);
        int x, y;
        for (int i = 0; i < E; i++){
            scanf("%d %d", &x, &y);
            if (tree[x].left == 0){
                tree[x].left = y;
            }
            else{
                tree[x].right = y;
            }
 
            tree[y].parent = x;
        }
 
        int cur = tree[s1].parent;
        while (true){
            check[cur] = true;
            if (cur == 1) break;
            cur = tree[cur].parent;
        }
 
        cur = tree[s2].parent;
        while (true){
            if (check[cur]){
                printf("#%d %d %d\n", tc, cur, count_node(tree, cur));
                break;
            }
            cur = tree[cur].parent;
        }
    }
}