Монокарп тренер команд Берляндского ГУ по программированию. Он решил собрать тренировку для своих команд перед квалификационным этапом.
У Монокарпа есть \(n\) задач, которые еще не решал ни один из его студентов. У \(i\)-й задачи есть тема \(a_i\) (целое число от \(1\) до \(n\)) и сложность \(b_i\) (целое число от \(1\) до \(n\)), причем все задачи попарно различны, то есть нет двух задач, у которых одинаковы и тема, и сложность.
Монокарп решил выбрать из \(n\) задач ровно \(3\) задачи для тренировки, при этом должно выполняться хотя бы одно из двух условий (возможно, оба):
- темы всех трех выбранных задач различны;
- сложности всех трех выбранных задач различны.
Перед вами стоит задача определить количество способов, которыми Монокарп может выбрать три задачи для тренировки.
Выходные данные
Выведите количество способов выбрать три задачи для тренировки, которые удовлетворяют описанным в условии требованиям.
Примечание
В первом примере можно взять следующие наборы по три задачи:
- задачи с номерами \(1\), \(2\), \(4\);
- задачи с номерами \(1\), \(3\), \(4\);
- задачи с номерами \(2\), \(3\), \(4\).
Таким образом, количество способов равно трем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
2 4
3 4
2 1
1 3
5
1 5
2 4
3 3
4 2
5 1
|
3
10
|