Problem: There are n students in Polycarp's class (including himself). A few days ago all students wrote an essay "My best friend". Each student's essay was dedicated to one of the students of class, to his/her best friend. Note that student b's best friend is not necessarily student a, if a's best friend is b.

And now the teacher leads the whole class to the museum of the history of sports programming. Exciting stories of legendary heroes await the students: tourist, Petr, tomek, SnapDragon — that's who they will hear about!

The teacher decided to divide students into pairs so that each pair consisted of a student and his best friend. She may not be able to split all the students into pairs, it's not a problem — she wants to pick out the maximum number of such pairs. If there is more than one variant of doing so, she wants to pick out the pairs so that there were as much boy-girl pairs as possible. Of course, each student must not be included in more than one pair.

Input

The first line contains an integer n (2 ≤ n ≤ 105), n is the number of students per class. Next, n lines contain information about the students, one per line. Each line contains two integers fi, si (1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2), where fi is the number of i-th student's best friend and si denotes the i-th pupil's sex (si = 1 for a boy and si = 2 for a girl).

Output

Print on the first line two numbers t, e, where t is the maximum number of formed pairs, and e is the maximum number of boy-girl type pairs among them. Then print t lines, each line must contain a pair ai, bi (1 ≤ ai, bi ≤ n), they are numbers of pupils in the i-th pair. Print the pairs in any order. Print the numbers in pairs in any order. If there are several solutions, output any of them.

Examples

Input

5
5 2
3 2
5 1
2 1
4 2


Output

2 2
5 3
4 2


Input

6
5 2
3 2
5 1
2 1
4 2
3 1


Output

3 1
4 2
5 1
3 6


Input

8
2 2
3 2
5 1
3 1
6 1
5 1
8 2
7 1


Output

4 1
5 6
3 4
2 1
7 8

Note

The picture corresponds to the first sample. On the picture rhomb stand for boys, squares stand for girls, arrows lead from a pupil to his/her best friend. Bold non-dashed arrows stand for pairs in the answer. 

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
 public:
  explicit DisjointSet(int n) {
    whichset_ = vector<int>(n);
    height_ = vector<int>(n, 1);
    for (int i = 0; i < n; ++i) whichset_[i] = i;
  }
  int Find(int node) {
    if (whichset_[node] == node) return node;
    return (whichset_[node] = Find(whichset_[node]));
  }
  void Merge(int first_node, int second_node) {
    int h1 = height_[Find(first_node)];
    int h2 = height_[Find(second_node)];
    if (h1 < h2) {
      whichset_[Find(first_node)] = Find(second_node);
      return;
    }
    whichset_[Find(second_node)] = Find(first_node);
    if (h2 < h1) return;
    ++height_[Find(second_node)];
  }

 private:
  vector<int> whichset_;
  vector<int> height_;
};
class Graph {
 public:
  virtual ~Graph(){};
  virtual void Simplify(){};
};
class UnweightedGraph : public Graph {
 public:
  UnweightedGraph(int number_of_nodes) : adj_(number_of_nodes) {}
  UnweightedGraph& operator=(const UnweightedGraph& input_graph) {
    adj_ = vector<vector<int> >(((int)input_graph.adj_.size()));
    for (int(i) = 0; (i) < (((int)input_graph.adj_.size())); ++(i))
      for (typeof((input_graph.adj_[i]).begin()) j =
               (input_graph.adj_[i]).begin();
           j != (input_graph.adj_[i]).end(); j++)
        this->AddEdge(i, *j);
    return *this;
  }
  virtual void AddEdge(int from, int to) { adj_[from].push_back(to); }
  virtual int Size() { return adj_.size(); }
  vector<vector<int> > adj_;
};
class UndirectedUnweightedGraph : public UnweightedGraph {
 public:
  UndirectedUnweightedGraph(int number_of_nodes)
      : UnweightedGraph(number_of_nodes) {}
  virtual void AddEdge(int from, int to) {
    UnweightedGraph::AddEdge(from, to);
    UnweightedGraph::AddEdge(to, from);
  }
};
class GraphOptimizedDisjointSet {
 public:
  explicit GraphOptimizedDisjointSet(int n) {
    whichset_ = vector<int>(n);
    node_count_ = vector<int>(n, 1);
    for (int i = 0; i < n; ++i) whichset_[i] = i;
  }
  int Find(int node) {
    if (whichset_[node] == node) return node;
    return (whichset_[node] = Find(whichset_[node]));
  }
  int Merge(int first_node, int second_node) {
    if (node_count_[Find(first_node)] < node_count_[Find(second_node)]) {
      whichset_[Find(first_node)] = Find(second_node);
      node_count_[Find(second_node)] += node_count_[Find(first_node)];
      return 1;
    }
    whichset_[Find(second_node)] = Find(first_node);
    node_count_[Find(first_node)] += node_count_[Find(second_node)];
    return 0;
  }

 private:
  mutable vector<int> whichset_;
  vector<int> node_count_;
};
vector<int> SequenceSimplify(vector<int> seq) {
  int lowest = 0;
  vector<int> disort = seq;
  sort(disort.begin(), disort.end());
  disort.erase(unique(disort.begin(), disort.end()), disort.end());
  for (int(i) = 0; (i) < (((int)seq.size())); ++(i)) {
    seq[i] =
        (lower_bound(disort.begin(), disort.end(), seq[i]) - disort.begin()) +
        lowest;
  }
  return seq;
}
class MergeableUnweightedGraph : public UnweightedGraph {
 public:
  explicit MergeableUnweightedGraph(int number_of_nodes)
      : UnweightedGraph(number_of_nodes),
        disjoint_set_(number_of_nodes),
        deleted_edges_count_(0),
        is_simplified_(0),
        is_n_changed_(1) {}
  virtual void AddEdge(int from, int to) {
    is_simplified_ = 0;
    UnweightedGraph::AddEdge(from, to);
  }
  void Merge(int first_node, int second_node);
  int Find(int node) {
    if (!is_simplified_) Simplify();
    return second_map_[node];
  }
  int Size() {
    if (!is_n_changed_) return n_;
    is_n_changed_ = 0;
    n_ = 0;
    for (int(i) = 0; (i) < (((int)adj_.size())); ++(i))
      if (disjoint_set_.Find(i) == i) ++n_;
    return n_;
  }
  template <class cInType>
  void MoveData(cInType* input_graph);
  virtual void Simplify();
  int DeletedEdgesCount() {
    if (!is_simplified_) Simplify();
    return deleted_edges_count_;
  }

 private:
  GraphOptimizedDisjointSet disjoint_set_;
  vector<int> second_map_;
  int deleted_edges_count_;
  int is_simplified_;
  int is_n_changed_;
  int n_;
};
void MergeableUnweightedGraph::Merge(int first_node, int second_node) {
  is_simplified_ = 0;
  is_n_changed_ = 1;
  int real_first = disjoint_set_.Find(first_node);
  int real_second = disjoint_set_.Find(second_node);
  if (real_first == real_second) return;
  if (!disjoint_set_.Merge(real_first, real_second))
    swap(real_first, real_second);
  for (typeof((adj_[real_first]).begin()) i = (adj_[real_first]).begin();
       i != (adj_[real_first]).end(); i++) {
    if (disjoint_set_.Find((*i)) == disjoint_set_.Find(real_first)) {
      ++deleted_edges_count_;
      continue;
    }
    adj_[real_second].push_back(disjoint_set_.Find(*i));
  }
  adj_[real_first].clear();
  return;
}
template <class cInType>
void MergeableUnweightedGraph::MoveData(cInType* input_graph) {
  if (!is_simplified_) Simplify();
  (*input_graph) = cInType(Size());
  for (int(i) = 0; (i) < (((int)adj_.size())); ++(i))
    for (typeof((adj_[i]).begin()) j = (adj_[i]).begin(); j != (adj_[i]).end();
         j++)
      input_graph->AddEdge(second_map_[i], second_map_[*j]);
}
void MergeableUnweightedGraph::Simplify() {
  is_simplified_ = 1;
  for (int(i) = 0; (i) < (((int)adj_.size())); ++(i))
    for (typeof((adj_[i]).begin()) j = (adj_[i]).begin(); j != (adj_[i]).end();
         j++)
      *j = disjoint_set_.Find(*j);
  for (int(i) = 0; (i) < (((int)adj_.size())); ++(i)) {
    int org = ((int)adj_[i].size());
    adj_[i].erase(
        remove_if(adj_[i].begin(), adj_[i].end(), bind1st(equal_to<int>(), i)),
        adj_[i].end());
    deleted_edges_count_ += org - ((int)adj_[i].size());
  }
  vector<int> active_nodes;
  for (int(i) = 0; (i) < (((int)adj_.size())); ++(i))
    if (disjoint_set_.Find(i) == i) active_nodes.push_back(i);
  vector<int> tmp_map = SequenceSimplify(active_nodes);
  second_map_ = vector<int>(((int)adj_.size()));
  for (int(i) = 0; (i) < (((int)active_nodes.size())); ++(i))
    second_map_[active_nodes[i]] = tmp_map[i];
  for (int(i) = 0; (i) < (((int)adj_.size())); ++(i))
    second_map_[i] = second_map_[disjoint_set_.Find(i)];
}
vector<int> StronglyConnectedComponents(UnweightedGraph* graph,
                                        bool should_merge) {
  stack<int> urutan;
  DisjointSet ds(graph->Size());
  stack<pair<int, int> > ngurut;
  vector<int> sudah(graph->Size(), 0);
  vector<int> adadiurutan(graph->Size(), 0);
  for (int i = 0; i < graph->Size(); i++) {
    if (sudah[i]) continue;
    urutan.push(i);
    ngurut.push(make_pair(i, 0));
    adadiurutan[i] = 1;
    sudah[i] = 1;
    while (!ngurut.empty()) {
      int id = ngurut.top().first;
      int val = ngurut.top().second;
      ngurut.pop();
      if (val == (int)graph->adj_[id].size()) {
        while (!urutan.empty() && urutan.top() == id) urutan.pop();
        adadiurutan[ds.Find(id)] = 0;
        if (!urutan.empty()) adadiurutan[ds.Find(urutan.top())] = 1;
        continue;
      }
      ngurut.push(make_pair(id, val + 1));
      int next = graph->adj_[id][val];
      if (sudah[next] && !adadiurutan[ds.Find(next)]) continue;
      if (!sudah[next]) {
        sudah[next] = 1;
        urutan.push(next);
        ngurut.push(make_pair(next, 0));
        adadiurutan[next] = 1;
        continue;
      }
      if (ds.Find(id) == ds.Find(next)) continue;
      while (!urutan.empty() && ds.Find(urutan.top()) != ds.Find(next)) {
        ds.Merge(urutan.top(), next);
        urutan.pop();
      }
      adadiurutan[ds.Find(id)] = 1;
    }
  }
  vector<int> ret(graph->Size());
  for (int(i) = 0; (i) < (graph->Size()); ++(i)) ret[i] = ds.Find(i);
  if (should_merge) {
    MergeableUnweightedGraph* mwg =
        dynamic_cast<MergeableUnweightedGraph*>(graph);
    int n = graph->Size();
    for (int(i) = 0; (i) < (n); ++(i)) mwg->Merge(i, ret[i]);
  }
  return ret;
}
int sex[125000];
int fri[125000];
long long getCost(int i, int j) {
  return 1000000LL + (long long)(sex[i] != sex[j]);
}
set<pair<int, int> > edges;
vector<int> adj[125000];
vector<long long> cost[125000];
int parent[125000];
int parent2[125000];
long long cycdp[125000][2][2];
enum kAction { pairedWithBack, pairedWithFirst, treeAndThis, treeOnly };
kAction actfrom[125000][2][2];
pair<int, pair<int, int> > from[125000][2][2];
long long treedp[125000][2];
int backtracktree[125000][2];
int ispaired[125000][2];
vector<pair<int, int> > ret;
long long treeSolve(int node, int paired) {
  if (treedp[node][paired] != -1LL) return treedp[node][paired];
  long long best = -1LL;
  long long sumzero = 0LL;
  for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i)) {
    int nex = adj[node][i];
    if (nex == parent[node] || nex == parent2[node]) continue;
    parent[nex] = node;
    sumzero += treeSolve(nex, 0);
  }
  if (paired) {
    ispaired[node][paired] = 0;
    return treedp[node][paired] = sumzero;
  }
  best = sumzero;
  for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i)) {
    int nex = adj[node][i];
    if (nex == parent[node] || nex == parent2[node]) continue;
    long long val =
        sumzero - treeSolve(nex, 0) + treeSolve(nex, 1) + cost[node][i];
    if (val > best) {
      best = val;
      ispaired[node][paired] = 1;
      backtracktree[node][paired] = i;
    }
  }
  return treedp[node][paired] = best;
}
void treeBt(int node, int paired) {
  for (int(i) = 0; (i) < (((int)adj[node].size())); ++(i)) {
    int nex = adj[node][i];
    if (nex == parent[node] || nex == parent2[node]) continue;
    if (ispaired[node][paired] && backtracktree[node][paired] == i) {
      ret.push_back(make_pair(node + 1, nex + 1));
      treeBt(nex, 1);
    } else {
      treeBt(nex, 0);
    }
  }
  return;
}
int main() {
  for (int(i) = 0; (i) < (125000); ++(i))
    for (int(j) = 0; (j) < (2); ++(j)) {
      treedp[i][j] = -1LL;
      parent[i] = parent2[i] = -1;
    }
  int n;
  scanf("%d", &n);
  UnweightedGraph* ug = new UnweightedGraph(n);
  for (int(i) = 0; (i) < (n); ++(i)) {
    scanf("%d%d", fri + i, sex + i);
    fri[i] -= 1;
    sex[i] -= 1;
    if (!edges.count(make_pair(i, fri[i]))) {
      edges.insert(make_pair(i, fri[i]));
      ug->AddEdge(i, fri[i]);
      if (!edges.count(make_pair(fri[i], i))) {
        adj[i].push_back(fri[i]);
        adj[fri[i]].push_back(i);
      }
    }
  }
  for (int(i) = 0; (i) < (n); ++(i))
    for (int(j) = 0; (j) < (((int)adj[i].size())); ++(j))
      cost[i].push_back(getCost(i, adj[i][j]));
  vector<int> components = StronglyConnectedComponents(ug, 0);
  vector<int> count(n + 2);
  for (int(i) = 0; (i) < (((int)components.size())); ++(i))
    count[components[i]]++;
  long long kHuge = (long long)1023123123 * (long long)1023123123;
  long long valans = 0LL;
  vector<int> done(n + 2);
  for (int(i) = 0; (i) < (n); ++(i)) {
    if (count[components[i]] > 1 && !done[components[i]]) {
      done[components[i]] = 1;
      vector<int> cyc;
      cyc.push_back(i);
      int cyc_el = fri[i];
      while (cyc_el != i) {
        cyc.push_back(cyc_el);
        cyc_el = fri[cyc_el];
      }
      for (int(i) = 0; (i) < (((int)cyc.size())); ++(i)) {
        parent[cyc[i]] = cyc[(i + 1) % ((int)cyc.size())];
        parent2[cyc[i]] = cyc[(i + ((int)cyc.size()) - 1) % ((int)cyc.size())];
      }
      for (int(i) = 0; (i) < (((int)cyc.size()) + 1); ++(i))
        cycdp[i][0][0] = cycdp[i][0][1] = cycdp[i][1][0] = cycdp[i][1][1] =
            kHuge * -1LL;
      cycdp[1][1][1] = treeSolve(cyc[0], 1);
      cycdp[1][0][0] = treeSolve(cyc[0], 0);
      for (int j = 1; j < ((int)cyc.size()); ++j)
        for (int(zero) = 0; (zero) < (2); ++(zero))
          for (int(last) = 0; (last) < (2); ++(last)) {
            long long val = cycdp[j][zero][last];
            if (val == kHuge * -1LL) continue;
            long long valtes = val + treeSolve(cyc[j], 0);
            pair<int, pair<int, int> > ini =
                make_pair(j, make_pair(zero, last));
            if (valtes > cycdp[j + 1][zero][0]) {
              cycdp[j + 1][zero][0] = valtes;
              from[j + 1][zero][0] = ini;
              actfrom[j + 1][zero][0] = treeAndThis;
            }
            valtes = val + treeSolve(cyc[j], 1);
            if (valtes > cycdp[j + 1][zero][1]) {
              cycdp[j + 1][zero][1] = valtes;
              from[j + 1][zero][1] = ini;
              actfrom[j + 1][zero][1] = treeOnly;
            }
            if (last) {
              int newzero = zero;
              if (j == 1) newzero = 0;
              valtes = val + getCost(cyc[j], cyc[j - 1]) + treeSolve(cyc[j], 1);
              if (valtes > cycdp[j + 1][newzero][0]) {
                cycdp[j + 1][newzero][0] = valtes;
                from[j + 1][newzero][0] = ini;
                actfrom[j + 1][newzero][0] = pairedWithBack;
              }
            }
            if (j == ((int)cyc.size()) - 1 && zero) {
              valtes = val + getCost(cyc[j], cyc[0]) + treeSolve(cyc[j], 1);
              if (valtes > cycdp[j + 1][0][0]) {
                cycdp[j + 1][0][0] = valtes;
                from[j + 1][0][0] = ini;
                actfrom[j + 1][0][0] = pairedWithFirst;
              }
            }
          }
      long long best = -kHuge;
      int l1, l2, l3;
      l1 = ((int)cyc.size());
      for (int(j) = 0; (j) < (2); ++(j))
        for (int(k) = 0; (k) < (2); ++(k)) {
          if (cycdp[((int)cyc.size())][j][k] > best) {
            best = cycdp[((int)cyc.size())][j][k];
            l2 = j;
            l3 = k;
          }
        }
      valans += best;
      while (l1 > 1) {
        pair<int, pair<int, int> > prev = from[l1][l2][l3];
        if (actfrom[l1][l2][l3] == treeAndThis) {
          treeBt(cyc[prev.first], 0);
        } else {
          treeBt(cyc[prev.first], 1);
          if (actfrom[l1][l2][l3] == pairedWithBack) {
            ret.push_back(make_pair(cyc[prev.first - 1] + 1, cyc[l1 - 1] + 1));
          } else if (actfrom[l1][l2][l3] == pairedWithFirst) {
            ret.push_back(make_pair(cyc[prev.first] + 1, cyc[0] + 1));
          }
        }
        l1 = prev.first;
        l2 = prev.second.first;
        l3 = prev.second.second;
      }
      if (l2 == 1) {
        treeBt(cyc[0], 1);
      } else {
        treeBt(cyc[0], 0);
      }
    }
  }
  cout << valans / 1000000LL << " " << valans % 1000000LL << endl;
  for (int(i) = 0; (i) < (((int)ret.size())); ++(i)) {
    printf("%d %d\n", ret[i].first, ret[i].second);
  }
  return 0;
}