Problem: Bytelandian Tree Factory produces trees for all kinds of industrial applications. You have been tasked with optimizing the production of a certain type of tree for an especially large and important order.

The tree in question is a rooted tree with n vertices labelled with distinct integers from 0 to n - 1. The vertex labelled 0 is the root of the tree, and for any non-root vertex v the label of its parent p(v) is less than the label of v.

All trees at the factory are made from bamboo blanks. A bamboo is a rooted tree such that each vertex has exactly one child, except for a single leaf vertex with no children. The vertices of a bamboo blank can be labelled arbitrarily before its processing is started.

To process a bamboo into another tree a single type of operation can be made: choose an arbitrary non-root vertex v such that its parent p(v) is not a root either. The operation consists of changing the parent of v to its parent's parent p(p(v)). Note that parents of all other vertices remain unchanged, in particular, the subtree of v does not change.

Efficiency is crucial, hence you have to minimize the number of operations to make the desired tree from a bamboo blank. Construct any optimal sequence of operations to produce the desired tree.

Note that the labelling of the resulting tree has to coincide with the labelling of the desired tree. Formally, the labels of the roots have to be equal, and for non-root vertices with the same label the labels of their parents should be the same.

It is guaranteed that for any test present in this problem an answer exists, and further, an optimal sequence contains at most 10^6 operations. Note that any hack that does not meet these conditions will be invalid.

Input

The first line contains a single integer n — the number of vertices in the tree (2 ≤ n ≤ 10^5).

The second line contains n - 1 integers p(1), …, p(n - 1) — indices of parent vertices of 1, …, n - 1 respectively (0 ≤ p(i) < i).

Output

In the first line, print n distinct integers id_1, …, id_n — the initial labelling of the bamboo blank starting from the root vertex (0 ≤ id_i < n).

In the second line, print a single integer k — the number of operations in your sequence (0 ≤ k ≤ 10^6).

In the third line print k integers v_1, …, v_k describing operations in order. The i-th operation consists of changing p(v_i) to p(p(v_i)). Each operation should be valid, i.e. neither v_i nor p(v_i) can be the root of the tree at the moment.

Examples

Input


5
0 0 1 1


Output


0 2 1 4 3
2
1 3


Input


4
0 1 2


Output


0 1 2 3
0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
inline T floor_mod(T a, const T &b) {
  a %= b;
  if (a < 0) a += b;
  return a;
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
int n;
vector<int> p;
vector<vector<int>> g;
vector<int> heavy;
vector<int> max_depth;
void dfs(int v) {
  heavy[v] = -1;
  max_depth[v] = 0;
  for (int sub : g[v]) {
    dfs(sub);
    max_depth[v] = max(max_depth[v], max_depth[sub] + 1);
    if (heavy[v] == -1 || max_depth[heavy[v]] < max_depth[sub]) heavy[v] = sub;
  }
}
vector<int> aosnethaosnehoaseh;
vector<int> acts;
void go(int v) {
  assert(p[v] != -1 && p[p[v]] != -1);
  p[v] = p[p[v]];
  acts.push_back(v);
}
vector<int> euler;
void solve(int v) {
  euler.push_back(v);
  for (int sub : g[v]) {
    if (sub == heavy[v]) continue;
    solve(sub);
  }
  if (heavy[v] != -1) solve(heavy[v]);
}
void final(int v) {
  for (int sub : g[v]) {
    if (sub == heavy[v]) continue;
    final(sub);
  }
  if (heavy[v] != -1) final(heavy[v]);
  for (int sub : g[v]) {
    if (sub == heavy[v]) continue;
    while (p[sub] != v) {
      go(sub);
    }
  }
  if (heavy[v] != -1) {
    while (p[heavy[v]] != v) go(heavy[v]);
  }
}
signed main(signed argc, char *argv[]) {
  cin, n;
  aosnethaosnehoaseh.resize(n);
  iota(aosnethaosnehoaseh.begin(), aosnethaosnehoaseh.end(), 1);
  aosnethaosnehoaseh.back() = -1;
  p.resize(n - 1);
  cin, p;
  p.insert(p.begin(), -1);
  g.resize(n);
  max_depth.resize(n);
  heavy.resize(n);
  for (int i = 1; i < n; i++) {
    g[p[i]].push_back(i);
  }
  dfs(0);
  solve(0);
  p[euler[0]] = -1;
  for (int i = 1; i < n; i++) {
    p[euler[i]] = euler[i - 1];
  }
  smart_io::precall_print();
  cout, euler;
  final(0);
  smart_io::precall_print();
  cout, ((int)acts.size());
  smart_io::precall_print();
  cout, acts;
}