D. Гипотеза доктора Брауна
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Повстанцы потерпели поражение в последней битве с имперскими войсками, но появился луч новой надежды.

Тем временем на одной из завоеванных планет Люк готовился к нелегальным уличным гонкам (что не должно удивлять, учитывая историю его семьи). Люк прибыл к финишу с 88 милями в час на спидометре. Выйдя из машины, он был встречен новой реальностью. Оказалось, что битва еще не произошла и начнется ровно через $$$k$$$ часов.

Повстанцы разместили по одному линкору на каждой из $$$n$$$ планет. $$$m$$$ однонаправленных червоточин соединяют планеты. Прохождение каждой червоточины занимает ровно один час. Генералы Империума точно спланировали битву, но их войска не могут быстро адаптироваться к изменяющимся обстоятельствам. Поэтому повстанцам достаточно переместить несколько кораблей перед битвой, чтобы запутать противника, обеспечить победу и изменить судьбу галактики.

В силу многочисленных стратегических соображений, которые мы сейчас опустим, повстанцы хотели бы выбрать два корабля, которые поменяются местами так, чтобы оба они были в движении все время (ровно $$$k$$$ часов). Другими словами, повстанцы ищут две планеты $$$x$$$ и $$$y$$$ такие, что существуют пути длиной $$$k$$$ от $$$x$$$ до $$$y$$$ и от $$$y$$$ до $$$x$$$.

Из-за ограниченного запаса топлива выбор одного корабля также будет приемлемым. Этот корабль должен лететь через червоточины в течение $$$k$$$ часов, а затем вернется на исходную планету.

Сколько существует способов выбора кораблей для выполнения задания?

Входные данные

В первой строке ввода находятся три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$, $$$n^3 \leq k \leq 10^{18}$$$), обозначающие соответственно количество планет, червоточин и часов, оставшихся до начала битвы.

Следующие $$$m$$$ строк содержат по два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \ne y$$$), означающих, что существует однонаправленная червоточина от планеты $$$x$$$ до планеты $$$y$$$. Гарантируется, что не существует двух одинаковых червоточин, т. е. для любых двух червоточин либо $$$x_1 \neq x_2$$$, либо $$$y_1 \neq y_2$$$.

Выходные данные

В первой и единственной строке ваша программа должна вывести количество возможных вариантов выбора пары или одного военного корабля для миссии.

Примеры
Входные данные
7 8 346
1 2
1 3
2 4
3 4
4 5
5 1
6 7
7 6
Выходные данные
5
Входные данные
5 6 128
1 2
1 3
2 4
3 4
4 5
5 1
Выходные данные
6
Входные данные
3 3 30
1 2
2 3
3 2
Выходные данные
2
Примечание

В первом наборе входных данных можно выбрать пары кораблей со следующих планет: $$$2$$$ и $$$5$$$, $$$3$$$ и $$$5$$$, $$$1$$$ и $$$4$$$. Также можно было выбрать отдельные корабли с планет $$$6$$$ и $$$7$$$.

Во втором наборе входных данных можно выбрать пару кораблей из следующих планет: $$$2$$$ и $$$3$$$. Также можно было выбрать отдельные корабли с планет $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$.

В третьем наборе входных данных нет пар кораблей, которые мы можем выбрать. Также можно было выбрать отдельные корабли с планет $$$2$$$ и $$$3$$$.