{"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Đối với đồ thị vô hướng có trọng số kết nối \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eG\u003c/i\u003e\u003c/span\u003e, MST (cây bao trùm nhỏ nhất) là một đồ thị con của \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eG\u003c/i\u003e\u003c/span\u003e chứa tất cả các đỉnh của \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eG\u003c/i\u003e\u003c/span\u003e, là một cây, và tổng trọng số của các cạnh là nhỏ nhất có thể.\u003c/p\u003e\u003cp\u003eBạn được cho một đồ thị \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eG\u003c/i\u003e\u003c/span\u003e. Nếu bạn chạy một thuật toán MST trên đồ thị, nó chỉ cho bạn một MST duy nhất và làm cho các cạnh khác trở nên ghen tị. Bạn được cho một số truy vấn, mỗi truy vấn chứa một tập hợp các cạnh của đồ thị \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eG\u003c/i\u003e\u003c/span\u003e, và bạn nên xác định xem có một MST chứa tất cả các cạnh này hay không.\u003c/p\u003e"}},{"title":"Nhập","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, \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, \u003ci\u003em\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1 ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e) — số đỉnh và số cạnh trong đồ thị và số truy vấn.\u003c/p\u003e\u003cp\u003eDòng thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e của \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e dòng tiếp theo chứa ba số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\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\u003ev\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\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ev\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\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — các đầu mút và trọng số của cạnh thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e. Có thể có nhiều hơn một cạnh giữa hai đỉnh. Đảm bảo rằng đồ thị đã cho là kết nối.\u003c/p\u003e\u003cp\u003eDòng tiếp theo chứa một số nguyên duy nhất \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — số truy vấn.\u003c/p\u003e\u003cp\u003eCác dòng tiếp theo, dòng thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e chứa truy vấn thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e. Nó bắt đầu bằng một số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\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\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e) — kích thước của tập hợp cạnh và tiếp tục với \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e số nguyên cách nhau bằng dấu cách từ \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e — các chỉ số của các cạnh. Đảm bảo rằng tổng của \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e cho \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003eq\u003c/i\u003e\u003c/span\u003e không vượt quá \u003cspan class\u003d\"tex-span\"\u003e5·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eĐối với mỗi truy vấn, bạn nên in ra \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e\" (không có dấu ngoặc kép) nếu có một MST chứa các cạnh này và \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e\" (tất nhiên là không có dấu ngoặc kép) nếu ngược lại.\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\u003e5 7\n1 2 2\n1 3 2\n2 3 1\n2 4 1\n3 4 1\n3 5 2\n4 5 2\n4\n2 3 4\n3 3 4 5\n2 1 7\n2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\nNO\nYES\nNO\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\u003eĐây là đồ thị của ví dụ:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"302px\" src\u003d\"CDN_BASE_URL/1fa184ce6ecd15e12438851b99c933eb?v\u003d1701731713\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"378px\"\u003e \u003c/center\u003e\u003cp\u003eTrọng số của cây bao trùm nhỏ nhất trên đồ thị này là \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eMST với các cạnh \u003cspan class\u003d\"tex-span\"\u003e(1, 3, 4, 6)\u003c/span\u003e, chứa tất cả các cạnh từ truy vấn thứ nhất, vì vậy câu trả lời cho truy vấn đầu tiên là \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eCác cạnh từ truy vấn thứ hai tạo thành một chu trình có độ dài \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, vì vậy không có cây bao trùm nào bao gồm ba cạnh này. Do đó, câu trả lời là \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e\".\u003c/p\u003e"}}]}