AlgoLiga 2018

Diament

Jasiu, znany specjalista od zabezpieczeń bankowych, ma dziś nie lada kłopot. Otóż nie pamięta hasła, dzięki któremu może wyłączyć laserowy system w bardzo ważnym pomieszczeniu. To pomieszczenie jest szczególnie chronione, znajduje się tam bowiem diament Hope. Jedyny sposób, aby wyłączyć system i wprowadzić nowe hasło, to dostać się do diamentu, pod którym znajduję się wyłącznik. Wygląda na to, że Jasiu będzie musiał czołgać się lub przeskakiwać wiązki laserowe. Wiadomo, że w każdym takim pomieszczeniu z diamentem, wyznaczono kwadrat o długości n, którego lewy dolny wierzchołek ma współrzędne (0,0), a prawy górny ma współrzędne (n, n). Na brzegu tego kwadratu znajdują się punkty o współrzędnych całkowitych, niektóre z tych punktów połączone są wiązkami laserowymi, które chronią cenny diament. Wiązkami laserowymi połączone są także sąsiednie wierzchołki kwadratu. Jasiu ma wszystkie informacje o wiązkach i położeniu diamentu, chce zminimalizować ryzyko włączenia alarmu, pokonując jak najmniej takich wiązek. Pomóż Jasiowi i napisz program, który wyznaczy najmniejszą liczbę promieni laserowych, jakie będzie musiał pokonać w drodze do diamentu, być może będzie z niego nie raz jeszcze korzystał. Jasiu zdradza dodatkowo, że nie istnieje punkt należący do kwadratu, w którym przecinają się więcej niż dwie wiązki laserowe, żadne dwie wiązki nie nakładają się oraz żadna wiązka nie przechodzi przez punkt diamentu. Ponadto wiadomo, że Jasiu jest tak chudy, że potrafi przecisnąć się przez jakąkolwiek niezerową odległość między dwoma punktami.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Dalej podane są przypadki testowe. Pierwszy wiersz każdego przypadku zawiera cztery liczby n, m, x, y (4 ≤ n ≤ 100, 0 ≤ m ≤ 2(n-1), 0 < x,y < n), gdzie n to liczba całkowita oznaczająca rozmiar kwadratu, m to liczba promieni laserowych przecinających wnętrze kwadratu, a x, y to współrzędne rzeczywiste, podane z dokładnością do dwóch miejsc po przecinku, wyznaczające położenie diamentu. W kolejnych m wierszach podane są po cztery liczby całkowite x₁, y₁, x₂, y₂ należące do brzegu kwadratu i oznaczające współrzędne początku i końca wiązki laserowej.

Wyjście
Dla każdego przypadku testowego należy wypisać najmniejszą liczbę promieni laserowych, które musi pokonać Jasiu, aby dotrzeć do diamentu.

Przykład

Wejście
1
6 7 3.00 3.00
1 0 0 5
2 0 6 4
3 0 1 6
4 0 4 6
5 0 0 3
0 4 5 6
2 6 6 2

Wyjście
2

Rysunek do przykładu.