{"problem":{"name":"Poor Turkeys","description":{"content":"There are $N$ turkeys. We number them from $1$ through $N$. $M$ men will visit here one by one. The $i$\\-th man to visit will take the following action: *   If both turkeys $x_i$ and $y_i$ are alive:","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc016_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $2 ≤ N ≤ 400$\n*   $1 ≤ M ≤ 10^5$\n*   $1 ≤ x_i < y_i ≤ N$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc016_e","tags":[],"sample_group":[["3 1\n1 2","2\n\n$(i,\\ j) = (1,\\ 3), (2,\\ 3)$ satisfy the condition."],["4 3\n1 2\n3 4\n2 3","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."],["3 2\n1 2\n1 2","0"],["10 10\n8 9\n2 8\n4 6\n4 9\n7 8\n2 8\n1 8\n3 4\n3 4\n2 7","5"]],"created_at":"2026-03-03 11:01:13"}}