The governments of Berland and Beerland announced the possible consolidation coming soon! Sounds unbelievable, but seems that the heads of the governments were able to come to an agreement. The only open issue is the old sore spot with the road network. Both countries have N cities, the cities in each country are numbered from 1 to N. Some pairs of cities are connected by bidirectional roads. There is exactly one way to get from one city to any other in each country. There are no roads between Berland and Beerland.

The decision was made to keep things clear for the drivers and to introduce a number of changes in the road networks. The essential requirement for the consolidation is the identity of the road networks in both countries. This mean that cities with numbers a and b are connected by a road in Berland if and only if the cities with the same numbers are connected by a road in Beerland.

The Autoroad Construction Multicultural team (ACM-team) was created to achieve this goal. During one month the team can perform construction and repair work in one country. During this monthly repair one road is added to the road network of the country, resulting in a cycle in the road network, so one road in the cycle should be closed. So as the result of the month's work, there is still exactly one way to get from one city to any other in each country.

What is the minimum number of months required to make the road networks of both countries identical? What is the plan of actions for the ACM-team in this case?

The first line of the input file contains the integer number N (1 ≤ N ≤ 2000) — the number of cities in each country.

Each of the following N - 1 lines contains the description of the road in Berland given by the numbers of cities it connects. The following N - 1 lines contain the similar description of the roads in Beerland.

Write the minimal amount of months Q ACM-team needs to finish the work to the first line of the output. In the following Q lines write the description of the work for each month. Work during each month is described by five numbers p, a₁, b₁, a₂, b₂, which means that the repairs should be held in Berland (if p = 1) or Beerland (if p = 2), the road a₁, b₁ should be added, and the road a₂, b₂ should be closed. If there are several solutions, choose any of them.

sample input	sample output
4 1 2 2 3 3 4 1 3 3 4 4 2	2 2 1 2 2 4 1 1 3 2 3