{"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\u003eWe have a tree with \u003cvar\u003e\\(N\\)\u003c/var\u003e vertices. The \u003cvar\u003e\\(i\\)\u003c/var\u003e-th edge connects vertices \u003cvar\u003e\\(A_i\\)\u003c/var\u003e and \u003cvar\u003e\\(B_i\\)\u003c/var\u003e.\u003c/p\u003e\n \u003cp\u003eAlice is standing at vertex \u003cvar\u003e\\(u\\)\u003c/var\u003e, and Bob is standing at vertex \u003cvar\u003e\\(v\\)\u003c/var\u003e. They play a game as follows:\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003e\n \u003cp\u003e If Alice and Bob are standing at the same vertex, the game ends. Otherwise, Alice must move to any vertex adjacent to her current vertex.\u003c/p\u003e\u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIf Alice and Bob are standing at the same vertex, the game ends. Otherwise, Bob must move to any vertex adjacent to his current vertex.\u003c/p\u003e\u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eRepeat from the first step.\u003c/p\u003e\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eAlice plays so that the game ends as late as possible, while Bob plays so that the game ends as fast as possible. Find the number of moves Bob will perform before the end of the game if both Alice and Bob know each other\u0027s position and strategy at every moment and play according to that.\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 Bob 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\u003eAlice moves to Vertex \u003cvar\u003e\\(3\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eBob moves to Vertex \u003cvar\u003e\\(2\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eAlice moves to Vertex \u003cvar\u003e\\(5\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eBob moves to Vertex \u003cvar\u003e\\(3\\)\u003c/var\u003e.\u003c/li\u003e\n \u003cli\u003eAlice moves to Vertex \u003cvar\u003e\\(3\\)\u003c/var\u003e.\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eHere, Bob 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"}}]}