정올 주식회사는 N명의 직원으로 이루어져 있다.

정확히 1명의 회장을 제외한 나머지 모든 직원은, 본인의 직속 상사를 정확히 한 명 가지고 있으며,
모든 직원은 자신의 상사를 따라서 계속 올라간다면 결국 회장을 만나게 될 때, 이 구조를 '안정적인 회사' 라 부른다.

어느 날 구조조정의 시간이 다가왔다. 이 구조조정은 다음과 같이 이루어진다.

서로 다른 두 직원 a와 b를 뽑는다. 이때 둘은 직원 - 직속 상사 관계임이 보장된다.
(누가 상사인지는 모른다, 또한 회장도 여기에 뽑힐 수 있다.)
두 직원의 관계를 역전한다. 즉, a와 b의 직원 - 직속 상사 관계를 뒤바꾼다.

물론, 마구잡이식의 구조조정은 '안정적인 회사'를 유지할 수 없게 한다.

구조조정안 Q개에 대해, 각 조정안의 결과가 '안정적인 회사'인지 판별해보자.

각 조정안은 순서대로 제공되며, 이 조정안은 누적된다.

즉, i번째 조정안은 i-1번째 조정안을 적용한 상태에서 직원 쌍 하나를 추가로 역전시키는 안이다.

초기 상태가 안정적인 회사가 아닐수도 있음에 유의하라.

그러나, 모든 테스트 케이스에 대해, 적절한 구조조정안을 통해 안정적인 회사를 만들 수 있다는 보장을 할 수 있다.

구조조정 timer 1s memory 1024MB

구조조정 1s 1024MB