{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Oh those picky N (1 \u0026lt;\u003d N \u0026lt;\u003d 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 \u0026lt;\u003d A \u0026lt;\u003d B \u0026lt;\u003d 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.\r\u003cbr\u003e\r\u003cbr\u003eHelp FJ by determining:\u003cul\u003e\u003cli\u003eThe minimum number of stalls required in the barn so that each cow can have her private milking period\u003c/li\u003e\u003cli\u003eAn assignment of cows to these stalls over time\u003c/li\u003e\u003c/ul\u003eMany answers are correct for each test dataset; a program will grade your answer."}},{"title":"Input","value":{"format":"HTML","content":"Line 1: A single integer, N\r\u003cbr\u003e\r\u003cbr\u003eLines 2..N+1: Line i+1 describes cow i\u0027s milking interval with two space-separated integers."}},{"title":"Output","value":{"format":"HTML","content":"Line 1: The minimum number of stalls the barn must have.\r\u003cbr\u003e\r\u003cbr\u003eLines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period."}},{"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\u003e5\r\n1 10\r\n2 4\r\n3 6\r\n5 8\r\n4 7\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n1\r\n2\r\n3\r\n2\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Explanation of the sample:\r\u003cbr\u003e\r\u003cbr\u003eHere\u0027s a graphical schedule for this output:\r\u003cbr\u003e\r\u003cbr\u003e\u003cpre\u003eTime 1 2 3 4 5 6 7 8 9 10\r\u003cbr\u003eStall 1 c1\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\r\u003cbr\u003eStall 2 .. c2\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt; c4\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt; .. ..\r\u003cbr\u003eStall 3 .. .. c3\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt; .. .. .. ..\r\u003cbr\u003eStall 4 .. .. .. c5\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt;\u0026gt; .. .. ..\u003c/pre\u003eOther outputs using the same number of stalls are possible."}}]}