Counting triplets

3.8

10 votes
Ad-Hoc, Algorithms, Combinatorics, Graphs, Medium, 普通
Problem

You are given an undirected, complete graph  that contains  vertices. Each edge is colored in either white or black. You are required to determine the number of triplets   of vertices such that the edges are of the same color.

There are white edges and black edges.

Input format

  • First line: Two integers - and
  • line: Two integers - and  denoting that the edge is white in color

Note: The conditions and are satisfied for all .

Output format

Print an integer that denotes the number of triples that satisfy the mentioned condition.

Additional information

  • For points:  is satisfied
  • For additional  points:  is satisfied
  • Original constraints for remaining points
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The triplets are: .

The graph consisting of only white edges:

The graph consisting of only black edges:

 

Editor Image

?