Given two number n and q where 1 ≤ n, q ≤ 10.000
There are n nodes, each node have a green string connect to another. Each 2 node only have 1 string connect between them. There are n * (n — 1) * (n — 2) / 6 total string
You have to answer q queries, each query give 2 number u and v. You paint the string connect (u, v) by color red if they are green, and green if they are red (red <-> green). Then you have to count the number of triangle ABC (1 ≤ A, B, C ≤ n) where (A, B), (B, C), (C, A) have same color (all are red or green).
Time limit for the problem is 1s
Memory limit for the problem is 256Mb
Here are examples
Notice that the number of valid triangle can be bigger than 10 ^ 9
I think the problem can be solved using map
This is a not an ongoing contest problem but if you mind it you can ignore my blog. Thanks for reading