Very Sparse Table
시간 제한30초메모리 제한2048 MB
0에서 n까지의 경로만 있는 방향 그래프에서 a→b와 b→c가 있으면 a→c를 추가하는 연산만으로 모든 v가 뒤쪽 u에 세 간선 이내로 도달하도록 만들어야 한다.
문제
This is an interactive problem.
You are given a directed graph on vertices numbered to . Initially, contains exactly edges of the form . Your task is to add some edges to this graph in such a way that for every two vertices () there exists a directed path from to consisting of at most three edges. There are also two additional requirements you must meet:
- You can add an edge if and only if there exists such that edges and are already present in .
- You can add at most edges in total.