Contest problemset description

Wyobraź sobie ogromną metropolię nocą, której układ ulic tworzy idealną, nieskończoną szachownicę. W samym centrum tego miejskiego labiryntu, na głównym skrzyżowaniu o współrzędnych (0,0), stoi gmach sztabu Partii Czerwonych. Tej nocy na każdym dostępnym skrzyżowaniu w mieście czuwa jeden działacz partyjny i – co kluczowe – w chwili rozpoczęcia akcji wszyscy oni deklarują wierność właśnie Czerwonym.

Sytuacja w mieście jest jednak napięta, a dotarcie do centrum utrudniają liczne awarie i roboty drogowe. Niektóre skrzyżowania są całkowicie rozkopane; nie można na nich stać ani przez nie przechodzić, co zmusza pieszych do kluczenia i szukania alternatywnych tras. Prezes wezwał wszystkich do swojej siedziby, ale na ten apel odpowiedzą tylko ci, którzy są w stanie dotrzeć do celu, pokonując pieszo maksymalnie S przecznic najkrótszą możliwą drogą, przemieszczając się w każdym kroku jedynie na pole stykające się krawędzią. Osoby te dotrą na spotkanie, wybierając trasę, która jest najkrótszą możliwą drogą do siedziby. Reszta, zniechęcona dystansem, pozostanie na swoich posterunkach.

Największym problemem nie jest jednak logistyka, lecz chwiejna natura samych działaczy. Ruszając ze swojego skrzyżowania, każdy polityk jest Czerwony, ale wystarczy spacer jedną przecznicą, by pod wpływem chwili zmienił barwy na Niebieskie. Po przejściu kolejnego odcinka do następnego skrzyżowania, sentyment powraca i znów staje się Czerwony, by po następnym kroku ponownie przejść na stronę opozycji. Ta polityczna karuzela trwa przez całą drogę, a każdy kolejny odcinek ulicy oznacza zmianę poglądów na przeciwne. Twoim zadaniem jest obliczyć, ilu z tych wędrowców, po pokonaniu plątaniny ulic, ostatecznie zamelduje się u prezesa jako lojalni Czerwoni, a ilu wejdzie do środka jako farbowani Niebiescy.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i S oznaczające kolejno liczbę zablokowanych skrzyżowań oraz maksymalną liczbę przecznic, którą politycy są w stanie pokonać. Następne N wierszy zawiera współrzędne remontowanych skrzyżowań. W i–tym z nich znajdują się dwie liczby całkowite X_i, Y_i reprezentujące współrzędne i–tego remonotwanego skrzyżowania.

Wyjście

Dwie liczby całkowite oddzielone spacją: liczba wędrowców, którzy dotrą jako lojalni Czerwoni i liczba wędrowców, którzy dotrą jako farbowani Niebiescy.

Ograniczenia

0 ≤ N ≤ 100 000, 1 ≤ S ≤ 10⁹, |X_i|, |Y_i| < 1 000, (X_i,Y_i) ≠ (X_j,Y_j) dla i ≠ j. Skrzyżowanie, znajdujące się przy głównym gmachu partii, nie jest zablokowane.

Przykład

0 2

9 4

4 5
-1 1
0 -1
0 1
1 0

10 16

4 50000
1 1
-1 -1
1 -1
-1 1

2500099997 2500000000

Ocenianie

W piwnicach Uniwersytetu Wrocławskiego są przechowywane radioaktywne chemikalia. Stworzono dla nich N specjalnych pomieszczeń, ponumerowanych od 1 do N. Pomieszczenia są połączone N − 1 korytarzami tak, aby z każdego można było dotrzeć do dowolnego innego.

Ze względu na swoje radioaktywne właściwości, chemikalia nie mogą znajdować się zbyt blisko siebie. Ustanowiono, że układ jest bezpieczny, jeśli dowolne dwa radioaktywne chemikalia są oddalone od siebie o co najmniej dwa korytarze.

Podane przykłady przedstawiają dwie sytuacje: (a) układ bezpieczny oraz (b) układ niebezpieczny.

Pracownicy uczelni czasem muszą posprzątać, co wymaga przestawienia chemikaliów do innych pomieszczeń. Jedyną możliwą operacją jest przeniesienie radioaktywnych chemikaliów przez korytarz do sąsiadującego pomieszczenia. Warunkiem koniecznym jest, aby układ pozostał bezpieczny.

Rozwiązanie 3-ciego przykładu

Jasio, pracownik Uniwersytetu Wrocławskiego, otrzymał od przełożonego aktualny oraz docelowy bezpieczny układ radioaktywnych chemikaliów. Jasio nie jest pewny, czy da się przenieść chemikalia w docelowe miejsca. Twoim zadaniem jest mu pomóc. Dla każdego przypadku testowego sprawdź, czy istnieje ciąg bezpiecznych operacji prowadzących z układu aktualnego do układu docelowego.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita T, oznaczająca liczbę przypadków testowych. Dla każdego przypadku testowego:

W pierwszym wierszu znajduje się liczba całkowita N – liczba pomieszczeń.

W kolejnych N − 1 wierszach znajdują się pary liczb całkowitych u_i, v_i, opisujące pomieszczenia połączone korytarzem.

Następnie podane są dwa binarne ciągi długości N, opisujące odpowiednio aktualne oraz docelowe układy chemikaliów. Jeśli w pokoju i znajdują się radioaktywne chemikalia to w ciągu na pozycji i znajduje się 1, a 0 w przeciwnym przypadku.

Podane dwa układy są bezpieczne oraz zawierają taką samą liczbę radioaktywnych chemikaliów.

Wyjście

Dla każdego z T przypadków testowych w osobnych liniach wypisz TAK jeśli da się przestawić radioaktywne chemikalia w docelowy układ lub wypisz NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ T ≤ 10⁵, ∑N ≤ 10⁶, 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i

Podzadania

Przykład

4
4
1 2
2 3
2 4
1001
0011
4
1 2
2 3
2 4
1001
1001
5
1 2
2 3
2 4
4 5
10010
00110
11
1 2
2 3
3 4
4 5
5 6
2 7
4 8
3 9
5 10
8 11
10000111000
10101001000

NIE
TAK
TAK
NIE

Jako, że święta tuż-tuż, to dwaj studenci postanowili posprzątać swój pokój pierwszy raz od momentu, gdy się do niego wprowadzili (wprowadzili się dwa lata temu).

Na podłodze wala się wiele śmieci różnych rodzajów. Wykształceni studenci świadomi są potrzeby ich segregacji, wobec czego w jednym przejściu od pokoju do śmietnika student weźmie pewną liczbę odpadów tego samego rodzaju.

Nasi bohaterowie są jednak sprytni. By nie przeszkadzać sobie nawzajem w zbieraniu syfu z podłogi, chodzą do śmietnika na zmiany: najpierw Student 1 zbiera jakieś śmieci i dopiero wtedy, gdy wychodzi je wyrzucić, Student 2 zaczyna zbierać swoje. Gdy Student 1 wraca zebrać więcej śmieci, Student 2 jest w drodze do śmietnika.

Student oczywiście nie będzie się przemęczał bardziej niż jego kolega student. Widząc, że współlokator wziął ze sobą x śmieci, w kolejnym przejściu nie weźmie ich więcej niż x. Z drugiej strony obaj chcieliby kiedyś skończyć, więc podczas każdego przejścia student zabierze przynajmniej jednego śmiecia. Podsumowując, jeśli jeden ze studentów zabrał ze sobą x śmieci, to drugi z nich w kolejnym przejściu zabierze pewną, wybraną przez siebie liczbę śmieci mieszczącą się w przedziale [1,x].

Ten z nich, który pierwszy skończy sprzątać – czyli na początku swojej tury zastanie podłogę czystą – natychmiast zacznie grać na komputerku (są biedni i mają jeden komputerek, więc drugi nie pogra; mają też jeden wspólny talerz).

Sprzątanie rozpoczyna Student 1. Ponieważ konsekwentnie oblewał każdy semestr wuefu, nie uniesie na raz więcej niż K śmieci.

Twoim zadaniem jest napisanie programu, który wczyta opis śmieci w ich pokoju, a następnie stwierdzi, czy Student 1 będzie mógł pograć na komputerku, niezależnie od wyborów Studenta 2.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i K oddzielone pojedynczym odstępem, oznaczające kolejno liczbę różnych rodzajów odpadów oraz maksymalny udźwig studenta.
W drugim wierszu wejścia znajduje się N liczb całkowitych, pooddzielanych pojedynczymi odstępami. Oznaczymy i-tą z nich przez A_i. Jest to liczba śmieci i-tego rodzaju.

Wyjście

Wyjście składa się z jednego wiersza.
W wierszu tym powinien znaleźć się napis TAK jeśli Student 1 może skończyć sprzątanie jako pierwszy niezależnie od wyborów Studenta 2.
W przeciwnym przypadku powinien znaleźć się tam napis NIE.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ K, A_i ≤ 10⁹.

Podzadania

Przykład

1 1
1

NIE

2 2
2 1

TAK

2 2
4 1

NIE

2 4
4 1

TAK