IX Wiosenny Turniej
w Programowaniu Zespołowym
Politechnika Poznańska, 11.06.2005

Zadanie G - Podbój rynku

Opis

Anty-Patentowcy chcąc zdobyć przewagę na nowym rynku oprogramowania dla floty okrętów międzyplanetarnych postanowili każdy problem rozwiązywać najwcześniej jak to jest możliwe. W tym celu wszystkie problemy podzielili na małe zadania, każde o podobnej trudności, a więc i czasie rozwiązywania. Oczywiście wiele zadań można zacząć rozwiązywać dopiero, gdy inne zostaną zakończone. W tym celu zebrano informacje o wszystkich zależnościach. Ponieważ Anty-Anty-Patentowcy także pragną zdobyć dominującą rolę w Patentolandii, Anty-Patentowcy postanowili zatrudnić do rozwiązywania zadań taką liczbę osób, aby każde zadanie zostało wykonane jak najszybciej. Jednak dbając o koszty nie chcą zatrudniać żadnej osoby, która nie jest niezbędna.

Zadanie

Dane jest N zadań, o równym czasie wykonywania. Dodatkowo dana jest lista wszystkich zależności pomiędzy zadaniami. Każde zadanie może zostać wykonane dopiero, gdy zostaną wykonane wszystkie zadania od których zależy. Każde zadanie rozwiązywane jest przez jedną osobę. Każda osoba po skończeniu jednego zadania może zabrać się za kolejne. Twoim zadaniem jest znalezienie minimalnej liczby pracowników, takiej, że każde zadanie zostanie zakończone najwcześniej jak to możliwe, aby udziałowcy widzieli, że Anty-Patentowcy potrafią pracować sprawnie.

Wejście

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę następujących zestawów danych.

W pierwszej linii każdego zestawu znajdują się dwie liczby całkowite: 1≤N≤10000 oraz 0≤M≤100000 oznaczające odpowiednio: liczbę zadań i liczbę zależności. W następnych M liniach następują opisy zależności - po jednej w linii. Każda opisana jest przez parę liczb 1≤i,j≤N (i != j), oznaczające, że zadanie i można rozpocząć dopiero po zakończeniu zadania j.

Wejście

Dla każdego zestawu wypisz jedną liczbę całkowitą oznaczającą wymaganą liczbę pracowników lub "Brak rozwiazania", gdy rozwiązanie nie istnieje.

Przykładowe wejście

2
6 6
3 1
4 1
4 2
5 2
6 1
6 4
4 5
1 4
2 1
2 3
3 1
4 3

Przykładowe wyjście

3
Brak rozwiazania