Транзитивне Замикання#3330

Транзитивне Замикання

3 секунди

64 мегабайти

Дуже легка

У майже всіх тренуваннях ICPC одним із основних елементів, які потрібно вміти обчислювати (або навіть краще, знати напам'ять), є транзитивне замикання орієнтованого графа. Оскільки ця концепція є настільки фундаментальною, один професор пропонує вирішити цю задачу, використовуючи алгоритм Уоршалла. Як одне з бонусних завдань цього ICPC, ми хотіли б перевірити, чи дійсно учасники опанували цю техніку.

Дано орієнтований граф $G =< V, E >$ G = < V, E > з $N = ∣ V ∣$ N = |V| вершинами ( $2 \leq N \leq 2500$ 2 \leq N \leq 2500) та $M = ∣ E ∣$ M = |E| ребрами ( $1 \leq M \leq 10000$ 1 \leq M \leq 10000). Його транзитивне замикання є бінарним відношенням $R$ на $V$ таке, що дві вершини, $A$ та $B$ , пов'язані у $R$ , якщо існує орієнтований шлях від $A$ до $B$ . Орієнтований шлях - це послідовність ребер графа $C_{0} C_{1}$ C_0C_1, $C_{1} C_{2}$ C_1C_2, ..., $C_{K - 1} C_{K}$ C_{K-1}C_K така, що $A = C_{0}$ A = C_0 та $B = C_{K}$ B = C_K. Ваше завдання - обчислити $R$ .

Оскільки $R$ може бути дуже великим, ми вирішили спростити вихідні дані. Обчисліть кількість впорядкованих пар $(X, Y)$ (X, Y), де $X$ не дорівнює $Y$ , таких, що існує шлях від вершини $X$ до вершини $Y$ у графі $G$ .

Вхідні дані

Перша строка вхідних даних містить ціле число $T$ ( $T \leq 10$ T \leq 10), що позначає кількість тестових випадків. Наступні строки описують кожен тестовий випадок у наступному форматі.

Перша строка тестового випадку складається з двох цілих чисел $N$ та $M$ . Кожна з наступних $M$ строк містить $2$ цілі числа, $A$ та $B$ , що позначають, що існує орієнтоване ребро від $A$ до $B$ . Вершини пронумеровані від $1$ до $N$ , і не буде повторюваних ребер у описі графа.

Вихідні дані

Для кожного випадку виведіть ціле число, що позначає кількість впорядкованих пар $(X, Y)$ (X, Y), де $X$ не дорівнює $Y$ , таких, що існує шлях від вершини $X$ до вершини $Y$ .

Приклади

Приклад 1