Задан ацикличный ориентированный граф, состоящий из \(n\) вершин и \(m\) ребер. Граф не содержит кратных ребер и петель.
Вершина называется истоком, если в нее не входит ребер. Вершина называется стоком, если из нее не исходит ребер. Эти определения подразумевают, что некоторые вершины могут быть одновременно истоком и стоком.
Количество истоков в графе равно количеству стоков, и это число не превосходит \(20\).
К графу применяется следующий алгоритм:
- если в графе нет истоков и стоков, то выйти;
- выбрать произвольный исток \(s\), произвольный сток \(t\), добавить ребро из \(t\) в \(s\) в граф и перейти к шагу \(1\) (эта операция удаляет \(s\) из истоков и \(t\) из стоков). Обратите внимание, что \(s\) и \(t\) могут быть одной и той же вершиной, тогда добавляется петля.
В конце проверяется, стал ли граф сильно связным (любая вершина достижима из любой другой).
Ваша задача — проверить, что граф становится сильно связным вне зависимости от выбора истоков и стоков на втором шаге алгоритма.