Chefbook

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Chief Chef has built a new social network call Chefbook. Everyone who is interested in cooking can join Chefbook. Already N chefs joined the chefbook and loved it so much.
In Chefbook, a chef can be a friend with other chefs (one or more). The friendship is not bidirectional that means if chef A is a friend of chef B, not necessarily chef B is a friend of chef A. Every chef x in Chefbook will give a likeness value L_{xy} to each of his Chefbook friend y. Likeness indicates how much he like his friend.
The Chief Chef wants that every chef in Chefbook should have friends with moderate likeness only. He does not like the fact one chef likes another chef too much or one chef does not like another chef at all. As he is the admin of the Chefbook, he decided to change the likeness value of some chef’s such that all the likeness value resides between a lower value and upper value. But changing likeness value for each friendship could be tedious and boring job. So Chief Chef comes up with a new idea. He will choose a chef x of Chefbook and increase likeness L_{xy} by P_{x} for all of his friends y. Another option is he will choose a chef y and decrease likeness L_{xy} by Q_{y} for all chef x such that y is a friend of x. The increase operation on x or decrease operation on y can be done only once. During any operation the intermediate value of L_{xy} can have any value but the final value of L_{xy} (for all x and y) should be in between S_{xy} and T_{xy} (inclusive), where S_{xy} and T_{xy} are the lower limit and upper limit respectively of the new likeness value W_{xy} of chef x for his friend y.
W_{xy} = L_{xy} + P_{x}  Q_{y}
Though Chief Chef wants to moderate the likeness value but he does not wants reduce overall likeness in Chefbook. So he decided to make the change such that sum of likeness W_{xy} should be as maximum as possible.
Input
The first line of input contains an integer T, denoting the number of test cases to follow.
The first line of each test case contains two space separated integers N and M, denoting the number of chefs in the Chefbook and number of friend relationship in Chefbook respectively. Followed by M lines, each containing five space separated integers x, y, L_{xy}, S_{xy} and T_{xy} such that y is a friend of x where L_{xy} is the y’s likeness value given by x and S_{xy} and T_{xy} are the lower and upper limit respectively of the new likeness W_{xy} set by Chief chef. Note that x and y can be same (a chef can like himself).
Output
First line of each test case will contain a single line with a single word "Unlike" (without the quotes) if it is not possible to change the likeness value according to the constraint described above. Otherwise each test case will consist of three lines. First line will contain a single integer SUM, which is the sum of the new likeness value W_{xy}. Next line will contain N space separated integers containing P_{x} (for all x = 1 to N). Similarly next line will contain N space separated integers containing Q_{y} (for all y = 1 to N). If there are several P and Q possible output anyone of them.
Note that, there will be no new friendship within these operation.
Constraints
 1≤T≤10
 1≤N≤100
 1≤M≤N^{2}
 1≤x, y≤N
 600≤L_{xy}≤600
 1000≤S_{xy}≤T_{xy}≤1000
 0≤P_{x}, Q_{y}≤10^{6}
Subtask
Subtask #1: Point 20
 1≤N≤20
Subtask #2: Point 80
 1≤N≤100
Example
Sample Input 2 2 4 1 1 2 5 10 1 2 4 8 10 2 1 3 5 10 2 2 2 7 10 2 4 1 1 1 7 7 1 2 7 7 7 2 1 7 7 7 2 2 7 7 7 Output for Sample Input 37 15 17 10 9 Unlike
Author:  shiplu 
Editorial  http://discuss.codechef.com/problems/CHEFBOOK 
Tags  hard, june15, lp, maxflow, shiplu 
Date Added:  8052015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions