James is fat, hungry, and mad at trees for existing.
To resolve his problems, he plans on deconstructing and eating a structure, called his tree, made out of marshmallows and toothpicks! His structure consists of ~N~ marshmallows and ~N-1~ toothpicks, all connected such that by moving through marshmallows and along toothpicks, he can travel between any two marshmallows.
James is planning on eating his tree. However, he is a perfectionist, only consuming marshmallows and throwing out the toothpicks in a very specific fashion! He has a list of ~Q~ operations, which he will apply in the order that they are given in. Each operation is of one of the following forms:
- ~L~ - James will eat every marshmallow that has one or less toothpicks attached to it, throwing out the single toothpick if it exists.
- ~D\ a_i\ b_i~ - James will throw out the toothpick between marshmallow ~a_i~ and marshmallow ~b_i~. If either of the marshmallows now has no toothpicks attached to it, he will eat it!
When running these operations, it is possible for James to become disappointed by his tree in the following ways:
- If there are no marshmallows left to eat when he runs an ~L~ operation.
- If either marshmallow ~a_i~, marshmallow ~b_i~, or the toothpick between them does not exist when he runs a ~D~ operation.
- If, following a ~D~ operation, the remaining toothpicks and marshmallows in his graph no longer form a tree.
After he is finished running his operations, he will eat all the remaining marshmallows in his tree anyways. As you may have noticed, James is in need of dieting, so he would like to minimize the total number of marshmallows he consumes. Can you find a tree that won't disappoint him, such that the initial number of marshmallows, ~N~, is minimized?
~1 \leq Q \leq 2\times10^3~
~1 \leq a_i, b_i \leq 2Q~
~a_i \neq b_i~
If there is at least one ~D~ operation, all unique marshmallows mentioned as ~a_i~ or ~b_i~ in ~D~ operations form a set of all integers in the range ~[1,X]~ for some integer ~2 \leq X \leq 2Q~.
Subtask 1 [10%]
There will only be ~D~ operations.
Subtask 2 [90%]
No additional constraints.
The first line of input contains a single integer ~Q~.
The next ~Q~ lines contain an operation, as specified in the problem statement.
If a tree cannot be constructed to appease James, print
-1 on a single line. You will receive an AC verdict if it was not possible, and WA otherwise.
The first line of output should be a single integer ~N~. ~N~ should be within the range ~[1,3\times10^6]~.
The next ~N-1~ lines should contain two integers ~u_i~ and ~v_i~ ~(1 \leq u_i, v_i \leq N)~, representing a toothpick that connects the marshmallows ~u_i~ and ~v_i~.
If your output follows this format and your output describes a tree that will not disappoint James, you will receive an AC verdict.
If your tree receives an AC verdict, it will be awarded at least 30% of the points. For the remaining 70%, the tree's ~N~ value must also be minimal.
Otherwise, you will receive a WA verdict.
Sample Input 1
8 L D 8 7 D 4 8 D 4 6 D 4 5 L D 1 3 D 1 2
Sample Output 1
12 1 2 2 11 11 12 1 3 3 5 5 4 4 6 6 10 4 8 8 7 7 9
Explanation for Sample 1
The tree the sample output represents can be visualized as follows:
The operations remove the following marshmallows from the tree, taking all toothpicks attached to them as they fall:
- The first ~L~ operation removes the marshmallows ~9~, ~10~, and ~12~.
- The first ~D~ operation removes the marshmallow ~7~.
- The second and third ~D~ operations remove the marshmallows ~8~ and ~6~, respectively.
- The fourth ~D~ operation remove the marshmallow ~4~.
- The second ~L~ operation removes the marshmallows ~5~ and ~11~.
- The fifth ~D~ operation removes the marshmallow ~3~.
- The sixth ~D~ operation removes the marshmallows ~1~ and ~2~.
Note that this is not the only possible sample output that would receive an AC verdict.
Sample Input 2
3 D 1 2 D 2 3 D 1 3
Sample Output 2
Explanation for Sample 2
It can be shown that it is not possible to construct a tree that will satisfy James.