{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eEach of Farmer John\u0027s \u003ci\u003eN\u003c/i\u003e cows (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.\u003c/p\u003e\u003cp\u003eFJ has already compared the milk output rate for \u003ci\u003eM\u003c/i\u003e (1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 10,000) pairs of cows. He wants to make a list of \u003ci\u003eC\u003c/i\u003e additional pairs of cows such that, if he now compares those \u003ci\u003eC\u003c/i\u003e pairs, he will definitely be able to deduce the correct ordering of all \u003ci\u003eN\u003c/i\u003e cows. Please help him determine the minimum value of \u003ci\u003eC\u003c/i\u003e for which such a list is possible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Line 1: Two space-separated integers: \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e\r\u003cbr\u003eLines 2..\u003ci\u003eM\u003c/i\u003e+1: Two space-separated integers, respectively: \u003ci\u003eX\u003c/i\u003e and \u003ci\u003eY\u003c/i\u003e. Both \u003ci\u003eX\u003c/i\u003e and \u003ci\u003eY\u003c/i\u003e are in the range 1...\u003ci\u003eN\u003c/i\u003e and describe a comparison where cow \u003ci\u003eX\u003c/i\u003e was ranked higher than cow \u003ci\u003eY\u003c/i\u003e."}},{"title":"Output","value":{"format":"HTML","content":"Line 1: A single integer that is the minimum value of \u003ci\u003eC\u003c/i\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\u003e5 5\r\n2 1\r\n1 5\r\n2 3\r\n1 4\r\n3 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\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":"From the information in the 5 test results, Farmer John knows that since cow 2 \u0026gt; cow 1 \u0026gt; cow 5 and cow 2 \u0026gt; cow 3 \u0026gt; cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 \u0026gt; cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 \u0026gt; cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: \"Is cow 1 \u0026gt; cow 3? Is cow 4 \u0026gt; cow 5? Is cow 5 \u0026gt; cow 3?\""}}]}