[Medium] MonsterFarm

각 pinguo 들을 그래프의 정점으로 두고 pinguo i 가 죽었을 때 살아나는 pinguo v에 대해 i->v 인 단방향 간선을 이어준다. 다음과 같은 성질을 갖는 정점 u가 존재하면 pinguo의 수는 무한히 늘어난다. 1) 정점 0에서 정점 u로 도달할 수 있다. 2) 정점 u에서 출발하여 한 개 이상의 간선을 타고 다시 정점 u로 돌아올 수 있다. 3) 정점 u의 out degree 가 2 이상이다. 이것은 간단하게 보일 수 있다. u의 out degree 가 2 이상이라는 것은 u가 1마리 죽으면 2마리 이상의 pinguo 가 생긴다는 뜻이다. 그런데 u로 갔다가 다시 u로 돌아오는 방법이 존재하므로 전체 pinguo의 수는 무한히 늘어나게 된다. 그렇다면 저런 성질을 갖는 점이 없다면 pinguo의 수는 유한하게 수렴할까? 그것도 맞는 말이다. 이것은 다음과 같이 보일 수 있다. 1)을 만족하지 않는 점은 있으나 없으나 답에 영향을 주지 않으므로 관심에서 제거해도 된다. 2)를 만족하는 어떤 점 u가 존재한다고 해보자. 2)를 만족한다는 것은, 이 점이 어떤 사이클에 속한다는 뜻이다. 가정에 의해 이 점은 3)를 만족하지 않는다. 그렇다고 해서 out degree 가 0 일리는 없으므로 이 점의 out degree는 1 이다. 따라서 링 모양의 사이클을 이루게 된다. 이 안에서는 pinguo 의 수가 변하지 않고 유지되는 것이 자명하다. 남은 점들은 2)를 만족하지 않는 점들이다. 이런 점들은 어느 사이클에도 속하지 않기 때문에 DAG를 이루게 된다. DAG 위에서는 pinguo 의 수가 늘어나긴 하는데, 무한히 늘어나지 않고 유한한 선에서 멈추게 된다. 이제 실제로 답을 구해보자. 우선 위의 성질을 갖는 정점이 있는지 확인하고 있으면 -1을 리턴. 없다면 pinguo 의 수가 유한하게 수렴한다는 뜻이다. pinguo 가 죽고 살아나는 과정을 여러번 시뮬레이션 한 후 평형 상태의 pinguo의 수를 다 더해서 리턴하면 된다. 시뮬레이션은 최대 몇 번을 수행해야 할까? pinguo의 수는 DAG 부분에서만 늘어날 수 있기 때문에 DAG 부분의 최장경로의 길이 = N번 만 반복해주면 된다.