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 JAVA):

Solution:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;

/**
 * @author timat
 *
 */
public class Task_codeforces {

	public static void main(String[] args) throws IOException {
		FastIO.init();

		int n = FastIO.readInt();

		DSU dsu = new DSU(n);

		LinkedList<int[]> notused = new LinkedList<int[]>();

		for (int i = 0; i < n - 1; i++) {
			int a = FastIO.readInt() - 1;
			int b = FastIO.readInt() - 1;

			if (dsu.findSet(a) == dsu.findSet(b)) {
				notused.addFirst(new int[] { a, b });
			} else {
				dsu.unionSets(a, b);
			}
		}

		int t = 0;
		StringBuilder result = new StringBuilder();
		for (int i = 0; i < n; i++) {
			if (dsu.findSet(0) != dsu.findSet(i)) {
				t++;
				int[] toclose = notused.removeFirst();
				result.append(toclose[0] + 1).append(" ").append(toclose[1] + 1).append(" 1 ").append(i + 1)
						.append("\n");
				dsu.unionSets(0, i);
			}
		}
		System.out.println(t);
		System.out.println(result.toString());

		FastIO.cleanup();
	}

	private static class FastIO {
		private static StringTokenizer tokenizer;
		private static BufferedReader in;

		public static void init() {
			in = new BufferedReader(new InputStreamReader(System.in));
		}

		public static void initf() throws FileNotFoundException {
			initf("in.txt");
		}

		public static void initf(String name) throws FileNotFoundException {
			File file = new File(name);
			in = new BufferedReader(file.exists() ? new FileReader(file) : new InputStreamReader(System.in));
		}

		public static void cleanup() throws IOException {
			in.close();
		}

		public static String readToken() throws IOException {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(in.readLine());
			}
			return tokenizer.nextToken();
		}

		public static int readInt() throws NumberFormatException, IOException {
			return Integer.parseInt(readToken());
		}

	}

	private static class DSU {

		// Tree
		private final ArrayList<Union> unions = new ArrayList<Union>();

		public DSU(int startcap) {
			unions.ensureCapacity(startcap);
			for (int i = 0; i < startcap; i++) {
				makeSet();
			}
		}

		public DSU() {
		}

		/**
		 * Creates new set and returns its index.
		 * 
		 * @return : Index of the new element.
		 */
		public int makeSet() {
			int index = unions.size();
			Union entry = new Union(index);
			unions.add(index, entry);
			return index;
		}

		/**
		 * This method find set in which given set is in.
		 * 
		 * @param setIndex
		 * @return
		 */
		public int findSet(int setIndex) {
			if (unions.get(setIndex).parent == setIndex) {
				return setIndex;
			} else {
				int parent = unions.get(setIndex).parent;
				int result = findSet(parent);
				unions.get(setIndex).parent = result;
				return result;
			}
		}

		/**
		 * This method unites two sets.
		 * 
		 * @param element1
		 *            : Index of the set 1.
		 * @param element2
		 *            : Index if the set 2.
		 */
		public void unionSets(int element1, int element2) {
			int set1 = findSet(element1);
			int set2 = findSet(element2);
			Union es1 = unions.get(set1);
			Union es2 = unions.get(set2);
			if (es1.rank == es2.rank) {
				es1.rank++;
				es2.parent = set1;
				return;
			}
			if (es1.rank > es2.rank) {
				es2.parent = set1;
			} else {
				es1.parent = set2;
			}
		}

		@Override
		public String toString() {
			TreeMap<Integer, StringBuilder> str = new TreeMap<Integer, StringBuilder>();

			for (int unionIndex = 0; unionIndex < unions.size(); unionIndex++) {
				int set = findSet(unionIndex);
				if (!str.containsKey(set)) {
					str.put(set, new StringBuilder());
				}

				StringBuilder b = str.get(set);
				if (b.length() > 0) {
					b.append(", ");
				} else {
					b.append("Set leader : ").append(set).append(" : [");
				}
				b.append(unionIndex);
			}

			StringBuilder result = new StringBuilder();
			Set<Entry<Integer, StringBuilder>> es = str.entrySet();
			for (Entry<Integer, StringBuilder> e : es) {
				result.append(e.getValue().append("]\n"));
			}

			return result.toString();
		}

		private class Union {
			private int parent;
			private int rank = 0;

			private Union(int parent) {
				super();
				this.parent = parent;
			}
		}

	}

}