{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe mayor of ACMburg decided to reorganize the work of the city\r\npublic transport. There are \u003ci\u003eN\u003c/i\u003e bus stops in ACMburg, and \r\nsome of them are connected by roads. If two bus stop are \r\nconnected by a road, then a bus may go without additional stops\r\nfrom the first stop to the second stop as well as from the second \r\nstop to the first stop. No two stops are connected by more than \r\none road, and no road connects a stop with itself.\r\nA bus must stop at every stop along its route.\r\nAfter the reform, there are only circular routes with at least \r\nthree different stops, and on each route the stops do not repeat.\r\nAny two routes differ in at least one road. For the convenience \r\nof citizens, there are as many different routes (satisfying the \r\nabove conditions) as possible. The routes are numbered from 1 to\r\n\u003ci\u003eK\u003c/i\u003e. On each route there is exactly one bus, and the buses \r\nare numbered according to their routes.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAccording to the mayor\u0027s regulation, inspectors must examine\r\npassengers\u0027 tickets according to a certain schedule, which \r\nmust be arranged by city officials. The schedule must be \r\nin the form of a table with columns corresponding to bus routes\r\nand rows corresponding to time moments at which checks are \r\nperformed. \r\n\r\nIf there is a number \u003ci\u003eX\u003c/i\u003e in a cell [\u003ci\u003eT\u003c/i\u003e, \u003ci\u003eI\u003c/i\u003e], \r\nthen the bus \u003ci\u003eI\u003c/i\u003e stops for a ticket check at the stop \r\n\u003ci\u003eX\u003c/i\u003e at the moment \u003ci\u003eT\u003c/i\u003e. There may be empty cells in the \r\ntable. During a day, each bus must undergo a check at each stop \r\nexactly once, i.e., the number of nonempty cells in each column \r\nequals the number of stops on the corresponding route.\r\nTwo buses cannot be checked at the same stop simultaneously.\r\nAnd, of course , a bus cannot be at two different stops at \r\nthe same moment.\r\nIt is required to find the minimal number of lines in this table.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains the numbers of stops and roads in the \r\ncity: \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e (3 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 14). \r\nIn the next \u003ci\u003eM\u003c/i\u003e lines there are pairs of stops\r\nconnected by roads.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the minimal number of lines in the schedule.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\r\n1 2\r\n2 3\r\n1 3\r\n1 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}