// cf bits/extc++.h nonsense
#ifdef ONLINE_JUDGE
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#endif
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T>
struct PSA {
    int n;
    vector<T> psum;

    template <typename U>
    PSA(const vector<U>& arr) : n(sz(arr)), psum(n + 1) {
        for (int i = 0; i < n; i++) {
            psum[i + 1] = psum[i] + arr[i];
        }
    }

    T query(int l, int r) const {
        return psum[r] - psum[l];
    }
};

template <typename T>
bool on(T mask, int bit) {
    return (mask >> bit) & 1;
}

using GG = vector<vector<int>>;

int visit(int);

struct Grader {
    int c_pos, c_color;

    Grader() {}
    Grader(int pos, int color) : c_pos(pos), c_color(color) {}

    int query_visit(int u) {
        c_pos = u;
        return c_color = visit(u + 1);
    }
} G;

struct Tree {
    int n;
    GG graph;
    vector<int> par, siz;

    Tree() {}
    Tree(const GG& graph) : n(sz(graph)), graph(graph), par(n, -2), siz(n) {}

    void dfs(int u, int p) {
        par[u] = p;
        siz[u] = 1;

        for (auto& v : graph[u]) {
            if (v == p) {
                continue;
            }

            dfs(v, u);
            siz[u] += siz[v];
        }
    }

    bool is_vis(int u) const {
        return par[u] != -2;
    }

    static Tree from_root(const GG& graph, int root) {
        Tree tree(graph);
        tree.dfs(root, -1);
        return tree;
    }

    static Tree from_edge(const GG& graph, int u, int v) {
        Tree tree(graph);
        tree.dfs(u, v);
        tree.dfs(v, u);
        return tree;
    }
};

vector<int> find_centroid(const GG& graph) {
    int n = sz(graph), u = 0;
    auto siz = Tree::from_root(graph, u).siz;

    while (true) {
        pair opt {-1, -1};
        for (auto& v : graph[u]) {
            opt = max(opt, {siz[v], v});
        }

        auto [csz, v] = opt;
        if (csz <= n / 2) {
            if (csz == n / 2 && n % 2 == 0) {
                return {u, v};
            }
            return {u};
        }

        siz[u] -= siz[v];
        siz[v] += siz[u];
        u = v;
    }
}

vector<vector<int>> to_adj_list(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> graph(n);

    for (auto& [u, v] : edges) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    return graph;
}

vector<int> mark(vector<pair<int, int>> edges, int targ) {
    for (auto& [u, v] : edges) {
        u--;
        v--;
    }
    targ--;

    int n = sz(edges) + 1;
    auto graph = to_adj_list(n, edges);

    int root = [&]() -> int {
        auto centroids = find_centroid(graph);
        if (sz(centroids) == 1) {
            return centroids[0];
        }

        assert(sz(centroids) == 2);
        int u = centroids[0], v = centroids[1];

        {
            Tree tmp(graph);
            tmp.dfs(u, v);
            if (tmp.is_vis(targ)) {
                return u;
            } else {
                return v;
            }
        }
    }();

    Tree tree = Tree::from_root(graph, root);
    vector<bool> on_path(n);

    {
        int u = targ;
        while (u != -1) {
            on_path[u] = true;
            u = tree.par[u];
        }
    }

    vector<int> ans(n);
    {
        vector<int> q;
        vector<bool> vis(n);

        auto push = [&](int u) -> void {
            if (vis[u]) {
                return;
            }

            vis[u] = true;
            q.push_back(u);
        };

        push(root);

        while (sz(q)) {
            int u = q.back();
            q.pop_back();

            if (u == root) {
                ans[u] = 0;
            } else {
                if (on_path[u]) {
                    ans[u] = ans[tree.par[u]];
                    assert(!ans[u]);
                } else {
                    ans[u] = ans[tree.par[u]] ^ 1;
                }
            }

            for (auto& v : graph[u]) {
                push(v);
            }
        }
    }

    return ans;
}

void locate_ch(const Tree& tree) {
    while (true) {
        int u = G.c_pos, uc = G.c_color;

        vector<int> ch;
        for (auto& a : tree.graph[u]) {
            if (a != tree.par[u]) {
                ch.push_back(a);
            }
        }

        for (auto& a : ch) {
            if (tree.siz[a] > tree.siz[ch[0]]) {
                swap(ch[0], a);
            }
        }

        bool found = false;
        for (auto& v : ch) {
            if (G.query_visit(v) == uc) {
                found = true;
                break;
            }
            G.query_visit(u);
        }

        if (!found) {
            return;
        }
    }
}

void locate(vector<pair<int, int>> edges, int init_pos, int init_color) {
    for (auto& [u, v] : edges) {
        u--;
        v--;
    }
    init_pos--;

    int n = sz(edges) + 1;
    auto graph = to_adj_list(n, edges);

    G = Grader(init_pos, init_color);

    auto centroids = find_centroid(graph);

    Tree tree;
    if (sz(centroids) == 1) {
        tree = Tree::from_root(graph, centroids[0]);
    } else {
        tree = Tree::from_edge(graph, centroids[0], centroids[1]);
    }

    auto should_stop = [&](int u) -> bool {
        return find(begin(centroids), end(centroids), u) != end(centroids);
    };

    int hist = -1;
    while (true) {
        int u = G.c_pos, uc = G.c_color;

        if (should_stop(u)) {
            break;
        }

        hist = u;
        if (G.query_visit(tree.par[u]) == uc) {
            G.query_visit(u);
            locate_ch(tree);
            return;
        }
    }

    dbg(G.c_pos, hist);
    if (sz(centroids) == 2) {
        if (G.c_color) {
            G.query_visit(centroids[0] ^ centroids[1] ^ G.c_pos);
        }

        locate_ch(Tree::from_edge(graph, centroids[0], centroids[1]));
    } else {
        Tree tree2(graph);
        tree2.dfs(G.c_pos, hist);
        dbg(tree2.par);
        locate_ch(tree2);
    }
}