Snurriga stolpar

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

요약

최대 1000개의 점이 주어질 때, 직선으로만 이동하고 점에서 반시계 방향으로 90도만 회전하는 자기 교차 없는 경로의 최대 길이를 구한다.

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

문제

OBS!!! Denna uppgift handlar inte om samma sorts stolpar som gruppindelning

Din flygande matta har börjat strula! Så länge den är tom är allt frid och fröjd, och den kan flyga var som helst i planet utan problem. Men så fort den lastats med något, så som magiska oljelampor, kan den inte längre svänga själv, utan måste svänga vid så kallade snurriga stolpar. Eftersom de snurriga stolparna bara kan rotera motsols 90 grader åt gången så kan mattan också bara svänga exakt 90 grader motsols i varje sväng. Dessutom blir den så snabbt överhettad att den lämnar ett brinnande spår efter sig så snart den är lastad med något. Därför kan den inte heller svänga flera gånger vid samma stolpe, det skulle ta så lång tid att den brann upp. Den kan inte heller korsa sin egen väg eller besöka en stolpe som den redan varit vid.

Och självklart är det just nu, när mattan är i sämre skick än någonsin, som du behöver den som mest. Rafaj har nämligen spridit ut alla sultanens magiska oljelampor på stans snurriga stolpar. Du måste nu samla in så många oljelampor som möjligt innan någon råkar släppa ut andarna och katastrofen blir ett faktum.

I planet finns $n \leq 1000$ snurriga stolpar med heltalskoordinater mellan $1$ och $m \leq 10^9$ , och på varje stolpe finns nu en magisk oljelampa. Du vill besöka så många stolpar som möjligt med den flygande mattan, genom att vandra på följande sätt:

Du får börja vid godtycklig stolpe, eftersom mattan kan flyga obehindrat då den är tom
Du får bara röra dig upp/ner/vänster/höger
Du får bara svänga vid stolpar, och bara 90 grader motsols (du kan alltså inte svänga medsols eller byta håll, du kan dock fortsätta rakt fram)
Din väg får inte korsa sig själv, eller besöka en stolpe flera gånger, då brinner mattan upp

Hur många stolpar kan du besöka?

입력

Den första raden innehåller ett heltal $n \ge 1$ . Därefter följer $n$ rader. Varje rad innehåller två positiva heltal $x,y \leq m$ , stolparnas koordinater. Det kommer aldrig att stå två stolpar på samma position.

출력

Skriv ut en rad med ett heltal, det största antal stolpar du kan besöka.

제한

$n ≤ 1000$
$m ≤ 10^9$

예제4

예제 1
입력
```
6
1 1
1 4
2 2
3 2
3 4
5 4
```
예상 출력
```
5
```
예제 2
입력
```
3
1 1
2 2
3 3
```
예상 출력
```
1
```

예제 3

입력

예상 출력

예제 4
입력
```
3
1 1
1 2
1 3
```
예상 출력
```
3
```