#include <bits/stdc++.h>
using namespace std;
long long null = 0;
struct segment;
struct line;
struct point;
struct vec;
struct ray;
struct point {
  long double x, y;
  point() {}
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist_to_point(point p) {
    return sqrt((p.x - x) * (p.x - x) + (p.y - y) * (p.y - y));
  }
  bool operator<(point p) { return (x < p.x) || ((x == p.x) && (y < p.y)); }
};
struct vec {
  long double x, y;
  vec(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  vec(point a, point b) {
    x = b.x - a.x;
    y = b.y - a.y;
  }
  vec normal() {
    vec ans;
    ans.x = y;
    ans.y = -x;
    return ans;
  }
  vec opposite() {
    vec ans;
    ans.x = -x;
    ans.y = -y;
    return ans;
  }
  vec sum(vec b) {
    vec ans;
    ans.x = x + b.x;
    ans.y = y + b.y;
    return ans;
  }
  long double cross_product(vec v) { return x * v.y - v.x * y; }
  long double dot_product(vec v) { return x * v.x + y * v.y; }
  vec resize(long double size) {
    vec ans;
    ans.x = (x * size) / len();
    ans.y = (y * size) / len();
    return ans;
  }
  vec() {}
  long double len() { return sqrt(x * x + y * y); }
};
struct line {
  long double a, b, c;
  line(point a1, point b1) {
    a = a1.y - b1.y;
    b = b1.x - a1.x;
    c = -a1.x * a - a1.y * b;
  }
  line(long double a1, long double b1, long double c1) {
    a = a1;
    b = b1;
    c = c1;
  }
  line() {}
  vec normal_vec() {
    vec ans;
    ans.x = a;
    ans.y = b;
    return ans;
  }
  line normal_line(point p) {
    line ans;
    ans.a = -b;
    ans.b = a;
    ans.c = -ans.a * p.x - ans.b * p.y;
    return ans;
  }
  long double get_x(long double y1) {
    if (a == 0) return 0;
    return (-c - b * y1) / a;
  }
  long double get_y(long double x1) {
    if (b == 0) return 0;
    return (-c - a * x1) / b;
  }
  point intersection(line l) {
    point ans;
    ans.x = (-c * l.b + l.c * b) / (a * l.b - l.a * b);
    ans.y = (-a * l.c + l.a * c) / (a * l.b - l.a * b);
    return ans;
  }
  bool parallels(line l) { return a * l.b - l.a * b == 0; }
  long double dist_to_point(point p) {
    return abs((a * p.x + b * p.y + c) / (sqrt(a * a + b * b)));
  }
  long long is_inside(point p) {
    long double k = a * p.x + b * p.y + c;
    if (k < 0)
      return -1;
    else if (k == 0)
      return 0;
    return 1;
  }
};
struct segment {
  point a, b;
  segment() {}
  segment(point a1, point b1) {
    a = a1;
    b = b1;
  }
  long double len() {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  }
  bool is_inside(point p) {
    line l(a, b);
    if (l.is_inside(p) != 0) return false;
    vec v(p, a), v1(p, b);
    if (v.dot_product(v1) > 0) return false;
    return true;
  }
  long double dist_to_point(point p) {
    vec v(a, p), v1(a, b), v2(b, p), v3(b, a);
    if (v.dot_product(v1) < 0) return p.dist_to_point(a);
    if (v2.dot_product(v3) < 0) return p.dist_to_point(b);
    line l(a, b);
    return l.dist_to_point(p);
  }
  point get_center() {
    point ans;
    ans.x = (a.x + b.x) / 2;
    ans.y = (a.y + b.y) / 2;
    return ans;
  }
};
struct ray {
  point a, b;
  ray(point p, point p1) {
    a = p;
    b = p1;
  }
  ray() {}
  long double dist_to_point(point p) {
    vec v(a, p), v1(a, b);
    if (v.dot_product(v1) < 0) return a.dist_to_point(p);
    line l(a, b);
    return l.dist_to_point(p);
  }
  bool is_inside(point p) {
    line l(a, b);
    if (l.is_inside(p) != 0) return false;
    vec v(a, p), v1(a, b);
    if (v.dot_product(v1) < 0) return false;
    return true;
  }
};
struct angle {
  point a, b, c;
  angle(){};
  angle(point a1, point b1, point c1) {
    a = a1;
    b = b1;
    c = c1;
  }
  long double get_angle() {
    vec v(b, a), v1(b, c);
    return acos(v.dot_product(v1) / (v.len() * v1.len()));
  }
  long double get_grad_angle() {
    vec v(b, a), v1(b, c);
    return 180 * acos(v.dot_product(v1) / (v.len() * v1.len())) /
           3.141592653589793238462643;
  }
};
struct polygon {
  long long n;
  vector<point> points;
  long double get_area() {
    point a(0, 0);
    vec v(a, points[0]);
    long double ans = 0;
    for (long long i = 1; i < n; ++i) {
      vec v1(a, points[i]);
      ans = ans + v.cross_product(v1);
      v = v1;
    }
    vec v2(a, points[0]);
    vec v1(a, points[n - 1]);
    return abs(ans + v1.cross_product(v2)) / 2;
  }
};
struct triangle {
  point a, b, c;
  triangle() {}
  triangle(point a1, point b1, point c1) {
    a = a1;
    b = b1;
    c = c1;
  }
  long double get_area() {
    point d(0, 0);
    vec v(a, d), v1(b, d), v2(c, d);
    return (v.cross_product(v1) + v1.cross_product(v2) + v2.cross_product(v)) /
           2;
  }
  point get_center() {
    segment s(a, b), s1(a, c);
    point p = s.get_center(), p1 = s1.get_center();
    line l(a, b), l1(a, c), l2(b, c);
    l = l.normal_line(p);
    l1 = l1.normal_line(p1);
    return l.intersection(l1);
  }
  long double get_R() {
    triangle t(a, b, c);
    point p = t.get_center();
    return p.dist_to_point(a);
  }
};
long long power(long long a, long long b) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a;
  else {
    long long k = power(a, b / 2);
    return k * k * power(a, b % 2);
  }
}
long long power_mod(long long a, long long b, long long MOD) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a % MOD;
  else {
    long long k = power_mod(a, b / 2, MOD);
    return ((k * k) % MOD * power_mod(a, b % 2, MOD)) % MOD;
  }
}
long long sum_mod(long long a, long long b, long long MOD) {
  return (a + b) % MOD;
}
long long mul_mod(long long a, long long b, long long MOD) {
  return (a * b) % MOD;
}
long long ord(char a) { return a; }
char chr(long long a) { return a; }
long long strtoint(string s) {
  long long ans = 0;
  for (long long i = 0; i < s.size(); ++i) {
    ans *= 10;
    ans += ord(s[i]) - 48;
  }
  return ans;
}
string rev_string(string s) {
  string ans = "";
  for (long long i = s.size(); i >= 0; --i) {
    ans += s[i];
  }
  return ans;
}
string inttostr(long long a) {
  string ans = "", ans1 = "";
  while (a > 0) {
    ans += chr(a + 48);
    a /= 10;
  }
  for (long long i = ans.size() - 1; i >= 0; --i) {
    ans1 += ans[i];
  }
  return ans1;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long nok(long long a, long long b) { return a * b / gcd(a, b); }
long long center;
long long n;
vector<vector<pair<long long, long long> > > ar;
bool used[800000];
vector<long long> steck;
long long cur_max = 0, first_max = 0, second_max = 0;
bool ans[800000];
long long dfs(long long v) {
  used[v] = true;
  long long ans = 1;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (!used[ar[v][i].first]) {
      ar[v][i].second = dfs(ar[v][i].first);
      ans += ar[v][i].second;
    }
  }
  return ans;
}
void dfs1(long long v) {
  used[v] = true;
  long long len = 0;
  for (long long i = 0; i < ar[v].size(); ++i) {
    len += ar[v][i].second;
  }
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (used[ar[v][i].first]) {
      ar[v][i].second = n - len - 1;
    }
  }
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (!used[ar[v][i].first]) dfs1(ar[v][i].first);
  }
}
void dfs2(long long v) {
  used[v] = true;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (used[ar[v][i].first]) continue;
    if (ar[v][i].second > n / 2) {
      dfs2(ar[v][i].first);
      return;
    }
  }
  center = v;
}
void dfs3(long long v) {
  steck.push_back(v);
  used[v] = true;
  long long ma = 0;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (ar[v][i].second > ma) ma = ar[v][i].second;
  }
  ans[v] = ma - cur_max <= n / 2;
  if ((ma > cur_max) && (ma <= n / 2)) cur_max = ma;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (!used[ar[v][i].first]) dfs3(ar[v][i].first);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  srand(time(0));
  cin >> n;
  ar.resize(n + 1);
  for (long long i = 0; i < n - 1; ++i) {
    long long u, v;
    cin >> u >> v;
    ar[u].push_back(make_pair(v, 0));
    ar[v].push_back(make_pair(u, 0));
  }
  dfs(1);
  for (long long i = 1; i <= n; ++i) {
    used[i] = false;
  }
  dfs1(1);
  for (long long i = 1; i <= n; ++i) {
    used[i] = false;
  }
  dfs2(1);
  for (long long i = 0; i < ar[center].size(); ++i) {
    if (ar[center][i].second > first_max) {
      second_max = first_max;
      first_max = ar[center][i].second;
    } else if (ar[center][i].second > second_max) {
      second_max = ar[center][i].second;
    }
  }
  ans[center] = true;
  for (long long i = 1; i <= n; ++i) {
    used[i] = false;
  }
  for (long long i = 0; i < ar[center].size(); ++i) {
    used[center] = true;
    for (long long i = 0; i < steck.size(); ++i) {
      used[steck[i]] = false;
    }
    steck.clear();
    if (ar[center][i].second == first_max)
      cur_max = second_max;
    else
      cur_max = first_max;
    dfs3(ar[center][i].first);
  }
  for (long long i = 1; i <= n; ++i) {
    if (ans[i])
      cout << "1 ";
    else
      cout << "0 ";
  }
}

### Prompt

Please create a solution in Cpp to the following problem:

Tree is a connected acyclic graph. Suppose you are given a tree consisting of n vertices. The vertex of this tree is called centroid if the size of each connected component that appears if this vertex is removed from the tree doesn't exceed <image>.

You are given a tree of size n and can perform no more than one edge replacement. Edge replacement is the operation of removing one edge from the tree (without deleting incident vertices) and inserting one new edge (without adding new vertices) in such a way that the graph remains a tree. For each vertex you have to determine if it's possible to make it centroid by performing no more than one edge replacement.

Input

The first line of the input contains an integer n (2 ≤ n ≤ 400 000) — the number of vertices in the tree. Each of the next n - 1 lines contains a pair of vertex indices ui and vi (1 ≤ ui, vi ≤ n) — endpoints of the corresponding edge.

Output

Print n integers. The i-th of them should be equal to 1 if the i-th vertex can be made centroid by replacing no more than one edge, and should be equal to 0 otherwise.

Examples

Input

3
1 2
2 3


Output

1 1 1 


Input

5
1 2
1 3
1 4
1 5


Output

1 0 0 0 0 

Note

In the first sample each vertex can be made a centroid. For example, in order to turn vertex 1 to centroid one have to replace the edge (2, 3) with the edge (1, 3).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long null = 0;
struct segment;
struct line;
struct point;
struct vec;
struct ray;
struct point {
  long double x, y;
  point() {}
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist_to_point(point p) {
    return sqrt((p.x - x) * (p.x - x) + (p.y - y) * (p.y - y));
  }
  bool operator<(point p) { return (x < p.x) || ((x == p.x) && (y < p.y)); }
};
struct vec {
  long double x, y;
  vec(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  vec(point a, point b) {
    x = b.x - a.x;
    y = b.y - a.y;
  }
  vec normal() {
    vec ans;
    ans.x = y;
    ans.y = -x;
    return ans;
  }
  vec opposite() {
    vec ans;
    ans.x = -x;
    ans.y = -y;
    return ans;
  }
  vec sum(vec b) {
    vec ans;
    ans.x = x + b.x;
    ans.y = y + b.y;
    return ans;
  }
  long double cross_product(vec v) { return x * v.y - v.x * y; }
  long double dot_product(vec v) { return x * v.x + y * v.y; }
  vec resize(long double size) {
    vec ans;
    ans.x = (x * size) / len();
    ans.y = (y * size) / len();
    return ans;
  }
  vec() {}
  long double len() { return sqrt(x * x + y * y); }
};
struct line {
  long double a, b, c;
  line(point a1, point b1) {
    a = a1.y - b1.y;
    b = b1.x - a1.x;
    c = -a1.x * a - a1.y * b;
  }
  line(long double a1, long double b1, long double c1) {
    a = a1;
    b = b1;
    c = c1;
  }
  line() {}
  vec normal_vec() {
    vec ans;
    ans.x = a;
    ans.y = b;
    return ans;
  }
  line normal_line(point p) {
    line ans;
    ans.a = -b;
    ans.b = a;
    ans.c = -ans.a * p.x - ans.b * p.y;
    return ans;
  }
  long double get_x(long double y1) {
    if (a == 0) return 0;
    return (-c - b * y1) / a;
  }
  long double get_y(long double x1) {
    if (b == 0) return 0;
    return (-c - a * x1) / b;
  }
  point intersection(line l) {
    point ans;
    ans.x = (-c * l.b + l.c * b) / (a * l.b - l.a * b);
    ans.y = (-a * l.c + l.a * c) / (a * l.b - l.a * b);
    return ans;
  }
  bool parallels(line l) { return a * l.b - l.a * b == 0; }
  long double dist_to_point(point p) {
    return abs((a * p.x + b * p.y + c) / (sqrt(a * a + b * b)));
  }
  long long is_inside(point p) {
    long double k = a * p.x + b * p.y + c;
    if (k < 0)
      return -1;
    else if (k == 0)
      return 0;
    return 1;
  }
};
struct segment {
  point a, b;
  segment() {}
  segment(point a1, point b1) {
    a = a1;
    b = b1;
  }
  long double len() {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  }
  bool is_inside(point p) {
    line l(a, b);
    if (l.is_inside(p) != 0) return false;
    vec v(p, a), v1(p, b);
    if (v.dot_product(v1) > 0) return false;
    return true;
  }
  long double dist_to_point(point p) {
    vec v(a, p), v1(a, b), v2(b, p), v3(b, a);
    if (v.dot_product(v1) < 0) return p.dist_to_point(a);
    if (v2.dot_product(v3) < 0) return p.dist_to_point(b);
    line l(a, b);
    return l.dist_to_point(p);
  }
  point get_center() {
    point ans;
    ans.x = (a.x + b.x) / 2;
    ans.y = (a.y + b.y) / 2;
    return ans;
  }
};
struct ray {
  point a, b;
  ray(point p, point p1) {
    a = p;
    b = p1;
  }
  ray() {}
  long double dist_to_point(point p) {
    vec v(a, p), v1(a, b);
    if (v.dot_product(v1) < 0) return a.dist_to_point(p);
    line l(a, b);
    return l.dist_to_point(p);
  }
  bool is_inside(point p) {
    line l(a, b);
    if (l.is_inside(p) != 0) return false;
    vec v(a, p), v1(a, b);
    if (v.dot_product(v1) < 0) return false;
    return true;
  }
};
struct angle {
  point a, b, c;
  angle(){};
  angle(point a1, point b1, point c1) {
    a = a1;
    b = b1;
    c = c1;
  }
  long double get_angle() {
    vec v(b, a), v1(b, c);
    return acos(v.dot_product(v1) / (v.len() * v1.len()));
  }
  long double get_grad_angle() {
    vec v(b, a), v1(b, c);
    return 180 * acos(v.dot_product(v1) / (v.len() * v1.len())) /
           3.141592653589793238462643;
  }
};
struct polygon {
  long long n;
  vector<point> points;
  long double get_area() {
    point a(0, 0);
    vec v(a, points[0]);
    long double ans = 0;
    for (long long i = 1; i < n; ++i) {
      vec v1(a, points[i]);
      ans = ans + v.cross_product(v1);
      v = v1;
    }
    vec v2(a, points[0]);
    vec v1(a, points[n - 1]);
    return abs(ans + v1.cross_product(v2)) / 2;
  }
};
struct triangle {
  point a, b, c;
  triangle() {}
  triangle(point a1, point b1, point c1) {
    a = a1;
    b = b1;
    c = c1;
  }
  long double get_area() {
    point d(0, 0);
    vec v(a, d), v1(b, d), v2(c, d);
    return (v.cross_product(v1) + v1.cross_product(v2) + v2.cross_product(v)) /
           2;
  }
  point get_center() {
    segment s(a, b), s1(a, c);
    point p = s.get_center(), p1 = s1.get_center();
    line l(a, b), l1(a, c), l2(b, c);
    l = l.normal_line(p);
    l1 = l1.normal_line(p1);
    return l.intersection(l1);
  }
  long double get_R() {
    triangle t(a, b, c);
    point p = t.get_center();
    return p.dist_to_point(a);
  }
};
long long power(long long a, long long b) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a;
  else {
    long long k = power(a, b / 2);
    return k * k * power(a, b % 2);
  }
}
long long power_mod(long long a, long long b, long long MOD) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a % MOD;
  else {
    long long k = power_mod(a, b / 2, MOD);
    return ((k * k) % MOD * power_mod(a, b % 2, MOD)) % MOD;
  }
}
long long sum_mod(long long a, long long b, long long MOD) {
  return (a + b) % MOD;
}
long long mul_mod(long long a, long long b, long long MOD) {
  return (a * b) % MOD;
}
long long ord(char a) { return a; }
char chr(long long a) { return a; }
long long strtoint(string s) {
  long long ans = 0;
  for (long long i = 0; i < s.size(); ++i) {
    ans *= 10;
    ans += ord(s[i]) - 48;
  }
  return ans;
}
string rev_string(string s) {
  string ans = "";
  for (long long i = s.size(); i >= 0; --i) {
    ans += s[i];
  }
  return ans;
}
string inttostr(long long a) {
  string ans = "", ans1 = "";
  while (a > 0) {
    ans += chr(a + 48);
    a /= 10;
  }
  for (long long i = ans.size() - 1; i >= 0; --i) {
    ans1 += ans[i];
  }
  return ans1;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long nok(long long a, long long b) { return a * b / gcd(a, b); }
long long center;
long long n;
vector<vector<pair<long long, long long> > > ar;
bool used[800000];
vector<long long> steck;
long long cur_max = 0, first_max = 0, second_max = 0;
bool ans[800000];
long long dfs(long long v) {
  used[v] = true;
  long long ans = 1;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (!used[ar[v][i].first]) {
      ar[v][i].second = dfs(ar[v][i].first);
      ans += ar[v][i].second;
    }
  }
  return ans;
}
void dfs1(long long v) {
  used[v] = true;
  long long len = 0;
  for (long long i = 0; i < ar[v].size(); ++i) {
    len += ar[v][i].second;
  }
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (used[ar[v][i].first]) {
      ar[v][i].second = n - len - 1;
    }
  }
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (!used[ar[v][i].first]) dfs1(ar[v][i].first);
  }
}
void dfs2(long long v) {
  used[v] = true;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (used[ar[v][i].first]) continue;
    if (ar[v][i].second > n / 2) {
      dfs2(ar[v][i].first);
      return;
    }
  }
  center = v;
}
void dfs3(long long v) {
  steck.push_back(v);
  used[v] = true;
  long long ma = 0;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (ar[v][i].second > ma) ma = ar[v][i].second;
  }
  ans[v] = ma - cur_max <= n / 2;
  if ((ma > cur_max) && (ma <= n / 2)) cur_max = ma;
  for (long long i = 0; i < ar[v].size(); ++i) {
    if (!used[ar[v][i].first]) dfs3(ar[v][i].first);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  srand(time(0));
  cin >> n;
  ar.resize(n + 1);
  for (long long i = 0; i < n - 1; ++i) {
    long long u, v;
    cin >> u >> v;
    ar[u].push_back(make_pair(v, 0));
    ar[v].push_back(make_pair(u, 0));
  }
  dfs(1);
  for (long long i = 1; i <= n; ++i) {
    used[i] = false;
  }
  dfs1(1);
  for (long long i = 1; i <= n; ++i) {
    used[i] = false;
  }
  dfs2(1);
  for (long long i = 0; i < ar[center].size(); ++i) {
    if (ar[center][i].second > first_max) {
      second_max = first_max;
      first_max = ar[center][i].second;
    } else if (ar[center][i].second > second_max) {
      second_max = ar[center][i].second;
    }
  }
  ans[center] = true;
  for (long long i = 1; i <= n; ++i) {
    used[i] = false;
  }
  for (long long i = 0; i < ar[center].size(); ++i) {
    used[center] = true;
    for (long long i = 0; i < steck.size(); ++i) {
      used[steck[i]] = false;
    }
    steck.clear();
    if (ar[center][i].second == first_max)
      cur_max = second_max;
    else
      cur_max = first_max;
    dfs3(ar[center][i].first);
  }
  for (long long i = 1; i <= n; ++i) {
    if (ans[i])
      cout << "1 ";
    else
      cout << "0 ";
  }
}

```