Problem: Berland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roads so that from each city of Berland and neighboring countries it became possible to reach all the others. There are n cities in Berland and neighboring countries in total and exactly n - 1 two-way roads. Because of the recent financial crisis, the Berland Government is strongly pressed for money, so to build a new road it has to close some of the existing ones. Every day it is possible to close one existing road and immediately build a new one. Your task is to determine how many days would be needed to rebuild roads so that from each city it became possible to reach all the others, and to draw a plan of closure of old roads and building of new ones.

Input

The first line contains integer n (2 ≤ n ≤ 1000) — amount of cities in Berland and neighboring countries. Next n - 1 lines contain the description of roads. Each road is described by two space-separated integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — pair of cities, which the road connects. It can't be more than one road between a pair of cities. No road connects the city with itself.

Output

Output the answer, number t — what is the least amount of days needed to rebuild roads so that from each city it became possible to reach all the others. Then output t lines — the plan of closure of old roads and building of new ones. Each line should describe one day in the format i j u v — it means that road between cities i and j became closed and a new road between cities u and v is built. Cities are numbered from 1. If the answer is not unique, output any.

Examples

Input

2
1 2


Output

0


Input

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


Output

1
3 1 3 7

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<V<T>>;
template <typename T>
using Mi = map<long long, T>;
template <typename T>
using MMi = map<long long, Mi<T>>;
const double PI = 3.141592653589793238463;
template <typename T>
istream &operator>>(istream &cin, V<T> &arr) {
  for (T &val : arr) {
    cin >> val;
  }
  return cin;
}
template <typename T>
ostream &operator<<(ostream &cout, VV<T> &arr) {
  for (V<T> &val : arr) {
    cout << val << '\n';
  }
  return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, V<T> &arr) {
  for (T &val : arr) {
    cout << val << " ";
  }
  return cout;
}
template <typename T, typename R>
istream &operator>>(istream &cin, pair<T, R> &p) {
  cin >> p.first >> p.second;
  return cin;
}
template <typename T, typename R>
ostream &operator<<(ostream &cout, pair<T, R> &p) {
  cout << p.first << " " << p.second;
  return cout;
}
template <typename T>
V<T> &operator--(V<T> &arr) {
  for (T &val : arr) {
    val--;
  }
  return arr;
}
template <typename T>
V<T> &operator++(V<T> &arr) {
  for (T &val : arr) {
    val++;
  }
  return arr;
}
pair<long long, long long> zero = {-1, -1};
template <typename T>
long long bs(T &x, V<T> &arr) {
  long long l = 0;
  long long r = arr.size();
  while (l < r) {
    long long mid = (l + r) / 2;
    if (arr[mid] > x) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
}
int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, 1, -1};
class Siev {
 public:
  V<int> prim;
  V<int> prims;
  long long n;
  Siev(long long n = 1e6) : n(n) {
    prim.resize(n + 1);
    for (int i = 0; i <= n; i++) {
      prim[i] = i;
    }
    for (long long i = 2; i <= n; i++) {
      if (prim[i] == i) {
        prims.push_back(i);
        for (long long j = i * i; j <= n; j += i) {
          if (prim[j] == j) {
            prim[j] = i;
          }
        }
      }
    }
  }
};
long long gcd(long long a, long long b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
long long lcm(long long a, long long b) {
  long long nod = gcd(a, b);
  long long ans = a / nod * b;
  return ans;
}
long long divup(long long a, long long b) {
  if (a % b == 0) {
    return a / b;
  } else {
    return a / b + 1;
  }
}
class SNM {
 private:
  vector<long long> parent;
  vector<long long> size;

 public:
  SNM(int n) {
    parent = vector<long long>(n);
    size = vector<long long>(n, 1);
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }
  void make_set(int v) { parent[v] = v; }
  int find_set(int v) {
    if (v == parent[v]) return v;
    long long ans = find_set(parent[v]);
    parent[v] = ans;
    return ans;
  }
  void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
      parent[b] = a;
      size[a] += size[b];
    }
  }
  long long getSize(int v) {
    v = find_set(v);
    return size[v];
  }
};
class LCA {
 private:
  long long N;
  long long n;
  vector<vector<long long>> up;
  vector<vector<long long>> g;
  vector<long long> lvl;
  void dfs(long long v, long long h) {
    lvl[v] = h;
    for (long long u : g[v]) {
      dfs(u, h + 1);
    }
  }

 public:
  LCA(vector<long long> &parent) {
    n = parent.size();
    N = log2(n) + 1;
    g = vector<vector<long long>>(n);
    lvl = vector<long long>(n);
    long long core = -1;
    for (int i = 0; i < n; i++) {
      if (parent[i] != -1) {
        g[parent[i]].push_back(i);
      } else {
        core = i;
      }
    }
    dfs(core, 0);
    up = vector<vector<long long>>(N, vector<long long>(n));
    up[0] = parent;
    for (int i = 1; i < N; i++) {
      for (int j = 0; j < n; j++) {
        long long parent = up[i - 1][j];
        if (parent == -1) {
          up[i][j] = -1;
        } else {
          up[i][j] = up[i - 1][parent];
        }
      }
    }
  }
  long long getParent(long long v, long long needUp) {
    for (int i = N - 1; i >= 0; i--) {
      if (up[i][v] != -1 && lvl[v] - lvl[up[i][v]] <= needUp) {
        needUp -= lvl[v] - lvl[up[i][v]];
        v = up[i][v];
      }
    }
    if (needUp != 0) {
      return -1;
    } else {
      return v;
    }
  }
  long long getLCA(long long a, long long b) {
    if (lvl[a] > lvl[b]) {
      long long del = abs(lvl[a] - lvl[b]);
      a = getParent(a, del);
    }
    if (lvl[a] < lvl[b]) {
      long long del = abs(lvl[a] - lvl[b]);
      b = getParent(b, del);
    }
    if (a == b) {
      return a;
    }
    for (int i = N - 1; i >= 0; i--) {
      if (up[i][a] != up[i][b]) {
        a = up[i][a];
        b = up[i][b];
      }
    }
    return up[0][a];
  }
  long long getLvl(long long v) { return lvl[v]; }
};
class Node {
 private:
  long long val;
  long long size;
  long long l;
  long long r;
  Node *lChildren;
  Node *rChildren;
  long long merge(Node *a, Node *b) {
    long long ans = 0;
    ans = a->val + b->val;
    return ans;
  }
  Node(long long l, long long r, vector<long long> &arr) {
    this->l = l;
    this->r = r;
    if (l == r) {
      val = arr[l];
    } else {
      long long mid = (l + r) / 2;
      lChildren = new Node(l, mid, arr);
      rChildren = new Node(mid + 1, r, arr);
      val = merge(lChildren, rChildren);
    }
  }

 public:
  Node(vector<long long> arr) : Node(0, arr.size() - 1, arr) {}
  long long getValue(long long need) {
    if (size == 1) {
      return 1;
    }
    if (lChildren->val >= need) {
      return lChildren->getValue(need);
    } else {
      long long ans = lChildren->size;
      need -= lChildren->val;
      return ans + rChildren->getValue(need);
    }
  }
  long long getValue(long long left, long long right) {
    if (l == left && r == right) {
      return val;
    }
    long long mid = (l + r) / 2;
    long long ans = 0;
    if (left <= mid) {
      ans += lChildren->getValue(left, min(right, mid));
    }
    if (right > mid) {
      ans += rChildren->getValue(max(mid + 1, left), right);
    }
    return ans;
  }
  void update(long long l, long long r, long long value) {
    if (l == this->l && r == this->r) {
      val = value;
      return;
    }
    long long mid = (this->l + this->r) / 2;
    if (l <= mid) {
      lChildren->update(l, min(mid, r), value);
    }
    if (r > mid) {
      rChildren->update(max(mid + 1, l), r, value);
    }
    val = merge(lChildren, rChildren);
  }
  void up(long long ind) {
    if (ind == this->l && ind == this->r) {
      val++;
      return;
    }
    long long mid = (this->l + this->r) / 2;
    if (ind <= mid) {
      lChildren->up(ind);
    }
    if (ind > mid) {
      rChildren->up(ind);
    }
    val = merge(lChildren, rChildren);
  }
};
void delR(long long v, vector<vector<long long>> &g, vector<bool> &viz,
          vector<vector<long long>> &G) {
  viz[v] = true;
  for (long long u : g[v]) {
    if (!viz[u]) {
      G[v].push_back(u);
      delR(u, g, viz, G);
    }
  }
}
class Drob {
 public:
  long long a = 0;
  long long b = 1;
  Drob(long long a, long long b = 1) : a(a), b(b) {
    long long nod = gcd(a, b);
    a /= nod;
    b /= nod;
  }
  Drob operator+(Drob &add) {
    long long na = a * add.b + add.a * b;
    long long nb = b * add.b;
    return Drob(na, nb);
  }
  Drob operator+=(Drob &add) { return *this + add; }
  Drob operator-(Drob &minus) { minus.a *= -1; }
  Drob operator-=(Drob &minus) { return *this - minus; }
  Drob operator*(Drob &d) {
    long long na = a * d.a;
    long long nb = b * d.b;
    return Drob(na, nb);
  }
  Drob operator*=(Drob &d) { return (*this) * d; }
  Drob operator/(Drob &d) {
    Drob dd(d.b, d.a);
    return (*this) * dd;
  }
  Drob operator/=(Drob &d) { return (*this) / d; }
  bool operator==(Drob &d) { return a == d.a && b == d.b; }
  bool operator>(Drob &d) {
    long long aa = a * d.b;
    long long ad = d.a * b;
    return aa > ad;
  }
};
void split(string &str, char &space, V<string> &ans) {
  auto i = str.begin();
  while (i != str.end()) {
    i = std::find_if(i, str.end(), [space](char c) { return c != space; });
    auto j = std::find_if(i, str.end(), [space](char c) { return c == space; });
    if (i != str.end()) {
      ans.push_back(std::string(i, j));
      i = j;
    }
  }
}
long long sumNumber(long long n) {
  long long sum = 0;
  while (n != 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
class Prefix {
  vector<long long> prefix;
  long long n;

 public:
  Prefix(vector<long long> &arr) {
    n = arr.size() + 1;
    prefix.resize(n);
    prefix[0] = 0;
    for (int i = 0; i < n - 1; i++) {
      prefix[i + 1] = prefix[i] + arr[i];
    }
  }
  long long sum(long long l, long long r) { return prefix[r + 1] - prefix[l]; }
};
class DPrefix {
  vector<vector<long long>> prefix;
  long long n;
  long long m;

 public:
  DPrefix(vector<vector<long long>> &matr) {
    long long n = matr.size() + 1;
    long long m = matr[0].size() + 1;
    prefix = vector<vector<long long>>(n, vector<long long>(m, 0));
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < m - 1; j++) {
        prefix[i + 1][j + 1] =
            prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + matr[i][j];
      }
    }
  }
  long long sum(pair<long long, long long> p1, pair<long long, long long> p2) {
    p2.first++;
    p2.second++;
    long long res = prefix[p1.first][p1.second] + prefix[p2.first][p2.second] -
                    prefix[p1.first][p2.second] - prefix[p2.first][p1.second];
  }
};
template <typename T>
class AV : public V<T> {
 public:
  AV() : V<T>(){};
  AV(long long n) : V<T>(n){};
  AV(long long n, long long val) : V<T>(n, val){};
  T sum() {
    T ans = 0;
    for (T &val : *this) {
      ans += val;
    }
    return ans;
  }
  T max() {
    T ans = (*this)[0];
    for (T &val : *this) {
      ans = std::max(ans, val);
    }
    return ans;
  }
  T min() {
    T ans = (*this)[0];
    for (T &val : *this) {
      ans = std::min(ans, val);
    }
    return ans;
  }
  void rsort() { std::sort(this->rbegin(), this->rend()); }
  void sort() { std::sort(this->begin(), this->end()); }
  long long bs(T &x) {
    V<T> &arr = *this;
    long long l = 0;
    long long r = arr.size();
    while (l < r) {
      long long mid = (l + r) / 2;
      if (arr[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};
long long dfs(long long v, vector<vector<long long>> &g, vector<bool> &viz,
              map<pair<long long, long long>, long long> &road) {
  viz[v] = true;
  long long ans = 0;
  for (long long u : g[v]) {
    if (!viz[u]) {
      ans += dfs(u, g, viz, road);
      ans += road[{v, u}];
    }
  }
  return ans;
}
void tdfs(long long v, vector<vector<long long>> &g, vector<bool> &viz,
          map<pair<long long, long long>, long long> &road, long long sum,
          vector<long long> &ans) {
  ans[v] = sum;
  viz[v] = true;
  for (long long u : g[v]) {
    if (!viz[u]) {
      long long nsum = sum + road[{u, v}] - road[{v, u}];
      tdfs(u, g, viz, road, nsum, ans);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  SNM snm(n);
  stack<pair<long long, long long>> buf;
  for (int i = 0; i < n - 1; i++) {
    long long v, u;
    cin >> v >> u;
    v--;
    u--;
    long long a = snm.find_set(v);
    long long b = snm.find_set(u);
    if (a != b) {
      snm.union_sets(a, b);
    } else {
      buf.push({v, u});
    }
  }
  V<pair<pair<long long, long long>, pair<long long, long long>>> answer;
  long long core = snm.find_set(0);
  for (int i = 1; i < n; i++) {
    long long a = snm.find_set(i);
    if (a != core) {
      pair<long long, long long> del = buf.top();
      buf.pop();
      del.first++;
      del.second++;
      pair<long long, long long> add;
      add.first = core + 1;
      add.second = a + 1;
      snm.union_sets(core, a);
      answer.push_back({del, add});
    }
  }
  cout << answer.size() << '\n';
  for (auto pp : answer) {
    cout << pp << '\n';
  }
  return 0;
}