#include <bits/stdc++.h>
using namespace std;
inline namespace Infinity {
inline namespace Constant {
constexpr const int eof = EOF;
constexpr const int maxint = INT_MAX;
constexpr const long long maxll = LLONG_MAX;
constexpr const double eps = DBL_EPSILON;
}  // namespace Constant
inline namespace TypeDefine {
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
template <typename T = int>
using Pair = pair<T, T>;
template <typename T = int>
using PairList = vector<Pair<T>>;
template <typename T = vector<int>>
using Iter = typename T::iterator;
}  // namespace TypeDefine
inline namespace IO {
const char LF = '\n';
const char SP = ' ';
int dbl_prec = 10;
int ldbl_prec = 18;
inline void write(const int n) { printf("%d", n); }
inline void write(const unsigned n) { printf("%u", n); }
inline void write(const long long n) { printf("%lld", n); }
inline void write(const unsigned long long n) { printf("%lld", n); }
inline void write(const int64_t n) { printf("%" PRId64, n); }
inline void write(const uint64_t n) { printf("%" PRIu64, n); }
inline void write(const double a) { printf("%.*f", dbl_prec, a); }
inline void write(const long double a) { printf("%.*Lf", ldbl_prec, a); }
inline void write(const char c) { printf("%c", c); }
inline void write(const char s[]) { printf("%s", s); }
inline void write(const string &s) { printf("%s", s.data()); }
template <typename T>
inline void writeSP(const T a) {
  write(a);
  write(SP);
}
template <typename T, typename U>
inline void write(const pair<T, U> &p) {
  writeSP(p.first);
  write(p.second);
}
template <class T>
inline void write(const T a) {
  for (auto i = a.begin(); i != a.end(); i++) {
    if (i != a.begin()) write(SP);
    write(*i);
  }
}
template <typename T>
inline void write(initializer_list<T> list) {
  for (auto i = list.begin(); i != list.end(); i++) {
    if (i != list.begin()) write(SP);
    write(*i);
  }
}
template <typename T>
inline void writer(T begin, T end) {
  for (write(*begin++); begin != end; ++begin) write(SP), write(*begin);
}
inline void writeln() { write(LF); }
inline void writeSP() { write(SP); }
template <typename T>
inline void writeln(const T &a) {
  write(a);
  write(LF);
}
template <typename T>
inline void writeln(initializer_list<T> list) {
  for (auto i = list.begin(); i != list.end(); i++) {
    if (i != list.begin()) write(SP);
    write(*i);
  }
  write(LF);
}
template <class T>
inline void writelns(const T &a) {
  for (auto n : a) writeln(n);
}
template <typename T, typename... types>
inline void write(const T &a, const types &...args) {
  write(a);
  write(args...);
}
template <typename... types>
inline void writeln(const types &...args) {
  write(args...);
  write(LF);
}
template <typename... types>
inline void writeSP(const types &...args) {
  write(args...);
  write(SP);
}
inline void writelnYN(bool b) { writeln(b ? "YES" : "NO"); }
inline void writelnyn(bool b) { writeln(b ? "Yes" : "No"); }
string caseN(int n, bool sharp = true, bool space = true) {
  return string("Case ") + (sharp ? "#" : "") + to_string(n) + ":" +
         (space ? " " : "");
}
inline int read(int &n) { return scanf("%d", &n); }
inline int read(int64_t &n) { return scanf("%" SCNd64, &n); }
template <typename T, typename... types>
inline int read(T &n, types &...args) {
  return read(n) == eof ? eof : read(args...) + 1;
}
inline char getcc() {
  char c;
  do c = getchar();
  while (isspace(c));
  return c;
}
inline int getint() {
  int n;
  read(n);
  return n;
}
inline int64_t getll() {
  int64_t n;
  read(n);
  return n;
}
inline double getdbl() {
  double n;
  scanf("%lf", &n);
  return n;
}
inline pair<int, int> getpair() {
  pair<int, int> p;
  scanf("%d%d", &p.first, &p.second);
  return p;
}
inline vector<int> getints(int n) {
  vector<int> v(n);
  for (int &i : v) i = getint();
  return v;
}
inline vector<pair<int, int>> getpairs(int n) {
  vector<pair<int, int>> v(n);
  for (pair<int, int> &p : v) {
    p = getpair();
  }
  return v;
}
inline void read(string &str, unsigned size) {
  char s[++size];
  scanf("%s", s);
  str.assign(s);
}
inline string getstr(unsigned size = 0x100000) {
  string s;
  read(s, size);
  return s;
}
inline string getln(unsigned size = 0x100000) {
  char s[++size];
  scanf("%[^\n]", s);
  getchar();
  return s;
}
}  // namespace IO
inline namespace BattleLab {
class Range {
  class RangeIterator {
   public:
    RangeIterator(int current = 0, int step = 1)
        : current(current), step(step) {}
    bool operator!=(const RangeIterator &iterator) const {
      return current < iterator.current;
    }
    int operator*() const { return current; }
    RangeIterator operator++() { return {current += step, step}; }

   protected:
    int current, step;
  };

 public:
  Range(int to, int from = 0, int step = 1) : from(from), to(to), step(step) {}
  RangeIterator begin() const { return {from, step}; }
  RangeIterator end() const { return {to, step}; }

 protected:
  int from, to, step;
};
Range range(int to) { return {to}; }
Range range(int from, int to) { return {to, from}; }
Range range(int from, int to, int step) { return {to, from, step}; }
}  // namespace BattleLab
inline namespace Miscelleneous {
inline constexpr int ctoi(const char c) { return c - '0'; }
inline constexpr char itoc(const int n) { return n + '0'; }
inline int dtoi(const double d) { return round(d); }
template <typename T>
inline constexpr bool in(T x, T l, T r) {
  return l <= x && x <= r;
}
template <typename T>
inline constexpr T tristate(int val, T nag, T zero, T pos) {
  return val > 0 ? pos : val < 0 ? nag : zero;
}
template <class T>
inline int size(const T &a) {
  return a.size();
}
template <class T>
inline void sort(T &a) {
  sort(a.begin(), a.end());
}
template <class T1, class T2>
inline void sort(T1 &a, T2 comp) {
  sort(a.begin(), a.end(), comp);
}
template <class T1, typename T2>
inline int lbound(const T1 &a, const T2 k) {
  return lower_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, typename T2>
inline int ubound(const T1 &a, const T2 k) {
  return upper_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, class T2>
inline int count(T1 &a, T2 k) {
  return ubound(a, k) - lbound(a, k);
}
template <typename T>
inline void clear(T &a) {
  memset(a, 0, sizeof a);
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
long long qpow(long long a, long long b, long long c) {
  return b ? qpow(a * a % c, b >> 1, c) * (b & 1 ? a : 1) % c : 1;
}
template <typename T>
T exGcd(T a, T b, T &x, T &y) {
  T d = a;
  if (b) {
    d = exGcd(b, a % b, y, x);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
template <typename T>
inline constexpr T mps(T l, T r, T k) {
  return ((r - (r % k + k) % k) - (l + (k - l % k) % k)) / k + 1;
}
template <typename T>
inline constexpr T sgn(T a) {
  return a ? a > 0 ? 1 : -1 : 0;
}
template <typename T>
inline constexpr T sq(T a) {
  return a * a;
}
template <typename T>
inline constexpr bool odd(T a) {
  return bool(a % 2);
}
template <typename T>
inline constexpr bool even(T a) {
  return !bool(a % 2);
}
template <typename T1, typename T2>
inline constexpr T1 smod(T1 x, T2 m) {
  return x > m ? x - m : x + m < m ? x + m : x;
}
vector<int> repetend(vector<int> a) {
  vector<int> p(a.size(), -1);
  for (unsigned i = 0; i < a.size(); i++)
    if (p[i] == -1) {
      int c = 1;
      for (unsigned j = a[i]; j != i; j = a[j]) ++c;
      p[i] = c;
      for (unsigned j = a[i]; j != i; j = a[j]) p[j] = c;
    }
  return p;
}
template <typename T>
inline constexpr T lmiddle(T first, T last) {
  return first + (last - first) / 2;
}
template <typename T>
inline constexpr T rmiddle(T first, T last) {
  return last - (last - first) / 2;
}
template <typename T, typename F>
T dichotomy(T l, T r, F check, T prec = 1) {
  while (r - l > prec) {
    T m = lmiddle(l, r);
    (check(m) ? l : r) = m;
  }
  return l;
}
template <typename T, typename F>
T dichotomy2(T l, T r, F check, T prec = 1) {
  while (r - l > prec) {
    T m = rmiddle(l, r);
    (check(m) ? r : l) = m;
  }
  return r;
}
bool contains(const string &s, const string &t) {
  return s.find(t) != string::npos;
}
template <typename T>
bool contains(const T &s, typename T::value_type t) {
  for (typename T::value_type c : s)
    if (c == t) return true;
  return false;
}
template <typename T>
bool contains(const initializer_list<T> s, T t) {
  return find(s.begin(), s.end(), t) != s.end();
}
}  // namespace Miscelleneous
}  // namespace Infinity
class Tree {
 public:
  Tree(unsigned n) : n(n), adj(n) {}
  void addDirected(int u, int v) { adj[u].push_back(v); }
  void addUndirected(int u, int v) {
    addDirected(u, v);
    addDirected(v, u);
  }

 protected:
  int n;
  vector<vector<int>> adj;
};
class Centroids : public Tree {
 public:
  Centroids(unsigned n) : Tree(n), ss(n), sc(n), sp(n) {}
  vector<int> solve() {
    r.assign(n, 1);
    prepare1(0, -1);
    prepare2(0, -1);
    return r;
  }

 private:
  void update(int &a, int b) {
    if (b <= n / 2 && b > a) {
      a = b;
    }
  }
  void prepare1(int u, int p) {
    ss[u] = 1;
    for (int v : adj[u]) {
      if (v != p) {
        prepare1(v, u);
        if (ss[v] - sc[v] > n / 2) {
          r[u] = 0;
        }
        ss[u] += ss[v];
        update(sc[u], sc[v]);
        update(sc[u], ss[v]);
      }
    }
    update(sc[u], ss[u]);
  }
  void prepare2(int u, int p) {
    update(sp[u], n - ss[u]);
    update(sp[u], sp[p]);
    if (n - ss[u] - sp[u] > n / 2) {
      r[u] = 0;
    }
    int pm = 0;
    for (auto i = adj[u].begin(); i != adj[u].end(); i++) {
      int v = *i;
      if (v != p) {
        update(sp[v], pm);
        update(pm, sc[v]);
      }
    }
    pm = 0;
    for (auto i = adj[u].rbegin(); i != adj[u].rend(); i++) {
      int v = *i;
      if (v != p) {
        update(sp[v], pm);
        update(pm, sc[v]);
        prepare2(v, u);
      }
    }
  }

 protected:
  vector<int> ss, sc, sp, r;
};
int main() {
  int n = getint();
  Centroids c(n);
  for (int i = 0; i < n - 1; i++) {
    c.addUndirected(getint() - 1, getint() - 1);
  }
  writeln(c.solve());
  return 0;
}

### Prompt

Your task is to create a Cpp solution 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;
inline namespace Infinity {
inline namespace Constant {
constexpr const int eof = EOF;
constexpr const int maxint = INT_MAX;
constexpr const long long maxll = LLONG_MAX;
constexpr const double eps = DBL_EPSILON;
}  // namespace Constant
inline namespace TypeDefine {
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
template <typename T = int>
using Pair = pair<T, T>;
template <typename T = int>
using PairList = vector<Pair<T>>;
template <typename T = vector<int>>
using Iter = typename T::iterator;
}  // namespace TypeDefine
inline namespace IO {
const char LF = '\n';
const char SP = ' ';
int dbl_prec = 10;
int ldbl_prec = 18;
inline void write(const int n) { printf("%d", n); }
inline void write(const unsigned n) { printf("%u", n); }
inline void write(const long long n) { printf("%lld", n); }
inline void write(const unsigned long long n) { printf("%lld", n); }
inline void write(const int64_t n) { printf("%" PRId64, n); }
inline void write(const uint64_t n) { printf("%" PRIu64, n); }
inline void write(const double a) { printf("%.*f", dbl_prec, a); }
inline void write(const long double a) { printf("%.*Lf", ldbl_prec, a); }
inline void write(const char c) { printf("%c", c); }
inline void write(const char s[]) { printf("%s", s); }
inline void write(const string &s) { printf("%s", s.data()); }
template <typename T>
inline void writeSP(const T a) {
  write(a);
  write(SP);
}
template <typename T, typename U>
inline void write(const pair<T, U> &p) {
  writeSP(p.first);
  write(p.second);
}
template <class T>
inline void write(const T a) {
  for (auto i = a.begin(); i != a.end(); i++) {
    if (i != a.begin()) write(SP);
    write(*i);
  }
}
template <typename T>
inline void write(initializer_list<T> list) {
  for (auto i = list.begin(); i != list.end(); i++) {
    if (i != list.begin()) write(SP);
    write(*i);
  }
}
template <typename T>
inline void writer(T begin, T end) {
  for (write(*begin++); begin != end; ++begin) write(SP), write(*begin);
}
inline void writeln() { write(LF); }
inline void writeSP() { write(SP); }
template <typename T>
inline void writeln(const T &a) {
  write(a);
  write(LF);
}
template <typename T>
inline void writeln(initializer_list<T> list) {
  for (auto i = list.begin(); i != list.end(); i++) {
    if (i != list.begin()) write(SP);
    write(*i);
  }
  write(LF);
}
template <class T>
inline void writelns(const T &a) {
  for (auto n : a) writeln(n);
}
template <typename T, typename... types>
inline void write(const T &a, const types &...args) {
  write(a);
  write(args...);
}
template <typename... types>
inline void writeln(const types &...args) {
  write(args...);
  write(LF);
}
template <typename... types>
inline void writeSP(const types &...args) {
  write(args...);
  write(SP);
}
inline void writelnYN(bool b) { writeln(b ? "YES" : "NO"); }
inline void writelnyn(bool b) { writeln(b ? "Yes" : "No"); }
string caseN(int n, bool sharp = true, bool space = true) {
  return string("Case ") + (sharp ? "#" : "") + to_string(n) + ":" +
         (space ? " " : "");
}
inline int read(int &n) { return scanf("%d", &n); }
inline int read(int64_t &n) { return scanf("%" SCNd64, &n); }
template <typename T, typename... types>
inline int read(T &n, types &...args) {
  return read(n) == eof ? eof : read(args...) + 1;
}
inline char getcc() {
  char c;
  do c = getchar();
  while (isspace(c));
  return c;
}
inline int getint() {
  int n;
  read(n);
  return n;
}
inline int64_t getll() {
  int64_t n;
  read(n);
  return n;
}
inline double getdbl() {
  double n;
  scanf("%lf", &n);
  return n;
}
inline pair<int, int> getpair() {
  pair<int, int> p;
  scanf("%d%d", &p.first, &p.second);
  return p;
}
inline vector<int> getints(int n) {
  vector<int> v(n);
  for (int &i : v) i = getint();
  return v;
}
inline vector<pair<int, int>> getpairs(int n) {
  vector<pair<int, int>> v(n);
  for (pair<int, int> &p : v) {
    p = getpair();
  }
  return v;
}
inline void read(string &str, unsigned size) {
  char s[++size];
  scanf("%s", s);
  str.assign(s);
}
inline string getstr(unsigned size = 0x100000) {
  string s;
  read(s, size);
  return s;
}
inline string getln(unsigned size = 0x100000) {
  char s[++size];
  scanf("%[^\n]", s);
  getchar();
  return s;
}
}  // namespace IO
inline namespace BattleLab {
class Range {
  class RangeIterator {
   public:
    RangeIterator(int current = 0, int step = 1)
        : current(current), step(step) {}
    bool operator!=(const RangeIterator &iterator) const {
      return current < iterator.current;
    }
    int operator*() const { return current; }
    RangeIterator operator++() { return {current += step, step}; }

   protected:
    int current, step;
  };

 public:
  Range(int to, int from = 0, int step = 1) : from(from), to(to), step(step) {}
  RangeIterator begin() const { return {from, step}; }
  RangeIterator end() const { return {to, step}; }

 protected:
  int from, to, step;
};
Range range(int to) { return {to}; }
Range range(int from, int to) { return {to, from}; }
Range range(int from, int to, int step) { return {to, from, step}; }
}  // namespace BattleLab
inline namespace Miscelleneous {
inline constexpr int ctoi(const char c) { return c - '0'; }
inline constexpr char itoc(const int n) { return n + '0'; }
inline int dtoi(const double d) { return round(d); }
template <typename T>
inline constexpr bool in(T x, T l, T r) {
  return l <= x && x <= r;
}
template <typename T>
inline constexpr T tristate(int val, T nag, T zero, T pos) {
  return val > 0 ? pos : val < 0 ? nag : zero;
}
template <class T>
inline int size(const T &a) {
  return a.size();
}
template <class T>
inline void sort(T &a) {
  sort(a.begin(), a.end());
}
template <class T1, class T2>
inline void sort(T1 &a, T2 comp) {
  sort(a.begin(), a.end(), comp);
}
template <class T1, typename T2>
inline int lbound(const T1 &a, const T2 k) {
  return lower_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, typename T2>
inline int ubound(const T1 &a, const T2 k) {
  return upper_bound(a.begin(), a.end(), k) - a.begin();
}
template <class T1, class T2>
inline int count(T1 &a, T2 k) {
  return ubound(a, k) - lbound(a, k);
}
template <typename T>
inline void clear(T &a) {
  memset(a, 0, sizeof a);
}
template <typename T>
T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
long long qpow(long long a, long long b, long long c) {
  return b ? qpow(a * a % c, b >> 1, c) * (b & 1 ? a : 1) % c : 1;
}
template <typename T>
T exGcd(T a, T b, T &x, T &y) {
  T d = a;
  if (b) {
    d = exGcd(b, a % b, y, x);
    y -= a / b * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
template <typename T>
inline constexpr T mps(T l, T r, T k) {
  return ((r - (r % k + k) % k) - (l + (k - l % k) % k)) / k + 1;
}
template <typename T>
inline constexpr T sgn(T a) {
  return a ? a > 0 ? 1 : -1 : 0;
}
template <typename T>
inline constexpr T sq(T a) {
  return a * a;
}
template <typename T>
inline constexpr bool odd(T a) {
  return bool(a % 2);
}
template <typename T>
inline constexpr bool even(T a) {
  return !bool(a % 2);
}
template <typename T1, typename T2>
inline constexpr T1 smod(T1 x, T2 m) {
  return x > m ? x - m : x + m < m ? x + m : x;
}
vector<int> repetend(vector<int> a) {
  vector<int> p(a.size(), -1);
  for (unsigned i = 0; i < a.size(); i++)
    if (p[i] == -1) {
      int c = 1;
      for (unsigned j = a[i]; j != i; j = a[j]) ++c;
      p[i] = c;
      for (unsigned j = a[i]; j != i; j = a[j]) p[j] = c;
    }
  return p;
}
template <typename T>
inline constexpr T lmiddle(T first, T last) {
  return first + (last - first) / 2;
}
template <typename T>
inline constexpr T rmiddle(T first, T last) {
  return last - (last - first) / 2;
}
template <typename T, typename F>
T dichotomy(T l, T r, F check, T prec = 1) {
  while (r - l > prec) {
    T m = lmiddle(l, r);
    (check(m) ? l : r) = m;
  }
  return l;
}
template <typename T, typename F>
T dichotomy2(T l, T r, F check, T prec = 1) {
  while (r - l > prec) {
    T m = rmiddle(l, r);
    (check(m) ? r : l) = m;
  }
  return r;
}
bool contains(const string &s, const string &t) {
  return s.find(t) != string::npos;
}
template <typename T>
bool contains(const T &s, typename T::value_type t) {
  for (typename T::value_type c : s)
    if (c == t) return true;
  return false;
}
template <typename T>
bool contains(const initializer_list<T> s, T t) {
  return find(s.begin(), s.end(), t) != s.end();
}
}  // namespace Miscelleneous
}  // namespace Infinity
class Tree {
 public:
  Tree(unsigned n) : n(n), adj(n) {}
  void addDirected(int u, int v) { adj[u].push_back(v); }
  void addUndirected(int u, int v) {
    addDirected(u, v);
    addDirected(v, u);
  }

 protected:
  int n;
  vector<vector<int>> adj;
};
class Centroids : public Tree {
 public:
  Centroids(unsigned n) : Tree(n), ss(n), sc(n), sp(n) {}
  vector<int> solve() {
    r.assign(n, 1);
    prepare1(0, -1);
    prepare2(0, -1);
    return r;
  }

 private:
  void update(int &a, int b) {
    if (b <= n / 2 && b > a) {
      a = b;
    }
  }
  void prepare1(int u, int p) {
    ss[u] = 1;
    for (int v : adj[u]) {
      if (v != p) {
        prepare1(v, u);
        if (ss[v] - sc[v] > n / 2) {
          r[u] = 0;
        }
        ss[u] += ss[v];
        update(sc[u], sc[v]);
        update(sc[u], ss[v]);
      }
    }
    update(sc[u], ss[u]);
  }
  void prepare2(int u, int p) {
    update(sp[u], n - ss[u]);
    update(sp[u], sp[p]);
    if (n - ss[u] - sp[u] > n / 2) {
      r[u] = 0;
    }
    int pm = 0;
    for (auto i = adj[u].begin(); i != adj[u].end(); i++) {
      int v = *i;
      if (v != p) {
        update(sp[v], pm);
        update(pm, sc[v]);
      }
    }
    pm = 0;
    for (auto i = adj[u].rbegin(); i != adj[u].rend(); i++) {
      int v = *i;
      if (v != p) {
        update(sp[v], pm);
        update(pm, sc[v]);
        prepare2(v, u);
      }
    }
  }

 protected:
  vector<int> ss, sc, sp, r;
};
int main() {
  int n = getint();
  Centroids c(n);
  for (int i = 0; i < n - 1; i++) {
    c.addUndirected(getint() - 1, getint() - 1);
  }
  writeln(c.solve());
  return 0;
}

```