#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
vector<int> mark(vector<pair<int, int>> F, int safe) {
--safe;
int n = (int) F.size() + 1;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
auto [u, v] = F[i];
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> dist(n);
function<void(int, int)> dfs = [&](int v, int p) {
for (int u : g[v]) {
if (u != p) {
dist[u] = dist[v] + 1;
dfs(u, v);
}
}
};
dfs(safe, safe);
vector<int> ties(n);
function<void(int, int)> dfs2 = [&](int v, int p) {
for (int u : g[v]) {
if (u != p) {
if (dist[u] > dist[v]) {
ties[u] = 1; //go up
}
dfs2(u, v);
}
}
};
for (int i = 0; i < n; ++i) {
if (g[i].size() == 2) {
dfs2(i, i);
break;
}
}
return ties;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
//~ --curr;
//~ int n = (int) F.size() + 1;
//~ vector<vector<int>> g(n);
//~ for (int i = 0; i < n - 1; ++i) {
//~ auto [u, v] = F[i];
//~ --u, --v;
//~ g[u].push_back(v);
//~ g[v].push_back(u);
//~ }
//~ vector<int> sz(n);
//~ vector<int> pr(n);
//~ function<void(int, int)> dfs = [&](int v, int p) {
//~ sz[v] = 1;
//~ for (int u : g[v]) {
//~ if (u != p) {
//~ pr[u] = v;
//~ dfs(u, v);
//~ sz[v] += sz[u];
//~ }
//~ }
//~ };
//~ for (int i = 0; i < n; ++i) {
//~ if (g[i].size() == 2) {
//~ dfs(i, i);
//~ break;
//~ }
//~ }
//~ function<void(int, int, int)> dfs2 = [&](int v, int p, int tt) {
//~ if (tt == 1) {
//~ int x = visit(pr[v] + 1);
//~ return dfs2(pr[v], v, x);
//~ }
//~ sort(g[v].begin(), g[v].end(), [&](int i, int j) {
//~ return sz[g[v][i]] > sz[g[v][j]];
//~ });
//~ for (int u : g[v]) {
//~ if (u == pr[v] || u == p) continue;
//~ int x = visit(u + 1);
//~ if (x == 1) {
//~ visit(v + 1);
//~ } else {
//~ return dfs2(u, v, x);
//~ }
//~ }
//~ };
//~ dfs2(curr, curr, t);
}
