Problem: On the surface of a newly discovered planet, which we model by a plane, explorers found remains of two different civilizations in various locations. They would like to learn more about those civilizations and to explore the area they need to build roads between some of locations. But as always, there are some restrictions: 

  1. Every two locations of the same civilization are connected by a unique path of roads 
  2. No two locations from different civilizations may have road between them (explorers don't want to accidentally mix civilizations they are currently exploring) 
  3. Roads must be straight line segments
  4. Since intersections are expensive to build, they don't want any two roads to intersect (that is, only common point for any two roads may be at some of locations) 



Obviously all locations are different points in the plane, but explorers found out one more interesting information that may help you – no three locations lie on the same line!

Help explorers and find a solution for their problem, or report it is impossible.

Input

In the first line, integer n (1 ≤ n ≤ 10^3) - the number of locations discovered.

In next n lines, three integers x, y, c (0 ≤ x, y ≤ 10^4, c ∈ \{0, 1\}) - coordinates of the location and number of civilization it belongs to.

Output

In first line print number of roads that should be built.

In the following lines print all pairs of locations (their 0-based indices) that should be connected with a road.

If it is not possible to build roads such that all restrictions are met, print "Impossible". You should not print the quotation marks.

Example

Input

5
0 0 1
1 0 0
0 1 0
1 1 1
3 2 0


Output

3
1 4
4 2
3 0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
struct point_t {
  int x, y, ix, c;
  point_t(int x = 0, int y = 0, int ix = 0, int c = 0)
      : x(x), y(y), ix(ix), c(c) {}
  int operator<(const point_t& rhs) const {
    return make_pair(y, x) < make_pair(rhs.y, rhs.x);
  }
  int operator==(const point_t& rhs) const {
    return make_pair(y, x) == make_pair(rhs.y, rhs.x);
  }
  point_t operator-(const point_t& rhs) const {
    return point_t(x - rhs.x, y - rhs.y);
  }
};
long long cross(point_t a, point_t b) {
  return (long long)a.x * b.y - (long long)a.y * b.x;
}
long long area(point_t a, point_t b, point_t c) {
  return cross(a, b) + cross(b, c) + cross(c, a);
}
int inside(point_t a, point_t b, point_t c, point_t p) {
  return abs(area(a, b, c)) ==
         abs(area(p, a, b)) + abs(area(p, b, c)) + abs(area(p, c, a));
}
void ConvexHull(vector<point_t>& pts) {
  sort(pts.begin(), pts.end());
  pts.erase(unique(pts.begin(), pts.end()), pts.end());
  vector<point_t> up, dn;
  for (int i = 0; i < pts.size(); i++) {
    while (up.size() > 1 && area(up[up.size() - 2], up.back(), pts[i]) > 0)
      up.pop_back();
    while (dn.size() > 1 && area(dn[dn.size() - 2], dn.back(), pts[i]) < 0)
      dn.pop_back();
    up.push_back(pts[i]);
    dn.push_back(pts[i]);
  }
  pts = dn;
  for (int i = up.size() - 2; i >= 1; i--) pts.push_back(up[i]);
}
const int maxn = 1e3 + 5;
int n;
vector<point_t> p;
int used[maxn];
vector<pair<int, int> > res;
void solve(point_t a, point_t b, point_t c, vector<point_t> pts) {
  for (point_t p : {a, b, c}) used[p.ix] = 1;
  vector<point_t> npts;
  for (point_t p : pts) {
    if (inside(a, b, c, p) && !used[p.ix]) {
      npts.push_back(p);
    }
  }
  pts = npts;
  vector<point_t> g[2];
  for (point_t p : {a, b, c}) {
    g[p.c].push_back(p);
  }
  if (int((g[0]).size()) > int((g[1]).size())) {
    swap(g[0], g[1]);
  }
  if (int((g[0]).size())) {
    for (point_t p : pts) {
      if (p.c == g[0][0].c) {
        res.push_back(make_pair(p.ix, g[0][0].ix));
        solve(p, a, b, pts);
        solve(p, b, c, pts);
        solve(p, c, a, pts);
        return;
      }
    }
  }
  for (point_t p : pts) {
    for (point_t q : {a, b, c}) {
      if (p.c == q.c) {
        res.push_back(make_pair(p.ix, q.ix));
        break;
      }
    }
    solve(p, a, b, pts);
    solve(p, b, c, pts);
    solve(p, c, a, pts);
    return;
  }
}
void chemthan() {
  cin >> n;
  p.resize(n);
  vector<point_t> pts;
  for (int i = (0); i < (n); ++i) {
    cin >> p[i].x >> p[i].y >> p[i].c;
    p[i].ix = i;
    pts.push_back(p[i]);
  }
  ConvexHull(pts);
  for (point_t p : pts) used[p.ix] = 1;
  int st = 0;
  for (int i = (0); i < (int((pts).size())); ++i) {
    int j = (i + int((pts).size()) - 1) % int((pts).size());
    if (pts[i].c != pts[j].c) {
      st = i;
    }
  }
  vector<point_t> npts;
  for (int i = (0); i < (int((pts).size())); ++i) {
    int j = (i + st) % int((pts).size());
    npts.push_back(pts[j]);
  }
  pts = npts;
  int ed = 0;
  while (ed < int((pts).size()) && pts[ed].c == pts[0].c) ed++;
  for (int i = (ed); i < (int((pts).size())); ++i)
    if (pts[i].c == pts[0].c) {
      cout << "Impossible\n";
      return;
    }
  for (int i = (0); i < (ed - 1); ++i) {
    res.push_back(make_pair(pts[i].ix, pts[i + 1].ix));
  }
  for (int i = (ed); i < (int((pts).size()) - 1); ++i) {
    res.push_back(make_pair(pts[i].ix, pts[i + 1].ix));
  }
  if (ed == int((pts).size())) {
    int found = 0;
    for (point_t q : p) {
      if (q.c != pts[0].c) {
        for (int i = (0); i < (int((pts).size())); ++i) {
          int j = (i + 1) % int((pts).size());
          solve(q, pts[i], pts[j], p);
        }
        found = 1;
        break;
      }
    }
    if (!found) {
      for (int i = (1); i < (int((pts).size()) - 1); ++i) {
        solve(pts[0], pts[i], pts[i + 1], p);
      }
    }
    for (pair<int, int>& e : res) {
      if (e.first > e.second) {
        swap(e.first, e.second);
      }
    }
    sort((res).begin(), (res).end()),
        (res).erase(unique((res).begin(), (res).end()), (res).end());
    cout << int((res).size()) << "\n";
    for (pair<int, int> e : res) {
      cout << e.first << " " << e.second << "\n";
    }
    return;
  }
  for (int i = (0); i < (ed - 1); ++i) {
    solve(pts[ed], pts[i], pts[i + 1], p);
  }
  for (int i = (ed); i < (int((pts).size()) - 1); ++i) {
    solve(pts[0], pts[i], pts[i + 1], p);
  }
  for (pair<int, int>& e : res) {
    if (e.first > e.second) {
      swap(e.first, e.second);
    }
  }
  sort((res).begin(), (res).end()),
      (res).erase(unique((res).begin(), (res).end()), (res).end());
  cout << int((res).size()) << "\n";
  for (pair<int, int> e : res) {
    cout << e.first << " " << e.second << "\n";
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}