{"trustable":true,"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":"Bài toán","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eCó \u003cvar\u003e\\(N\\)\u003c/var\u003e hòn đảo và \u003cvar\u003e\\(M\\)\u003c/var\u003e cầu.\u003c/p\u003e\n\u003cp\u003eCầu thứ \u003cvar\u003e\\(i\\)\u003c/var\u003e nối giữa hòn đảo thứ \u003cvar\u003e\\(A_i\\)\u003c/var\u003e và hòn đảo thứ \u003cvar\u003e\\(B_i\\)\u003c/var\u003e theo cả hai chiều.\u003c/p\u003e\n\u003cp\u003eBan đầu, chúng ta có thể di chuyển giữa hai hòn đảo bất kỳ bằng một số cầu này.\u003c/p\u003e\n\u003cp\u003eTuy nhiên, kết quả của một cuộc khảo sát cho thấy rằng tất cả các cầu này sẽ đổ vì lão hóa, theo thứ tự từ cầu đầu tiên đến cầu thứ \u003cvar\u003e\\(M\\)\u003c/var\u003e.\u003c/p\u003e\n\u003cp\u003eĐặt \u003cstrong\u003esự bất tiện\u003c/strong\u003e là số cặp hòn đảo \u003cvar\u003e\\((a, b)\\)\u003c/var\u003e (\u003cvar\u003e\\(a \u0026lt; b\\)\u003c/var\u003e) mà chúng ta không còn có thể di chuyển giữa hòn đảo thứ \u003cvar\u003e\\(a\\)\u003c/var\u003e và hòn đảo thứ \u003cvar\u003e\\(b\\)\u003c/var\u003e bằng một số cầu còn lại.\u003c/p\u003e\n\u003cp\u003eĐối với mỗi \u003cvar\u003e\\(i\\)\u003c/var\u003e \u003cvar\u003e\\((1 \\leq i \\leq M)\\)\u003c/var\u003e, tìm sự bất tiện ngay sau khi cầu thứ \u003cvar\u003e\\(i\\)\u003c/var\u003e đổ.\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"Giới hạn","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cul\u003e\n\u003cli\u003eTất cả các giá trị trong input đều là số nguyên.\u003c/li\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 M \\leq 10^5\\)\u003c/var\u003e\u003c/li\u003e\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq A_i \u0026lt; B_i \\leq N\\)\u003c/var\u003e\u003c/li\u003e\n\u003cli\u003eTất cả các cặp \u003cvar\u003e\\((A_i, B_i)\\)\u003c/var\u003e đều là khác nhau.\u003c/li\u003e\n\u003cli\u003eSự bất tiện ban đầu là \u003cvar\u003e\\(0\\)\u003c/var\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eInput được đưa ra từ Standard Input theo định dạng sau:\u003c/p\u003e\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(M\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_1\\)\u003c/var\u003e \u003cvar\u003e\\(B_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_2\\)\u003c/var\u003e \u003cvar\u003e\\(B_2\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(\\vdots\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_M\\)\u003c/var\u003e \u003cvar\u003e\\(B_M\\)\u003c/var\u003e\r\n\u003c/pre\u003e\n\n\u003c/section\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003csection\u003e\n\u003cp\u003eTheo thứ tự \u003cvar\u003e\\(i \u003d 1, 2, ..., M\\)\u003c/var\u003e, in ra sự bất tiện ngay sau khi cầu thứ \u003cvar\u003e\\(i\\)\u003c/var\u003e đổ.\nLưu ý rằng kết quả có thể không vừa với kiểu số nguyên \u003cvar\u003e\\(32\\)\u003c/var\u003e-bit.\u003c/p\u003e\n\u003c/section\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\r\n1 2\r\n3 4\r\n1 3\r\n2 3\r\n1 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n0\r\n4\r\n5\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\u003cp\u003eVí dụ, khi cầu từ thứ nhất đến thứ ba đổ, sự bất tiện là \u003cvar\u003e\\(4\\)\u003c/var\u003e vì chúng ta không còn có thể di chuyển giữa các cặp \u003cvar\u003e\\((1, 2), (1, 3), (2, 4)\\)\u003c/var\u003e và \u003cvar\u003e\\((3, 4)\\)\u003c/var\u003e.\u003c/p\u003e\n\u003c/section\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\u003e6 5\r\n2 3\r\n1 2\r\n5 6\r\n3 4\r\n4 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n9\r\n12\r\n14\r\n15\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\u003c/section\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\u003e2 1\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\u003c/section\u003e"}}]}