AlgoLiga 2018

Ed i Edie grają w grę planszową. Na planszy znajdują się pola ponumerowane od 0 do n-1, a na każdym z nich może stać wiele pionków. Niektóre pola mają drogi prowadzące na inne pola (drogi nie tworzą cykli). Połączenia te umożliwiają pionkom przechodzenie z jednego pola na drugie. Ed i Edie wykonują ruchy na przemian. W jednym ruchu gracz może wziąć maksymalnie jeden pionek i przesunąć go na dowolne inne pole, do którego prowadzi droga, albo przeczekać swoją turę. Żeby zapewnić skończoność gry Ed może przeczekać maksymalnie a tur, a Edie maksymalnie b tur. Grę zawsze zaczyna Ed. Przegrywa ten, kto nie może wykonać ruchu.

Mając daną liczbę pól, liczbę łączących je dróg, rozmieszczenie pionków oraz liczbę tur jakie mogą przeczekać Ed i Edie, wyznacz zwycięzcę rozgrywki. Należy założyć, że zarówno Ed jak i Edie będą grali według strategii optymalnej.

Wejście

W pierwszej linii wejścia znajdują się dwie liczby naturalne n ∈ [1;10⁶] i m ∈ [1;2×10⁶] oznaczające kolejno liczbę pól oraz liczbę łączących je dróg.

W każdej z następnych m linii znajdują się dwie liczby naturalne a ∈ [0;n) i b ∈ [0;n) oznaczające, że istnieje droga z a do b.

W następnej linii znajduje się n liczb naturalnych. Liczba i-ta w kolejności oznacza ilość pionków znajdujących się na polu i-1. Wartość każdej z tych liczb nie przekracza 10⁹.

W ostatniej linii wejścia znajdują się dwie liczby a ∈ [0;10] i b ∈ [0;10], oznaczające kolejno ilość tur jakie może przeczekać Ed i ilość tur jakie może przeczekać Edie.

Wyjście

Na wyjściu należy wypisać Ed jeśli rozgrywkę wygrał Ed albo Edie w przeciwnym wypadku.

Przykład

Wejście:

6 6
0 2
0 1
1 3
1 2
2 4
3 5
0 1 2 0 1 1
9 9

Wyjście:

Edie