Handel

05.08.2011

Handel

Limit czasowy: 10000 milisekund
Limit pamięciowy: 32000 kilobajtów


Kraje zrzeszone w Unii Państw Północno-Południowo-Wschodnio-Zachodnich debatują nad swoimi wydatkami na wewnątrzunijne transakcje. W Unii znajduje się N państw (numerowanych od 1 do N), które zgłosiło łącznie M wymagań określających minimalną i maksymalną wartość wymiany handlowej między nimi.

Dokładniej, każde zgłoszone żądanie jest opisywane przez cztery liczby: a,b,l,h i oznacza, że krajowi a zależy na zakupie towarów z kraju b za kwotę co najmniej l, ale nie więcej niż h.

Zgodnie z najnowszymi dyrektywami unijnymi saldo każdego kraju członkowskiego w handlu wewnętrznym musi być zerowe, tj. dla każdego kraju łączna wartość jego międzypaństwowej sprzedaży musi być dokładnie równa wartości zakupów.

Sprawdź, czy spełnienie unijnych dyrektyw i żądań wszystkich krajów jest w ogóle możliwe.

Wejście

W pierwszej linii wejścia znajduje się liczba naturalna Z ( Z = 1 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pierwsza linia zestawu składa się z oddzielonych spacjami liczb naturalnych N oraz M ( 1 <= N <= 150, 0 <= M <= 1500 ), oznaczających kolejno liczbę krajów zrzeszonych w UPPPWZ oraz liczbę wszystkich wymagań państw członkowskich. W kolejnych M wierszach opisane są kolejne wymagania, i-te z nich składa się z czterech liczb całkowitych ai, bi, li, hi, które oznaczają, że kraj ai chciałby wydać na towary z kraju bi nie mniej niż li, ale i nie więcej niż hi ( 1 <= ai, bi <= N, 0 < li <= hi <= 150000 ). Każde dwie pary liczb spośród par (ai,bi) są różne. Żaden kraj nie handluje z samym sobą. Handel odbywa się tylko pomiędzy wymienionymi parami krajów.

Wyjście

Na wyjście należy wypisać liczb całkowitych, każda w osobnej linii, gdzie i-ta linia oznacza, ile kraj ai powinien przeznaczyć pieniędzy na handel z krajem bi. Jeśli istnieje wiele rozwiązań, można wypisać dowolne z nich. Dane testowe gwarantują istnienie przynajmniej jednego takiego kompromisowego planu transakcji.

Przykład

Wejście Wyjście
1
4 6
1 2 3 6
2 1 4 7
1 3 1 8
3 4 3 10
4 1 1 2
4 2 1 4
5
7
3
3
1
2
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com