Alchemic Transformation

Byteasar is a famous alchemist who wishes to transform his current molecule into a target molecule. Each molecule consists of n distinct atoms (from 1 to n) that are connected by bonds in such a way that the molecule is connected (i.e. every atom is reachable from any other via a sequence of bonds). There is at most one bond between any pair of atoms.

Byteasar has two kinds of operations available to modify the bonds in his molecule:

• Add Bond: He may add a bond between two distinct atoms a and b that are not directly connected. However, to do so, there must exist a third atom c (different from both a and b) that is bonded to both a and b.
• Remove Bond: He may remove an existing bond between two distinct atoms a and b, provided that there is a third atom c (different from a and b) which is bonded to both a and b at that moment.

Both the initial and the target molecules satisfy these properties (each is connected and has at most one bond between any pair of atoms). Byteasar wants to achieve the target molecule in at most \(200\,000\) operations. You are given the description of the current molecule and the target molecule. Write a program to output a valid sequence of operations which will transform the current molecule into the target one. If the current molecule already equals the target molecule, output 0 (i.e. no operations are needed).

Note: Atoms are distinct and numbered from 1 to n.

inputFormat

The input is given as follows:

1. A line containing a single integer n (number of atoms).
2. A line containing a single integer m₁ (the number of bonds in the current molecule).
3. Then m₁ lines follow, each containing two integers a and b (1 ≤ a, b ≤ n) representing a bond between atom a and atom b in the current molecule.
4. A line containing a single integer m₂ (the number of bonds in the target molecule).
5. Then m₂ lines follow, each containing two integers a and b representing a bond between atom a and atom b in the target molecule.

outputFormat

First, output a single integer k (0 ≤ k ≤ 200,000) representing the number of operations. Then output k lines, each describing an operation in one of the following formats:

• ADD a b — to add a bond between atoms a and b.
• REMOVE a b — to remove the bond between atoms a and b.

It is guaranteed that if the current molecule and target molecule are already identical, a valid output is simply 0.

sample

3
3
1 2
1 3
2 3
3
1 2
1 3
2 3

0