{"raw_statement":[{"iden":"problem statement","content":"There are $N$ turkeys. We number them from $1$ through $N$.\n$M$ men will visit here one by one. The $i$\\-th man to visit will take the following action:\n\n*   If both turkeys $x_i$ and $y_i$ are alive: selects one of them with equal probability, then eats it.\n*   If either turkey $x_i$ or $y_i$ is alive (but not both): eats the alive one.\n*   If neither turkey $x_i$ nor $y_i$ is alive: does nothing.\n\nFind the number of pairs $(i,\\ j)$ ($1 ≤ i < j ≤ N$) such that the following condition is held:\n\n*   The probability of both turkeys $i$ and $j$ being alive after all the men took actions, is greater than $0$."},{"iden":"constraints","content":"*   $2 ≤ N ≤ 400$\n*   $1 ≤ M ≤ 10^5$\n*   $1 ≤ x_i < y_i ≤ N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$:$\n$x_M$ $y_M$"},{"iden":"sample input 1","content":"3 1\n1 2"},{"iden":"sample output 1","content":"2\n\n$(i,\\ j) = (1,\\ 3), (2,\\ 3)$ satisfy the condition."},{"iden":"sample input 2","content":"4 3\n1 2\n3 4\n2 3"},{"iden":"sample output 2","content":"1\n\n$(i,\\ j) = (1,\\ 4)$ satisfies the condition. Both turkeys $1$ and $4$ are alive if:\n\n*   The first man eats turkey $2$.\n*   The second man eats turkey $3$.\n*   The third man does nothing."},{"iden":"sample input 3","content":"3 2\n1 2\n1 2"},{"iden":"sample output 3","content":"0"},{"iden":"sample input 4","content":"10 10\n8 9\n2 8\n4 6\n4 9\n7 8\n2 8\n1 8\n3 4\n3 4\n2 7"},{"iden":"sample output 4","content":"5"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}