연결된 마을

Pak Dengklek은 $0$부터 $N - 1$까지 번호가 매겨진 $N$개의 마을로 이루어진 나라인 인도네시아에 살고 있다. 모든 마을 쌍에 대해, 한 마을에서 다른 마을로 향하는 일방통행 도로가 하나 있다. Pak Dengklek은 도로의 방향에 관한 정보가 없지만, Pak Chanek이 그를 돕겠다고 제안했다.

Pak Dengklek은 Pak Chanek에게 최대 $40\;000$개의 질문을 할 수 있다. 각 질문에서 Pak Dengklek은 마을 한 쌍을 선택하고, Pak Chanek은 그 두 마을을 연결하는 도로의 방향을 알려 준다.

Pak Dengklek은 나가는 도로가 최대 하나인 마을의 번호를 알아내거나, 그러한 마을이 없다면 없다고 보고하려 한다. 그러한 마을이 둘 이상이라면, Pak Dengklek은 그중 아무 마을의 번호나 하나만 알아내면 된다.

구현 세부사항

다음 프로시저를 구현해야 한다.

int find_town(int N)

• $N$: 인도네시아에 있는 마을의 수.
• 이 프로시저는 나가는 도로가 최대 하나인 마을의 번호 중 아무 것이나 반환해야 하며, 그러한 마을이 없다면 $-1$을 반환해야 한다.
• 이 프로시저는 정확히 한 번 호출된다.

위 프로시저에서는 다음 프로시저를 호출할 수 있다.

bool check_road(int A, int B)

• $A, B$: Pak Chanek에게 물어볼 마을 번호 한 쌍.
• $A$와 $B$는 $0$ 이상 $N - 1$ 이하인 서로 다른 정수여야 한다.
• 마을 $A$에서 마을 $B$로 향하는 도로가 있으면 이 프로시저는 true를 반환하고, 마을 $B$에서 마을 $A$로 향하는 도로가 있으면 false를 반환한다.
• 이 프로시저는 최대 $40\;000$번 호출할 수 있다.

예제

예제 1

$3$개의 마을이 있고 마을들을 연결하는 도로가 다음 그림과 같은 상황을 생각해 보자.

프로시저 find_town은 다음과 같이 호출된다.

find_town(3)

이 프로시저는 check_road(0, 1)을 호출할 수 있으며, 이는 이 상황에서 true를 반환한다. 이 시점에는 마을 $1$에서 나가는 도로가 최대 하나라고 결론 내리기에 충분한 정보가 있다. 따라서 이 프로시저는 $1$을 반환할 수 있다.

또한 이 프로시저는 check_road(2, 1)을 호출할 수 있으며, 이는 이 상황에서 false를 반환한다. 이 시점에는 마을 $2$에서 나가는 도로가 최대 하나라고 결론 내리기에 충분한 정보가 있다. 따라서 이 프로시저는 $2$를 반환할 수도 있다.

예제 2

$5$개의 마을이 있고 마을들을 연결하는 도로가 다음 그림과 같은 상황을 생각해 보자.

프로시저 find_town은 다음과 같이 호출된다.

find_town(5)

이 상황에서는 나가는 도로가 최대 하나인 마을이 없다. 따라서 이 프로시저는 $-1$을 반환해야 한다.

제약 조건

• $3 \le N \le 2000$

서브태스크

1. (10점) $N \le 250$
2. (90점) 추가 제약 조건이 없다.

서브태스크 2에서는 부분 점수를 받을 수 있다. 이 서브태스크의 모든 테스트 케이스에 걸쳐 프로시저 check_road를 호출한 횟수의 최댓값을 $Q$라고 하자. 이 서브태스크에서 받는 점수는 다음 표에 따라 계산된다.

채점

일부 테스트 케이스에서 그레이더의 동작은 적응적이다. 이는 이러한 테스트 케이스에서 그레이더가 고정된 도로 방향 구성을 가지고 있지 않다는 뜻이다. 대신 그레이더가 주는 답은 여러분의 풀이가 한 질문에 따라 달라질 수 있다. 그레이더는 매번 답한 뒤 지금까지 주어진 모든 답과 일치하는 도로 방향 구성이 적어도 하나 존재하도록 답한다는 것이 보장된다.

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• $1$번째 줄: $N$
• $2 + i$번째 줄 ($0 \le i \le N - 1$): $R[i]$

샘플 그레이더가 프로토콜 위반을 감지하면 샘플 그레이더의 출력은 Protocol Violation: <MSG>이며, <MSG>는 다음 중 하나이다.

• too many questions: check_road가 $40\;000$번보다 많이 호출되었다.
• invalid parameters: check_road가 $0$ 이상 $N - 1$ 이하인 서로 다른 정수가 아닌 $A$와 $B$로 호출되었다.

그렇지 않으면 샘플 그레이더의 출력은 다음 형식이다.

• $1$번째 줄: find_town의 반환값.
• $2$번째 줄: check_road의 호출 횟수.

샘플 그레이더는 적응적이지 않다는 점에 유의하라.

샘플 그레이더는 인도네시아의 도로를 나타내는, 각각 $N$개의 문자를 갖는 $N$개 문자열의 배열 $R$을 읽는다. $0 \le i, j \le N - 1$이고 $i \ne j$인 각 $i$와 $j$에 대해, 마을 $i$에서 마을 $j$로 향하는 도로가 있으면 $R[i][j]$는 1이고, 마을 $j$에서 마을 $i$로 향하는 도로가 있으면 $R[i][j]$는 0이다. $0 \le i \le N - 1$인 각 $i$에 대해, $R[i][i]$는 0이어야 한다.