Tło zadania

To już nie wiadomo, które z kolei odrodzenie Yi Ai. Nowo narodzone kwiaty i dzwony pogrzebowe żegnające odchodzących przepływają przed jej oczami niczym strumień. To, co ma w głowie, wydaje się nie być wspomnieniami z przeszłości, lecz niezmienną przyszłością.

Zamiast nazywać tę nieskończoną torturę reinkarnacji „nieśmiertelnością”, lepiej byłoby podarować jej śmierć.

Jednak tym razem ponownie poczuła ten cień „możliwości” nieznanego. Przekroczyć rozpacz...

W niezliczonych restartach nie odtworzyły się tylko wspomnienia Yi Ai, ale także ta róża z „drugiego brzegu”, wyhodowana z nadziei, krwi i łez. To właśnie jest broń, dzięki której można stanąć do walki z „Nim”.

Treść zadania

Róża ta wyhodowała łącznie $n$ kwiatów, które tworzą strukturę drzewa. Wiadomo, że istnieje $m$ ścieżek, gdzie ścieżka $(a, b)$ oznacza, że zebranie wszystkich kwiatów na tej ścieżce pozwala wygenerować jedną jednostkę mocy przeciwko bóstwu. Jednak gdy ta moc zostanie wygenerowana, kwiaty te zostają zużyte i nie mogą zostać użyte w innych planach. Oznacza to, że można wybrać zbiór wierzchołkowo rozłącznych ścieżek na drzewie, z których każda generuje jedną jednostkę mocy. Yi Ai obliczyła już, ile maksymalnie jednostek mocy można zebrać z tych kwiatów, ale... brakuje tak niewiele.

Wystarczy jeszcze jedna jednostka mocy, aby móc stawić czoła bóstwu.

Yi Ai wyciąga miecz i robi ranę na swoim ramieniu. Chce wybrać jedną ścieżkę i splamić kwiaty na niej krwią, dzięki czemu zadziała starożytna magia, a kwiaty te będą mogły zostać użyte do wygenerowania nowej jednostki mocy.

Yi Ai chce wiedzieć, ile istnieje różnych ścieżek $(x, y)$, które może wybrać, takich że po uwzględnieniu tej ścieżki wraz z pierwotnymi $m$ ścieżkami, maksymalna liczba wierzchołkowo rozłącznych ścieżek, które można wybrać, jest większa niż liczba ścieżek, które można było wybrać z pierwotnych $m$ ścieżek.

Wypowiadam wojnę wieczności, szukając mnie —

Tak jak teraz, dziesięć palców splecionych.

Zestrzel słońce, ofiaruj mi —

Pamiętaj, ja jestem bogiem i buddą.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n, m$, oznaczające liczbę kwiatów róży oraz liczbę pierwotnych planów generowania mocy.

W kolejnych $n - 1$ liniach znajdują się po dwie liczby całkowite $u, v$, oznaczające, że kwiaty $u$ oraz $v$ są bezpośrednio połączone.

W kolejnych $m$ liniach znajdują się po dwie liczby całkowite $a, b$, oznaczające, że kwiaty na ścieżce od $a$ do $b$ mogą wygenerować jedną jednostkę mocy.

Wyjście

Wypisz jedną liczbę całkowitą, oznaczającą liczbę możliwych wyborów ścieżki $(a, b)$ przez Yi Ai.

Przykład

Wejście 1

8 6
1 2
1 3
1 4
1 5
5 6
5 7
7 8
2 3
2 4
3 4
1 6
5 6
5 8

Wyjście 1

8

Uwagi

Pierwotnie można było wybrać $2$ ścieżki, na przykład: $(2, 3), (5, 8)$.

Można dodać następujące ścieżki:

• Dodanie $(2, 2)$, można wybrać $3$ ścieżki: $(2, 2), (3, 4), (5, 8)$.
• Dodanie $(3, 3)$, można wybrać $3$ ścieżki: $(3, 3), (2, 4), (5, 8)$.
• Dodanie $(4, 4)$, można wybrać $3$ ścieżki: $(4, 4), (2, 3), (5, 8)$.
• Dodanie $(6, 6)$, można wybrać $3$ ścieżki: $(6, 6), (2, 3), (5, 8)$.
• Dodanie $(7, 7)$, można wybrać $3$ ścieżki: $(7, 7), (2, 3), (5, 6)$.
• Dodanie $(7, 8)$, można wybrać $3$ ścieżki: $(7, 8), (2, 3), (5, 6)$.
• Dodanie $(8, 7)$, można wybrać $3$ ścieżki: $(8, 7), (2, 3), (5, 6)$.
• Dodanie $(8, 8)$, można wybrać $3$ ścieżki: $(8, 8), (2, 3), (5, 6)$.

Zatem istnieje łącznie $8$ sposobów wyboru ścieżki.

Ograniczenia

Dla $100\%$ danych zapewnione jest $2\le n \le 3 \times 10^5, 0\le m \le 3\times 10^5, 1\le u, v, a, b\le n$.

Znaczenie typów danych:

A: Zapewnione $v = u + 1$.

B: Zapewnione $u = 1$.

C: Brak specjalnych ograniczeń co do kształtu drzewa.

1: Zapewnione $a = b$.

2: Brak specjalnych ograniczeń co do podanych ścieżek.