{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"epigraph\"\u003e\u003cdiv class\u003d\"epigraph-text\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eIn the middle of difficulty lies opportunity. We make alliances with the hope of avoiding bloodshed.\u003c/span\u003e\u003c/div\u003e\u003cdiv class\u003d\"epigraph-source\"\u003e— Albert Einstein and Sun Tzu, \u003cspan class\u003d\"tex-font-style-it\"\u003eThe Art of War\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cp\u003eA shadow falls, bringing the end to the entire world. To struggle for survival, people decided to seek allies.\u003c/p\u003e\u003cp\u003eThere are $$$n$$$ people standing in a row, who are initially unfamiliar with each other.\u003c/p\u003e\u003cp\u003eAlso, there are $$$d$$$ \u003cspan class\u003d\"tex-font-style-it\"\u003econditions\u003c/span\u003e, the $$$i$$$-th of them restricting that $$$p_i$$$ is familiar with $$$q_i$$$.\u003c/p\u003e\u003cp\u003eNow, it\u0027s your decision time. Let\u0027s define that:\u003c/p\u003e\u003cp\u003eYour one \u003cspan class\u003d\"tex-font-style-it\"\u003eoperation\u003c/span\u003e is to choose two integers $$$i, j$$$ $$$(1 \\leq i, j \\leq n, i \\neq j)$$$, such that the $$$i$$$-th person and the $$$j$$$-th person were not familiar before, and make them familiar.\u003c/p\u003e\u003cp\u003eNote that if $$$a$$$ is familiar with $$$b$$$ and $$$b$$$ is familiar with $$$c$$$, then $$$a$$$ is familiar with $$$c$$$.\u003c/p\u003e\u003cp\u003eAt time $$$i$$$ $$$(1 \\leq i \\leq d)$$$, you can do at most $$$i$$$ \u003cspan class\u003d\"tex-font-style-it\"\u003eoperations\u003c/span\u003e, but you need to satisfy the \u003cspan class\u003d\"tex-font-style-it\"\u003econditions\u003c/span\u003e from $$$1$$$ to $$$i$$$ (inclusive). After the last \u003cspan class\u003d\"tex-font-style-it\"\u003eoperation\u003c/span\u003e of each time $$$i$$$, you need to calculate the maximal number of people that one person can be familiar with.\u003c/p\u003e\u003cp\u003eNote that the \u003cspan class\u003d\"tex-font-style-it\"\u003eoperations\u003c/span\u003e of each $$$i$$$ are \u003cspan class\u003d\"tex-font-style-bf\"\u003eindependent\u003c/span\u003e. It means that before you start your first \u003cspan class\u003d\"tex-font-style-it\"\u003eoperation\u003c/span\u003e at each time $$$i$$$, you need to assume that the $$$n$$$ people are unfamiliar with each other.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$t$$$ $$$(1 \\leq t \\leq 10 ^ 4)$$$, denoting the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains two integers $$$n$$$, $$$d$$$ $$$(2 \\leq n \\leq 10 ^ 5, 1 \\leq d \\leq n - 1)$$$.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$d$$$ lines contains two integers $$$p_i$$$, $$$q_i$$$ $$$(1 \\leq p_i, q_i \\leq n, p_i \\neq q_i)$$$, denoting the $$$i$$$-th \u003cspan class\u003d\"tex-font-style-it\"\u003econdition\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIt\u0027s guaranteed that the sum of $$$n$$$ over all test cases doesn\u0027t exceed $$$2 \\times 10 ^ 5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output $$$d$$$ lines, the $$$i$$$-th of them contains one integer $$$x$$$, denoting the maximal number of people that one person can be familiar with at time $$$i$$$.\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\u003e2\n7 6\n1 2\n3 4\n2 4\n7 6\n6 5\n1 7\n10 8\n1 2\n2 3\n3 4\n1 4\n6 7\n8 9\n8 10\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n3\n3\n3\n6\n1\n2\n3\n4\n5\n5\n6\n8\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 explanation for the first test case:\u003c/p\u003e\u003ccenter\u003e \u003ctable class\u003d\"tex-tabular\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"tex-tabular-text-align-center\"\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d61c9784ea2afff10dcc6664058f227b?v\u003d1726273189\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"302px\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"tex-tabular-text-align-center\"\u003e\u003cspan class\u003d\"tex-font-size-small\"\u003eVisual explanation\u003c/span\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e \u003c/center\u003e\u003cp\u003eIn this explanation, the circles and the numbers in them denote a person with the corresponding number. The line denotes that you decided to make two connected people familiar. The person marked with red has the maximal number of people that one person can be familiar with.\u003c/p\u003e\u003cp\u003eThese are \u003cspan class\u003d\"tex-font-style-bf\"\u003enot\u003c/span\u003e the only correct ways.\u003c/p\u003e"}}]}