{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eСity N. has a huge problem with roads, food and IT-infrastructure. In total the city has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e junctions, some pairs of them are connected by bidirectional roads. The road network consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e roads, you can get from any junction to any other one by these roads. Yes, you\u0027re right — the road network forms an undirected tree.\u003c/p\u003e\u003cp\u003eRecently, the Mayor came up with a way that eliminates the problems with the food and the IT-infrastructure at the same time! He decided to put at the city junctions restaurants of two well-known cafe networks for IT professionals: \"iMac D0naldz\" and \"Burger Bing\". Since the network owners are not friends, it is strictly prohibited to place two restaurants of different networks on neighboring junctions. There are other requirements. Here\u0027s the full list:\u003c/p\u003e\u003cul\u003e \u003cli\u003e each junction must have at most one restaurant; \u003c/li\u003e\u003cli\u003e each restaurant belongs either to \"iMac D0naldz\", or to \"Burger Bing\"; \u003c/li\u003e\u003cli\u003e each network should build at least one restaurant; \u003c/li\u003e\u003cli\u003e there is no pair of junctions that are connected by a road and contains restaurants of different networks. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe Mayor is going to take a large tax from each restaurant, so he is interested in making the total number of the restaurants as large as possible.\u003c/p\u003e\u003cp\u003eHelp the Mayor to analyze the situation. Find all such pairs of \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e)\u003c/span\u003e that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e restaurants can belong to \"iMac D0naldz\", \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e restaurants can belong to \"Burger Bing\", and the sum of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e + \u003ci\u003eb\u003c/i\u003e\u003c/span\u003e is as large as possible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first input line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5000)\u003c/span\u003e — the number of junctions in the city. Next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e lines list all roads one per line. Each road is given as a pair of integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e)\u003c/span\u003e — the indexes of connected junctions. Consider the junctions indexed from 1 to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the given road network is represented by an undirected tree with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e vertexes.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint on the first line integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e\u003c/span\u003e — the number of sought pairs. Then print all sought pairs \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e)\u003c/span\u003e in the order of increasing of the first component \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","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\n1 2\n2 3\n3 4\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 3\n2 2\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e10\n1 2\n2 3\n3 4\n5 6\n6 7\n7 4\n8 9\n9 10\n10 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n1 8\n2 7\n3 6\n6 3\n7 2\n8 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe figure below shows the answers to the first test case. The junctions with \"iMac D0naldz\" restaurants are marked red and \"Burger Bing\" restaurants are marked blue.\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/a7f5d887d313a6dc2686690d6be5f3aa?v\u003d1715012106\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}