Problem description

Po ostatnim starciu ze sługami imperium rebelianci ponieśli olbrzymie straty i zostali rozbici, co oznacza, że nastały mroczne czasy dla naszego skrawka galaktyki. Na szczęście jeszcze nie cała nadzieja przepadła. W drodze na wykład tajnych kompletów w Bajtku obudziła się dusza rajdowca i rozpędził się przypadkiem do 142 kilometrów (88 mil) na godzinę. Kiedy dojechał na miejsce, okazało się, że do wielkiej bitwy zostało jeszcze dużo¹ czasu – ma do niej dojść dopiero za K godzin.

Rebelianci umieścili po jednym statku na każdej z N planet, pomiędzy którymi jest M jednokierunkowych tuneli czasoprzestrzennych. Pokonanie każdego z nich zajmuje dokładnie godzinę. Imperium bardzo dokładnie zaplanowało bitwę, ale jego wojska nie potrafią dynamicznie dostosowywać się do sytuacji. Dlatego wystarczy wytworzyć sztuczny ruch jednostek tuż przed bitwą, aby osiągnąć zwycięstwo. Ze względu na liczne i skomplikowane strategiczne uwarunkowania, które tutaj pominiemy, rebelianci ostrzeżeni przez Bajtka chcieliby wybrać dwa statki, które będą latać przez cały czas pozostały do bitwy (dokładnie K godzin), a każdy z nich ostatecznie wyląduje na planecie, z której startował przeciwny statek. Ze względu ma małą ilość paliwa, dopuszczalną strategią jest też wybranie jednego statku, który również będzie latał bez przerwy przez K godzin, a następnie wróci na swoją pierwotną pozycję.

Na ile sposobów dowództwo rebeliantów może wybrać statki do wypełnienia tej misji i odmienienia losów galaktyki?

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite N, M oraz K, oddzielone pojedynczymi odstępami, oznaczające odpowiednio liczbę planet, tuneli czasoprzestrzennych i godzin pozostałych do bitwy.
Kolejne M wierszy zawiera po dwie liczby całkowite x i y oznaczające istnienie tunelu czasoprzestrzennego, który może przenieść statek z planety x w dowolnym momencie na planetę y godzinę później.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą: liczbę możliwych sposobów wyboru dwójki lub pojedynczego statku.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000, N³ ≤ K ≤ 10¹⁸, 1 ≤ x, y ≤ N, x ≠ y.

Przykład

7 8 346
1 2
1 3
2 4
3 4
4 5
5 1
6 7
7 6

5