Code: Oriented Journey

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

void solveA() {
    int n;
    long long s;
    cin >> n >> s;

    if (n == -1)
        exit(0);

    vector<int> X(n + 1, 0);
    long long val = s - 1;
    X[1] = 0;
    for (int i = 2; i <= n; ++i) {
        X[i] = (val >> (i - 2)) & 1;
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        if (u == -1)
            exit(0);

        if (u > v)
            swap(u, v);

        if (X[u] == X[v]) {
            cout << u << " " << v << endl;
        } else {
            cout << v << " " << u << endl;
        }
    }
}

void solveB() {
    int n;
    cin >> n;
    if (n == -1)
        exit(0);

    vector<vector<pair<int, int>>> adj(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        if (a == -1)
            exit(0);

        int u = min(a, b);
        int v = max(a, b);
        int w = (a == u) ? 0 : 1;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> X(n + 1, -1);
    queue<int> q;

    q.push(1);
    X[1] = 0;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (auto edge : adj[curr]) {
            int nxt = edge.first;
            int w = edge.second;

            if (X[nxt] == -1) {
                X[nxt] = X[curr] ^ w;
                q.push(nxt);
            }
        }
    }

    long long s = 1;
    for (int i = 2; i <= n; ++i) {
        if (X[i] == 1) {
            s += (1LL << (i - 2));
        }
    }

    cout << s << endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, q;
    cin >> t >> q;
    while (t--) {
        if (q == 1) {
            solveA();
        } else if (q == 2) {
            solveB();
        }
    }
    return 0;
}