가장 긴 여행

Ópusztaszer에는 $N$개의 랜드마크가 있으며, 번호는 $0$부터 $N-1$까지 붙어 있다. 일부 랜드마크 쌍은 양방향으로 통행할 수 있는 도로로 연결되어 있다. 같은 쌍을 잇는 도로는 최대 한 개다. 주최 측은 어느 랜드마크끼리 연결되어 있는지 알지 못한다.

서로 다른 랜드마크 3개 사이의 도로가 최소 $\delta$개 있으면, 도로망의 밀도가 $\delta$ 이상이라고 한다. 즉 $0 \le u < v < w < N$을 만족하는 모든 삼중항 $(u, v, w)$에 대해, 쌍 $(u,v)$, $(v,w)$, $(u,w)$ 중 최소 $\delta$개가 도로로 연결되어 있다.

주최 측은 도로망의 밀도가 최소 $D$ 이상이라는 것을 알고 있다. $D$의 값은 3을 넘을 수 없다.

주최 측은 전화 교환원에게 호출을 하여 특정 랜드마크 사이의 도로 정보를 얻을 수 있다. 한 번의 호출에서는 비어 있지 않은 두 배열 $A[0], \ldots, A[P-1]$과 $B[0], \ldots, B[R-1]$을 지정해야 한다. $A$의 원소는 모두 서로 달라야 하고, $B$의 원소도 모두 서로 달라야 한다. 또한 $A$와 $B$에 같은 랜드마크가 함께 들어가서는 안 된다.

교환원은 $0 \le i < P$, $0 \le j < R$을 만족하는 모든 쌍 $i$, $j$를 확인한다. 그중 하나라도 $A[i]$와 $B[j]$가 도로로 연결되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

길이가 $l$인 여행은 서로 다른 랜드마크의 열 $t[0], t[1], \ldots, t[l-1]$이며, 모든 $0 \le i \le l-2$에 대해 $t[i]$와 $t[i+1]$이 도로로 연결되어 있다. 길이가 $l+1$ 이상인 여행이 존재하지 않으면, 길이 $l$인 그 여행을 가장 긴 여행이라고 한다.

여러분의 과제는 교환원에게 호출을 하여 Ópusztaszer에서 가장 긴 여행 하나를 찾는 것이다.

제한

• $3 \le N \le 256$
• 각 테스트 케이스에서 longest_trip에 대한 모든 호출의 $N$ 총합은 $1\,024$를 넘지 않는다.
• $1 \le D \le 3$