{"trustable":false,"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":"\u003cp\u003eCho một đồ thị vô hướng, trọng số liên thông mà không có vòng và cạnh lặp. \u003c/p\u003e\u003cp\u003eHãy nhớ rằng một \u003cspan class\u003d\"tex-font-style-underline\"\u003ecây bao trùm\u003c/span\u003e của một đồ thị được xác định là một đồ thị con không có chu trình, liên thông của đồ thị đã cho mà bao gồm tất cả các đỉnh của đồ thị. Trọng số của một cây được xác định là tổng trọng số của các cạnh mà cây đã chứa. \u003cspan class\u003d\"tex-font-style-underline\"\u003eCây bao trùm nhỏ nhất\u003c/span\u003e (\u003cspan class\u003d\"tex-font-style-bf\"\u003eMST\u003c/span\u003e) của một đồ thị được xác định là cây bao trùm của đồ thị có trọng số nhỏ nhất có thể. Đối với bất kỳ đồ thị nào liên thông thì cây bao trùm nhỏ nhất tồn tại, nhưng trong trường hợp tổng quát, cây bao trùm nhỏ nhất của một đồ thị không phải là duy nhất.\u003c/p\u003e\n\n\u003cp\u003eĐối với mỗi cạnh của đồ thị đã cho, bạn cần xác định: liệu nó có được bao gồm trong một MST \u003cspan class\u003d\"tex-font-style-bf\"\u003ebất kỳ\u003c/span\u003e nào không, hoặc được bao gồm \u003cspan class\u003d\"tex-font-style-bf\"\u003etrong ít nhất một MST\u003c/span\u003e, hoặc \u003cspan class\u003d\"tex-font-style-bf\"\u003ekhông được bao gồm trong bất kỳ\u003c/span\u003e MST nào.\u003c/p\u003e"}},{"title":"Dữ liệu","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/97a78af0554f2de95e24a7be1c5885b5?v\u003d1708939779\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e) — số đỉnh và cạnh của đồ thị, tương ứng. Tiếp theo là \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e dòng, mỗi dòng chứa ba số nguyên — mô tả các cạnh của đồ thị dưới dạng \"\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\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\u003ci\u003eb\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\u003ci\u003ew\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\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e, 1 ≤ \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e), trong đó \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e là số của các đỉnh kết nối bởi cạnh thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e là trọng số của cạnh. Đảm bảo rằng đồ thị là liên thông và không chứa vòng hoặc cạnh lặp.\u003c/p\u003e"}},{"title":"Kết quả","value":{"format":"HTML","content":"\u003cp\u003eIn ra \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e dòng — câu trả lời cho tất cả các cạnh. Nếu cạnh thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e được bao gồm trong bất kỳ MST nào, in \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eany\u003c/span\u003e\"; nếu cạnh thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e được bao gồm ít nhất trong một MST, in \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eat least one\u003c/span\u003e\"; nếu cạnh thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e không được bao gồm trong bất kỳ MST nào, in \"\u003cspan class\u003d\"tex-font-style-tt\"\u003enone\u003c/span\u003e\". In các câu trả lời cho các cạnh theo thứ tự mà các cạnh được chỉ định trong đầu vào.\u003c/p\u003e"}},{"title":"Ví dụ 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\u003e4 5\n1 2 101\n1 3 100\n2 3 2\n2 4 2\n3 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003enone\nany\nat least one\nat least one\nany\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 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\u003e3 3\n1 2 1\n2 3 1\n1 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eany\nany\nnone\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 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\u003e3 3\n1 2 1\n2 3 1\n1 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eat least one\nat least one\nat least one\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ thứ hai, MST là duy nhất cho đồ thị đã cho: nó chứa hai cạnh đầu tiên.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ ba, bất kỳ hai cạnh nào cũng tạo thành MST cho đồ thị đã cho. Điều đó có nghĩa là mỗi cạnh được bao gồm ít nhất trong một MST.\u003c/p\u003e"}}]}