{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003eYou have given the net consisting of nodes and pipes; pipes connect the nodes. Some substance can flow by pipes, and flow speed in any pipe doesn\u0027t exceed capacity of this pipe. \u003cbr\u003eThe substance cannot be accumulated in the nodes. But it is being produced in the first node with the non-negative speed and being consumed with the same speed in the last node. \u003cbr\u003eYou have some subset taken from the set of pipes of this net. You need to start the motion of substance in the net, and your motion must fully fill the pipes of the given subset. Speed of the producing substance in the first node must be minimal. \u003cbr\u003eCalculate this speed and show the scene of substance motion. \u003cbr\u003eRemember that substance can\u0027t be accumulated in the nodes of the net. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTwo positive integer numbers N (1\u0026lt;\u003dN\u0026lt;\u003d100) and M have been written in the first line of the input - numbers of nodes and pipes. \u003cbr\u003eThere are M lines follows: each line contains four integer numbers Ui, Vi, Zi, Ci; the numbers are separated by a space. Ui is the beginning of i-th pipe, Vi is its end, Zi is a capacity of i-th pipe (1\u0026lt;\u003dZi\u0026lt;\u003d10^5) and Ci is 1 if i-th pipe must be fully filled, and 0 otherwise. \u003cbr\u003eAny pair of nodes can be connected only by one pipe. If there is a pipe from node A to node B, then there is no pipe from B to A. Not a single node is connected with itself. \u003cbr\u003eThere is no pipe which connects nodes number 1 and N. Substance can flow only from the beginning of a pipe to its end. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eWrite one integer number in the first line of the output - it ought to be the minimal speed of the producing substance in the first node. \u003cbr\u003eWrite M integers in the second line - i-th number ought to be the flow speed in the i-th pipe (numbering of pipes is equal to the input). \u003cbr\u003eIf it is impossible to fill the given subset, write \"Impossible\". \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eInput 1: \u003cbr\u003e4 4 \u003cbr\u003e1 2 2 0 \u003cbr\u003e2 4 1 1 \u003cbr\u003e1 3 2 1 \u003cbr\u003e3 4 3 0 \u003cbr\u003eInput 2: \u003cbr\u003e4 4 \u003cbr\u003e1 2 1 0 \u003cbr\u003e2 4 2 1 \u003cbr\u003e1 3 3 1 \u003cbr\u003e3 4 2 0 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eOutput 1: \u003cbr\u003e3 \u003cbr\u003e1 1 2 2 \u003cbr\u003eOutput 2: \u003cbr\u003eImpossible \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003eDmitry Orlov \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003eSaratov ST team Spring Contest #1 \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003e18.05.2003 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}