Keçirici Bağlanma#3330
ICPC təlimlərində öyrədilməli olan əsas məsələlərdən biri istiqamətli qrafın tranzitiv bağlanmasını hesablamaqdır. Bu konsepsiya o qədər sadədir ki, bir professor bu problemi Warshall alqoritmi ilə həll etməyi təklif edir. ICPC-nin əlavə tapşırıqlarından biri olaraq, iştirakçıların bu texnikanı həqiqətən mənimsəyib-mənimsəmədiklərini yoxlamaq istəyirik.
Verilmiş istiqamətli qraf G = < V, E > ilə N = |V| təpələr (2 ≤ N ≤ 2500) və M = |E| kənarları (1 ≤ M ≤ 10000), onun tranzitiv bağlanması V üzərində ikili əlaqə R-dir. İki təpə, A və B, R-də əlaqəlidirlər əgər A-dan B-yə istiqamətli yol varsa. Burada istiqamətli yol qrafın C_0C_1, C_1C_2, ..., C_{K-1}C_K kənarlarının ardıcıllığıdır ki, A = C_0 və B = C_K. Sizin tapşırığınız R-ni hesablamaqdır.
Çünki R çox böyük ola bilər, biz çıxışı sadələşdirməyə qərar verdik. Qraf G-də təpə X-dən təpə Y-yə yol olduğu halda, X Y-yə bərabər olmayan (X, Y) sıralı cütlərinin sayını hesablayın.
Girişin ilk sətri testlərin sayını göstərən T (T ≤ 10) tam ədədini ehtiva edir. Aşağıdakı sətirlər hər bir test halını aşağıdakı formatda təsvir edir.
Test halının ilk sətri iki tam ədəd N və M ibarətdir. Növbəti M sətirin hər biri 2 tam ədəd, A və B ehtiva edir ki, bu da A-dan B-yə istiqamətli kənar olduğunu göstərir. Təpələr 1-dən N-ə qədər nömrələnir və qraf təsvirində təkrarlanan kənarlar olmayacaq.
Hər bir hal üçün, X-dən Y-yə yol olduğu halda, X Y-yə bərabər olmayan (X, Y) sıralı cütlərinin sayını göstərən tam ədəd çıxarın.
Nümunə 1