Problem description


Turniej szachowy
(F)
Limit pamięci: 1024 MB
Limit czasu: 3.00 s

Japońska społeczność miłośników Shogi (szachów japońskich) wzywa Cię na pomoc! Jak głosi miejska legenda, przy każdym z N skrzyżowań Tokio mieszka jakiś mistrz szachowy. Na dodatek, ostatniej nocy spadły dwa centymetry śniegu. Jak na tamtejsze standardy to bardzo dużo i niestety żadna z M ulic Tokio nie jest przejezdna.

Dzięki temu, że różni szachiści używają różnych technik gry, a każdy z nich opracowuje swoje własne taktyki, partie szachów bywają bardzo widowiskowe. Dokładniej rzecz biorąc, styl gry i-tego szachisty (mieszkającego przy i-tym skrzyżowaniu) można opisać nieujemną liczbą Xi. To, jak bardzo partia pomiędzy szachistami z a-tego i b-tego skrzyżowania będzie ciekawa, jest proporcjonalne do Xa ⊕ Xb (xor liczb Xa oraz Xb) . Intuicyjnie, taki model rzeczywiście wydaje się być właściwy – gra szachisty z nim samym byłaby dość nudna: Xa ⊕ Xa = 0, za to różnice w użyciu niektórych taktyk bardzo zwiększają widowiskowość pojedynków.

Po otrząśnięciu się z początkowego zaskoczenia, drogowcy przystąpili do udrażniania miasta i powoli odśnieżają ulice, jedna po drugiej. Szachiści mieli na dzisiaj zaplanowany bardzo ważny turniej, więc bardzo dłuży im się oczekiwanie na zakończenie pracy drogowców. Każdy z nich ciągle zastanawia się, jaką najciekawszą partię mógłby rozegrać z jakimś szachistą, z którym może się spotkać przy obecnym stanie infrastruktury drogowej. Oczywiście, w miarę jak kolejne ulice są odblokowywane, ich perspektywy mogą się poprawiać.

Jeśli odblokowanie pewnej ulicy spowodowało, że dany szachista może teraz rozegrać ciekawszą partię niż dotychczas, to bardzo się ucieszy i natychmiast opublikuje pochlebnego tweeta na temat władz miasta.

Dobry wizerunek w mediach społecznościowych jest bardzo ważny dla prezydenta Tokio. Dlatego chciałby wiedzieć, ilu pozytywnych tweetów może się spodziewać po odśnieżeniu każdej z ulic.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M, oznaczające odpowiednio liczbę skrzyżowań i ulic. Drugi wiersz wejścia składa się z N liczb X1, X2, …XN, pooddzielanych pojedynczymi odstępami, opisujących style gry kolejnych szachistów. Każdy z kolejnych M wierszy zawiera dwie liczby a i b opisujące ulicę łączącą skrzyżowania a oraz b. Ulice podane są w kolejności odśnieżania.

Wyjście

Na wyjściu należy wypisać M wierszy – i-ty z nich powinien zawierać liczbę szachistów, którym odśnieżenie i-tej ulicy umożliwiło dotarcie do przeciwników, z którymi mogą oni rozegrać ciekawszą partię niż dotychczas.

Ograniczenia

2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000, 0 ≤ Xi < 240.

We wszystkich testach oprócz przykładowych liczby Xilosowane niezależnie od siebie i jednostajnie z zakresu [0, 240).

Przykłady

Wejście Wyjście Wyjaśnienie
5 5
0 1 4 5 0
1 2
2 3
4 5
1 3
3 5
2
3
2
0
1

Oto indeksy szachistów, którzy tweetują po odśnieżeniu kolejnych dróg:

  1. 1, 2
  2. 1, 2, 3
  3. 4, 5
  4. 1

Oto najciekawsze partie dla poszczególnych zawodników po odśnieżeniu pierwszych dwóch ulic:

  • Dla szachisty 1 z szachistą 3 (0 ⊕ 4 = 4).
  • Dla szachisty 2 z szachistą 3 (1 ⊕ 4 = 5).
  • Dla szachisty 3 z szachistą 1 (1 ⊕ 4 = 5).

Czwarty i piąty szachista nie mają wyboru – mogą tylko grać sami ze sobą.

Odśnieżenie ostatniej ulicy nie zmienia sytuacji szachisty 4 – w szczególności jego partia z szachistą 1 jest tak samo ciekawa jak z 5.

Wejście Wyjście
8 7
0 1 2 3 4 5 6 7
1 2
3 4
5 6
7 8
2 4
6 8
4 8
2
2
2
2
4
4
8