Сегодня Пари задала Арию интересную графовую задачу. Арий написал неоптимальное решение, потому что верит, что может протолкнуть неоптимальное решение в любой задаче. Но его решение не только не оптимальное, оно ещё и содержит ошибки, а поскольку Арий долго пытался его оптимизировать, то код стал совсем «грязным». Арий продолжал получать вердикт Time Limit Exceeded и совсем уже расстроился, когда ему в голову пришла прекрасная идея!

Вот так выглядит сейчас его код:

dfs(v)
{
     set count[v] = count[v] + 1
     if(count[v] < 1000)
     {
          foreach u in neighbors[v]
          {
               if(visited[u] is equal to false)
               {
                    dfs(u)
               }
               break
          }
     }
     set visited[v] = true
}

main()
{
     input the digraph()
     TOF()
     foreach 1<=i<=n
     {
          set count[i] = 0 , visited[i] = false
     }
     foreach 1 <= v <= n
     {
          if(visited[v] is equal to false)
          {
               dfs(v)
          }
     }
     ... // And do something cool and magical but we can't tell you what!
}

Арий просит вас написать функцию TOF, которая будет уменьшать количество вызовов функции dfs. На вход подаётся ориентированный граф, и функция TOF должна переставить каким-то образом рёбра графа, то есть изменить порядок вершин в списке смежности neighbors каждой вершины. Количество вызовов функции dfs, разумеется, зависит от того, какой порядок для вершин в neighbors выбрать.