Problem D
The Summer Sun Setback

The Summer Sun Celebration is a major Equestria-wide festival that has been held every year since the defeat of Nightmare Moon at the hooves of Princess Celestia over a thousand years ago. It has been a long, long way since; one could hardly imagine today that any animosity could have ever existed between the two royal sisters, never mind the type of extreme hatred that turned Princess Luna into the horror that was.

The two princesses are retiring this year, and, having served its purpose, so too will the Summer Sun Celebration be retired. Twilight Sparkle has been put in charge of organizing this event for the last time, and she has set her heart on making it absolutely flawless; unbeknownst to her, however, sinister forces are conspiring to upend all her hard work...

Figure 1: Illustration by Kyle Coate.

Having retrieved Grogar’s legendary bell, Cozy Glow, Lord Tirek and Queen Chrysalis have decided to keep it for themselves. They do not know how to unlock its power, however, and all the information about this bell is hidden deep within the walls of the now-fortified Canterlot Castle. They have hatched a nefarious plan: during the festivities, cause enough of a chaos to form a distraction and sneak into the castle!

There are $S$ events that need to be organized for the festival to be a success and $N$ volunteers available to organize them. The $i^\text {th}$ volunteer is either

1. an assigned volunteer, who has been formally assigned to assist in organizing the $C_ i^\text {th}$ event, or

2. an unassigned volunteer, who signed up to assist in organizing either the $A_ i^\text {th}$ event or the $B_ i^\text {th}$ event but has not yet been formally assigned to either.

For the Summer Sun Celebration to be a success, all of the unassigned volunteers must be formally assigned to one of their two events such that every event has at least one volunteer assigned to organize it; additionally, after all assignments have been made, every event must have exactly one leader chosen among the volunteers assigned to organize that event, and the remaining volunteers, if any, must work in pairs. In other words, there must be an odd number of volunteers assigned to organize each event.

Now, here comes the devious strategy: Cozy Glow, Lord Tirek and Queen Chrysalis will deceive some (possibly none, possibly all) of the unassigned volunteers into thinking that they have been formally assigned to one of their two events, such that when Twilight comes to assign the remaining unassigned volunteers later, it will be impossible to satisfy the requirements, and she will completely freak out!

Obviously, the more volunteers they have to deceive, the more suspicion it raises and the greater their chances of getting caught. Determine how they might deceive the minimum number of volunteers such that Twilight will be unable to assign the remaining volunteers appropriately.

If the task is truly impossible, you must also say so.

Input

The first line of input contains two integers, $N$ ($1 \leq N \leq 8\, 000$) and $S$ ($1 \leq S \leq 500$), the number of volunteers and the number of events, respectively.

The next $N$ lines of input contain the descriptions of the volunteers. In particular, the $i^\text {th}$ of these lines begins with a single character:

• If this character is A, a single integer $C_ i$ ($1 \leq C_ i \leq S$) follows, denoting that the $i^\text {th}$ volunteer is an assigned volunteer and has been formally assigned to assist in organizing the $C_ i^\text {th}$ event.

• If this character is U, two integers $A_ i$ and $B_ i$ ($1 \leq A_ i, B_ i \leq S$; $A_ i \neq B_ i$) follow, denoting that the $i^\text {th}$ volunteer is an unassigned volunteer and has signed up to assist in organizing either the $A_ i^\text {th}$ event or the $B_ i^\text {th}$ event.

Output

If there is no way to deceive some (possibly none, possibly all) of the volunteers in such a way that Twilight will be unable to assign the remaining volunteers appropriately, output a single line containing the string IMPOSSIBLE.

Otherwise, on the first line, output a single integer $m$, the minimum number of volunteers they need to deceive.

Then, on the next $m$ lines, output the volunteers they need to deceive. In particular, the $i^\text {th}$ of these lines should contain two integers $v_ i$ ($1 \leq v_ i \leq N$) and $s_ i$ ($s_ i = A_{v_ i}$ or $s_ i = B_{v_ i}$), denoting that they should deceive the $v_ i^\text {th}$ volunteer into thinking they have been formally assigned to assist in organizing the $s_ i^\text {th}$ event. All $v_ i$ should be distinct, all volunteers should be unassigned and deceiving these volunteers in this way should make it impossible for Twilight to assign the remaining volunteers appropriately. You can output the volunteers in any order.

If there are multiple correct answers, you can output any of them.

12 6
U 1 2
U 1 3
U 1 6
A 2
U 2 4
A 3
U 3 4
U 3 5
U 3 6
A 4
U 5 6
A 6

2
1 1
7 3

3 3
A 1
A 2
A 3

IMPOSSIBLE

2 3
A 1
A 2

0