Нумерація шляхів

Перехрестя в місті з'єднані вулицями з одностороннім рухом. Напишіть програму, яка обчислить кількість різних маршрутів між кожною парою перехресть. Маршрут — це послідовність односторонніх вулиць, що з'єднують два перехрестя.

Перехрестя позначаються невід'ємними цілими числами. Одностороння вулиця задається парою перехресть, які вона з'єднує. Наприклад, $\text{j k}$ означає, що є одностороння вулиця від перехрестя $j$ до перехрестя $k$. Зауважте, що двосторонню вулицю можна змоделювати двома односторонніми: $\text{j k}$ та $\text{k j}$.

Розглянемо місто з чотирма перехрестями, з'єднаними наступним чином:

$\text{0 1}$

$\text{0 2}$

$\text{1 2}$

$\text{2 3}$

Є один маршрут від перехрестя $0$ до $1$, два маршрути від $0$ до $2$ (це 0 \to 1 \to 2 та 0 \to 2), два маршрути від $0$ до $3$, один маршрут від $1$ до $2$, один маршрут від $1$ до $3$, один маршрут від $2$ до $3$ і жодного іншого маршруту.

Може трапитися так, що існує нескінченно багато різних маршрутів між деякими перехрестями. Наприклад, якщо до наведених вище вулиць додати $\text{3 2}$, то від $0$ до $1$ буде лиш один маршрут, але тепер існує нескінченно багато різних маршрутів від $0$ до $2$. Це пов'язано з тим, що після досягнення $2$ та $3$ можна скільки завгодно разів повторювати шлях між $2$ та $3$ у різні боки й отримувати нові різні маршрути. Наприклад, 0 \to 2 \to 3 \to 2 \to 3 \to 2 та 0 \to 2 \to 3 \to 2 — це різні маршрути.