| 89 | S.push_back(u); |
| 90 | } |
| 91 | void pop() { |
| 92 | assert(!S.empty()); |
| 93 | vector<update> t[2]; |
| 94 | advance_bottom(); |
| 95 | if (bottom == S.size()) { |
| 96 | while (!S.empty()) { |
| 97 | t[0].push_back(S.back()); |
| 98 | S.pop_back(); |
| 99 | D.undo(); |
| 100 | } |
| 101 | for (auto &u : t[0]) { |
| 102 | u.type = 1; |
| 103 | push(u); |
| 104 | } |
| 105 | t[0].clear(); |
| 106 | bottom = 0; |
| 107 | } |
| 108 | do { |
| 109 | t[S.back().type].push_back(S.back()); |
| 110 | S.pop_back(); |
| 111 | D.undo(); |
| 112 | } while (t[1].size() < t[0].size() && S.size() > bottom); |
| 113 | for (int i : {0, 1}) { |
| 114 | reverse(t[i].begin(), t[i].end()); |
| 115 | for (auto &u : t[i]) push(u); |
| 116 | } |
| 117 | S.pop_back(); |
| 118 | D.undo(); |
| 119 | } |
| 120 | bool is_bipartite() { |
| 121 | return D.is_bipartite(); |
| 122 | } |