Alien Centipede Identification

In the year \(2333\), after a 17-year, 3‐month journey, the crew of the NASA spacecraft returned with extraordinary samples from outer space. Among these, the most fascinating are the centipedes discovered on asteroid Jason. Unlike Earth centipedes which always have an even number of legs, these alien centipedes have an unusual property: while each body segment may bear an arbitrary number of legs, the total number of legs of an alien centipede is always odd.

Scientists have learned that, by simply checking the parity of the total number of legs, one can tell which planet the centipede comes from. However, judging by appearance alone is impossible, so NASA devised a clever method.

You are given \(N\) centipedes numbered from \(1\) to \(N\). Each centipede belongs either to Earth (if it has an even number of legs) or to an alien planet (if it has an odd number of legs). You are not allowed to count the legs yourself. Instead, Charles Bolden, director of NASA, will perform \(M\) operations using the Insect Feet Counter (IFC).

In each operation, a designated subset of the \(N\) centipedes is placed into the IFC. The machine reports only the parity of the sum of the legs (i.e. the sum modulo \(2\)). Along with the parity result \(r\) (either \(0\) or \(1\)), you are told which centipedes were selected.

Your task is to determine the origin of each centipede by deducing their individual leg parities. Formally, let each centipede \(i\) have an unknown binary value \(x_i\), where \(x_i = 0\) indicates that the centipede is from Earth (even total legs) and \(x_i = 1\) indicates it is alien (odd total legs). Each operation gives you a linear equation modulo \(2\):

\[ \sum_{i\in S} x_i \equiv r \pmod{2}, \]

You must process the operations in order. If after the \(K\)th operation (with \(K \le M\)) the given data is sufficient to uniquely determine the values of \(x_1, x_2, \ldots, x_N\) (i.e. the system of equations has a unique solution over \(\mathbb{F}_2\)), then you should output \(K\) and the unique identification for all centipedes (printing "Earth" for \(0\) and "Alien" for \(1\)). Note that if \(K < M\), this means the remaining \(M-K\) operations were not necessary. If, after processing all \(M\) operations, the system does not have a unique solution (i.e. there exist multiple solutions), then output "MULTIPLE".

Input and Output formats are described below.

inputFormat

The first line contains two integers \(N\) and \(M\) \( (1 \le N, M \le \text{reasonable limits})\).

Then \(M\) lines follow. Each line describes an operation. The first number of the line is an integer \(k\) (the number of centipedes selected in this operation), followed by \(k\) distinct integers representing the centipede indices. The last number on the line is an integer \(r\) (either 0 or 1), the parity (modulo 2) of the total number of legs of the selected centipedes.

outputFormat

If the centipedes' origins can be uniquely identified after some \(K\) operations, output two lines. The first line should contain the minimum \(K\) (the earliest operation after which the data uniquely determines the assignment). The second line should contain \(N\) tokens: for each centipede from 1 to \(N\), output "Earth" if its corresponding value is 0 (even legs) or "Alien" if it is 1 (odd legs).

If after all operations the system has multiple valid solutions, output a single line containing the string "MULTIPLE".

sample

2 1
2 1 2 1

MULTIPLE