You are hired by the french NSA to break the RSA code used on the Pink Card. The easiest way to do that is to factor the public modulus and you have found the fastest algorithm to do that, except that you have to solve a subproblem that can be modeled in the following way. Let P = {p1,p2,...,pn} be a set of prime numbers. We call relation a set of two primes {p,q}, where p and q are distinct. You have a collection of R relations Si = {pi, qi}. If S and T are sets of primes, then S ∗ T will denote the product of all the primes in S and T . You are interested in subproducts of the (Si)′s whose product make a square. The way you look for these squares is the following. The ultimate goal is to count squares that appear in the process. Relations arrive one at a time. You maintain a collection C of relations that do not contain any square subproduct. This is easy: at first, C is empty. Then a relation arrives and C begins to grow. Suppose a new relation {p,q} arrives. If no square appears when adding {p,q} to C, then {p, q} is added to the collection. Otherwise, a square is about to appear, we increase the number of squares, but we do not store this relation, hence C keeps the desired property. Let us consider an example. First arrives S1 = {2, 3} and we put it in C ; then arrive S2 = {5, 11}, S3 = {3, 7} and they are stored in C. Now enters the relation S4 = {2, 7}. This relation could be used to form the square: S1 ∗S3 ∗S4 =(2∗3)∗(3∗7)∗(2∗7)=(2∗3∗7)2. So we count 1 and do not store S4 in C. Now, we consider S5 = {5,11} that could make a square with S2, so we count 1 square more. Then S6 = {2,13} is put into C. Now S7 = {7,13} could make the square S1 ∗ S3 ∗ S6 ∗ S7. Eventually, we get 3 squares. Input Input consists of several test cases, each of them following the description below. A blank line separates two consecutive cases. Each test case begins with a line containing two integers P and R: P ≤ 106 is the number of primes occurring in the test case; R(≤ 106) is the number of sets of primes that arrive. The subsequent R lines each contain two integers i and j making a set {pi,pj} (1 ≤ i,j ≤ P). Note that we actually do not deal with the primes, that are irrelevant to the solution. Output For each test case, output the number of squares that can be formed using the preceding rules. A line contains the number of the test case, followed by the number of square. The outputs of two consecutive cases will be separated by a blank line. Sample Input 67 12 35 24 14 35 16
2/2 46 23 12 12 12 Sample Output 3 2