There are two integers, separated by a single space, in the first line of the standard input: n and m (1<=N<=100000,1<=M<=1000000), denoting the number of intersections and the number of streets in Byteburg, respectively. The intersections are numbered from 1 to n. The following m lines specify successive streets, one per line. Each of those lines holds four integers separated by single spaces: a,b, s and t(1<=a<b<=N, s,t属于集合[0,1]). Such a quadruple specifies that the intersections a and b are connected with a street,
You may assume that if there exists a set of routes to carry out Byteasar's plan, then there is one in which the total number of streets that the garbage truck follows does not exceed 5*M.
In tests worth 60% of the points it additionally holds that m<=10000.