Mamy daną liczbę n. Rozważamy n zmiennych całkowitych nieujemnych x1, x2, ..., xn. Mamy zadane nierówności między nimi: dla niektórych par i i j mamy powiedziane, że xi < xj, xi > xj lub xi = xj. Chcemy wyznaczyć najmniejsze k takie, że zmienne x1, x2, ..., xn można zwartościować liczbami całkowitymi z przedziału [0,k] tak, by wszystkie nierówności były zachowane.
Napisz program który:
W pierwszym wierszu wejścia będą podane dwie liczby całkowite 1 <= n <= 1000 oraz 0 < m < 10000, oznaczające odpowiednio liczbę zmiennych oraz liczbę zadanych nierówności. W drugim wierszu wejścia dane jest 3m liczb całkowitych oddzielonych pojedynczymi odstępami; kolejne trzy liczby 1 <= a,b <= n oraz c = -1, 0 lub 1. c=-1 oznacza xa<xb, c=0 oznacza xa=xb, c=1 oznacza xa>xb.
Twój program powinien wypisać jedną liczbę całkowitą k. W przypadku, gdy dla żadnego k nie można zrobić wartościowania, Twój program powinien wypisać słowo NO.
Dla danych:
4 4 1 2 -1 2 3 0 2 4 -1 3 4 -1
powinieneś wypisać:
2
Dla danych:
2 2 1 2 -1 2 1 -1
powinieneś wypisać:
NO
[Zgłoś rozwiązanie] [Moje zgłoszenia]