{"code":"banga","name":"Bán Gà","description":"Nhà [user:shiba] đang nuôi $N$ con gà được đánh số từ $1$ đến $N$. [user:shiba] thấy đàn gà gáy quá ồn nên anh ấy quyết định ra chợ đi bán đàn gà ấy.\r\n\r\nCó $M$ người **xếp hàng** mua đàn gà [user:shiba] bán. Người thứ $i$ mua gà theo hành động như sau:\r\n\r\n - Nếu cả hai con $x_i$ và $y_i$ đều chưa bị bán: Chọn một trong hai con và mua nó.\r\n - Nếu một trong hai con $x_i$ và $y_i$ chưa bị bán: Mua con chưa bị bán.\r\n - Nếu cả hai con $x_i$ và $y_i$ đều đã bị bán: Không mua nữa.\r\n\r\n[user:shiba] muốn tính xem có bao nhiêu cặp $(i,j)$ $(1 \\le i < j \\le N)$ thỏa mãn rằng **xác xuất** cả hai con gà $i$ và $j$ đều chưa bị bán sau khi cả $M$ người đi mua lớn hơn $0$. Hay nói cách khác, [user:shiba] muốn tính xem có bao nhiêu cặp $(i,j)$ $(1 \\le i < j \\le N)$ thỏa mãn rằng cả hai con gà $i$ và $j$ đều chưa bị bán sau khi cả $M$ người đi mua là **có khả năng xảy ra**.\r\n\r\n#### Input\r\n - Dòng đầu tiên chứa hai số nguyên dương $N$ và $M$ $(2 \\le N \\le 5000, 1 \\le M \\le 10^5)$, hai số cách nhau một khoảng trắng.\r\n - $M$ dòng còn lại mỗi dòng chứa hai số nguyên dương $x_i$ và $y_i$ $(1 \\le x_i < y_i \\le N)$. \r\n\r\n#### Output\r\n - In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.\r\n\r\n#### Scoring\r\n - Subtask $1$ ($60\\%$ số điểm): Có $N \\le 400$.\r\n - Subtask $2$ ($40\\%$ số điểm): Có $N \\le 5000$ và $M \\le 10^4$.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 1\r\n        1 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Chỉ có $1$ người mua, con $3$ không bị đem đi bán. Nếu người đó chọn con $1$ thì cặp $(2,3)$ thỏa mãn điều kiện, nếu người đó chọn con $2$ thì cặp $(1,3)$ thỏa mãn điều kiện \r\n        \r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 3\r\n        1 2\r\n        3 4\r\n        2 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n    ??? warning \"Note\"\r\n        - có cặp $(1,4)$ sẽ thỏa mãn điều kiện nếu $3$ người kia mua như sau:\r\n            - Người thứ $1$ mua con gà $2$.\r\n            - Người thứ $2$ mua con gà $3$.\r\n            - Người thứ $3$ không mua con nào cả.\r\n            \r\n!!! question \"Test 3\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 2\r\n        1 2\r\n        1 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0\r\n        ```\r\n        \r\n!!! question \"Test 4\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        10 10\r\n        8 9\r\n        2 8\r\n        4 6\r\n        4 9\r\n        7 8\r\n        2 8\r\n        1 8\r\n        3 4\r\n        3 4\r\n        2 7\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        5\r\n        ```","points":1800.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}