{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\u003csection\u003e\n \u003cp\u003eThere is a tree with $N$ vertices. The $i^{th}$ edge connects vertices $A_i$ and $B_i$ bidirectionally.\u003c/p\u003e\n \u003cp\u003eTwo players play a game on this tree. Initially, there are positioned at vertices $u$ and $v$, respectively. The game continues as follows:\u003c/p\u003e\n \u003col\u003e\n \u003cli\u003eIf both players are positioned at the same vertex, the game ends. Otherwise, the first player moves to a vertex of his choice that is adjacent to his current vertex.\u003c/li\u003e\n \u003cli\u003eIf both players are positioned at the same vertex, the game ends. Otherwise, the second player moves to a vertex of his choice that is adjacent to his current vertex.\u003c/li\u003e\n \u003cli\u003eRepeat from step $1$.\u003c/li\u003e\n \u003c/ol\u003e\n \u003cp\u003eThe first player performs his moves so that the game ends as late as possible, while the second player performs his moves so that the game ends as early as possible.\u003c/p\u003e\n \u003cp\u003eFind the number of moves \u003ci\u003ethe second player\u003c/i\u003e will perform before the end of the game if both of the players know each other\u0027s position and strategy.\u003c/p\u003e\n \u003cp\u003eIt can be proved that the game is bound to end.\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"Constraints","value":{"format":"HTML","content":"\u003csection\u003e\n \u003cul\u003e\n \u003cli\u003e\u003cvar\u003e\\(2 \\leq N \\leq 10^5\\)\u003c/var\u003e\u003c/li\u003e\n \u003cli\u003e\u003cvar\u003e\\(1 \\leq u,v \\leq N\\)\u003c/var\u003e\u003c/li\u003e\n \u003cli\u003e\u003cvar\u003e\\(u \\neq v\\)\u003c/var\u003e\u003c/li\u003e\n \u003cli\u003e\u003cvar\u003e\\(1 \\leq A_i,B_i \\leq N\\)\u003c/var\u003e\u003c/li\u003e\n \u003cli\u003eThe given graph is a tree.\u003c/li\u003e\n \u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003csection\u003e\n \u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\n \u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(u\\)\u003c/var\u003e \u003cvar\u003e\\(v\\)\u003c/var\u003e\n\u003cvar\u003e\\(A_1\\)\u003c/var\u003e \u003cvar\u003e\\(B_1\\)\u003c/var\u003e\n\u003cvar\u003e\\(:\\)\u003c/var\u003e\n\u003cvar\u003e\\(A_{N-1}\\)\u003c/var\u003e \u003cvar\u003e\\(B_{N-1}\\)\u003c/var\u003e\n\u003c/pre\u003e\n\u003c/section\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003csection\u003e\n \u003cp\u003ePrint the number of moves the second player will perform before the end of the game.\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"Sample 1","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 4 1\n1 2\n2 3\n3 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\u003csection\u003e\n \u003cp\u003eIf both players play optimally, the game will progress as follows:\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003eThe first player moves to Vertex \u003cvar\u003e\\(3\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eThe second player moves to Vertex \u003cvar\u003e\\(2\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eThe first player moves to Vertex \u003cvar\u003e\\(5\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eThe second player moves to Vertex \u003cvar\u003e\\(3\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eThe first player moves to Vertex \u003cvar\u003e\\(3\\)\u003c/var\u003e.\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eHere, the second player performs two moves.\u003c/p\u003e\n \u003cp\u003eNote that, in each move, it is prohibited to stay at the current vertex.\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"Sample 2","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 4 5\n1 2\n1 3\n1 4\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\u003csection\u003e\n\u003c/section\u003e"}},{"title":"Sample 3","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 1 2\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\u003csection\u003e\n\u003c/section\u003e"}},{"title":"Sample 4","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\u003e9 6 1\n1 2\n2 3\n3 4\n4 5\n5 6\n4 7\n7 8\n8 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003csection\u003e\n\u003c/section\u003e\u003csection\u003e\n\u003c/section\u003e"}}]}