Количество триплетов с одинаковым цветом ребер в полном графике
Я готовлюсь к Национальному соревнованию по программированию и столкнулся с этой проблемой:
Нам дан неориентированный полный граф с N вершинами. Каждое ребро в графе имеет цвет красный или зеленый. Мы должны найти число триплетов(i,j,k) вершин,таких что ребра(i, j), (j,k)и(i,k) имеют одинаковый цвет. Нам даны N и M, где M - количество ребер красного цвета в графе. И в следующих M строках нам даны все красные ребра, которые существуют в этом графе. Остальные ребра(ребра, которых нет во входных данных, зеленые). Н-от 3 до 300000 (3&л;=п<=300000) м-от 1 до 300000 (1&ЛТ;=М&Л;=300000) Ограничение по времени составляет 2 секунды
Может ли кто-нибудь дать мне некоторое представление о том, как подойти и решить эту проблему?
Заранее спасибо.
Что я уже пробовал:
Я предполагаю, что это решение должно иметь сложность O(NlogN), но я понятия не имею, как решить его в этой сложности.