Повстанцы потерпели поражение в последней битве с имперскими войсками, но появился луч новой надежды.
Тем временем на одной из завоеванных планет Люк готовился к нелегальным уличным гонкам (что не должно удивлять, учитывая историю его семьи). Люк прибыл к финишу с 88 милями в час на спидометре. Выйдя из машины, он был встречен новой реальностью. Оказалось, что битва еще не произошла и начнется ровно через \(k\) часов.
Повстанцы разместили по одному линкору на каждой из \(n\) планет. \(m\) однонаправленных червоточин соединяют планеты. Прохождение каждой червоточины занимает ровно один час. Генералы Империума точно спланировали битву, но их войска не могут быстро адаптироваться к изменяющимся обстоятельствам. Поэтому повстанцам достаточно переместить несколько кораблей перед битвой, чтобы запутать противника, обеспечить победу и изменить судьбу галактики.
В силу многочисленных стратегических соображений, которые мы сейчас опустим, повстанцы хотели бы выбрать два корабля, которые поменяются местами так, чтобы оба они были в движении все время (ровно \(k\) часов). Другими словами, повстанцы ищут две планеты \(x\) и \(y\) такие, что существуют пути длиной \(k\) от \(x\) до \(y\) и от \(y\) до \(x\).
Из-за ограниченного запаса топлива выбор одного корабля также будет приемлемым. Этот корабль должен лететь через червоточины в течение \(k\) часов, а затем вернется на исходную планету.
Сколько существует способов выбора кораблей для выполнения задания?
Выходные данные
В первой и единственной строке ваша программа должна вывести количество возможных вариантов выбора пары или одного военного корабля для миссии.
Примечание
В первом наборе входных данных можно выбрать пары кораблей со следующих планет: \(2\) и \(5\), \(3\) и \(5\), \(1\) и \(4\). Также можно было выбрать отдельные корабли с планет \(6\) и \(7\).
Во втором наборе входных данных можно выбрать пару кораблей из следующих планет: \(2\) и \(3\). Также можно было выбрать отдельные корабли с планет \(1\), \(2\), \(3\), \(4\) и \(5\).
В третьем наборе входных данных нет пар кораблей, которые мы можем выбрать. Также можно было выбрать отдельные корабли с планет \(2\) и \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 8 346
1 2
1 3
2 4
3 4
4 5
5 1
6 7
7 6
|
5
|
|
2
|
5 6 128
1 2
1 3
2 4
3 4
4 5
5 1
|
6
|
|
3
|
3 3 30
1 2
2 3
3 2
|
2
|