스피드런

마르셀은 새로운 WR(World Record)을 얻으려고 스피드런을 시작했다. 안타깝게도 새로 발견된 전략을 익히지 못해서, 부정한 이점을 얻을 방법을 찾아야 한다.

그가 실력을 키우려는 게임은 Tree Souls III이며, full-tree% 카테고리에서 WR을 노린다.

이름이 말해 주듯, 이 게임은 트리 위에서 진행된다. 트리는 정점 $N$개(번호는 $1$부터 $N$까지)와 간선 $N - 1$개로 이루어지며 사이클이 없는 그래프이다.

게임은 다음과 같이 진행된다. 캐릭터는 트리의 임의의 정점에 놓인다. 플레이어는 정수 $x$를 고르고, 현재 정점에서 정점 $x$까지 걸어가려고 시도할 수 있다. $x$와 현재 정점 사이에 간선이 있으면 캐릭터는 $x$로 이동한다. 간선이 없으면 아무 일도 일어나지 않는다. 모든 정점을 적어도 한 번 방문하면 스피드런은 유효하다.

이제 부정행위 이야기다. 그는 간선 순간이동 버그를 모르기 때문에 자신의 월드 시드를 직접 설정한다. 즉, 실행을 시작하기 전에 트리의 모양을 이미 알고 있다. 트리를 통째로 외우면 부정행위가 너무 뚜렷하게 드러나서 스피드런 커뮤니티에서 즉시 제재를 받게 된다. 그래서 그는 코드를 변조해 각 정점에 힌트를 심는다. 힌트는 길이가 $l$인 이진 문자열이며, 모든 정점의 힌트 길이는 $l$로 같다. 그는 어떤 정점에 서면, 그 정점에 할당된 힌트를 읽을 수 있다.

• $1 ≤ N ≤ 1\,000$
• goTo를 호출했을 때 false를 반환한 횟수를 $Q$라고 하자. 각 서브태스크에서 점수를 얻기 위해 지켜야 하는 $l$과 $Q$의 제약을 아래에 정리한다.