Connected Towns

시간 제한2초메모리 제한1024 MB

요약

두 마을을 고르면 도로 방향을 알려주는 질문을 4만 번 이하로 하여, 진출 차수가 1 이하인 마을을 찾거나 그런 마을이 없음을 밝힌다.

난이도: 보통10점 중 7점
유형: 그래프, 정렬, 분할 정복, 구간
정답자: 아직 제출이 없습니다

문제

Pak Dengklek lives in Indonesia, a country consisting of $N$ towns numbered from $0$ to $N - 1$ . For every pair of towns, there is a one-way road going from one town to the other. Pak Dengklek has no information on the direction of the roads, but Pak Chanek has offered to help him

Pak Dengklek is allowed to ask Pak Chanek at most $40\\,000$ questions. For each question in turn, Pak Dengklek chooses a pair of towns and Pak Chanek tells him the direction of the road connecting those two towns.

Pak Dengklek wants to know a town number with at most one outgoing road, or report if there is no such town. If there is more than one such town, Pak Dengklek only needs to know any of such town numbers.

제한

$3 ≤ N ≤ 2000$

예제

이 문제는 공개된 예제가 없습니다.