Verið er að nýta sumarið í viðhaldsvinnu og Veitum vantar
aðstoð við að skipuleggja vatnslagnir. Búið er að finna
uppsprettur sem þarf
nú að tengja við
neytendur. Hver uppspretta gefur nákvæmlega og þægilegt nokk geta
lagnirnar flutt nákvæmlega . En hver neytandi þarf að fá jafn mikið
vatn og allir aðrir, annars myndast ósætti sem gengur ekki. Til
þess að laga þetta er hægt að skeyta saman lögnum. Hver
samskeytipunktur getur haft allt að tveimur inntökum og allt að
tveimur úttökum. Flæði út er ávallt jafnt flæði inn, en þar til
viðbótar passar samskeytingin upp á að ef tvö úttök eru til
staðar muni flæðið um bæði úttök ávallt vera jafn mikið. Einnig
eru lagnirnar útbúnar ventilum svo ef lögn er lögð frá
til flæðir vatnið aðeins í þá átt,
ekki til baka. Nú þarf að skipuleggja hvernig raða má niður
samskeytipunktum og lögnum til að tengja inntök við úttök. Hver
neytandi þarf að fá . Einnig þarf að passa upp á að hver lögn
geti aðeins tekið , samskeytingarnar geta hins vegar þolað
allt sem lagnirnar bera í þær. Uppspretturnar eru númeraðar
og
neytendur . Fjármagn er ekki endalaust, svo heildarfjöldi
samskeyta í úttaki má mest vera . Eins má heildarfjöldi
lagna ekki vera meiri en . Loks má ekki leggja lögn út frá neytanda.
Inntak
Inntakið inniheldur tvær heiltölur .
Úttak
Fyrsta lína úttaks skal innihalda tölurnar og , fjölda samskeyta,uppsprettur og
neytendur meðtaldir, og fjöldi lagna milli þeirra. Ný samskeyti
eru þá númeruð . Næst skulu koma línur, hver lýsir einni lögn. Ef
lögnin liggur frá samskeytum til skal prenta og með einu bili á milli.
Ef til eru margar lausnir máttu skrifa út einhverja
þeirra.
Sample Input 1 |
Sample Output 1 |
1 2
|
3 2
1 2
1 3
|
Sample Input 2 |
Sample Output 2 |
1 5
|
11 12
1 7
1 8
7 1
7 9
8 10
8 11
9 1
9 2
10 3
10 4
11 5
11 6
|
Sample Input 3 |
Sample Output 3 |
3 5
|
15 19
1 9
1 8
2 7
2 6
3 5
3 4
9 10
9 11
10 12
10 15
11 13
11 14
12 15
12 4
13 5
13 6
14 7
14 8
15 9
|