#line 2 "graph/biconnected-components.hpp"
#line 2 "graph/lowlink.hpp"
#include <vector>
using namespace std;
#line 2 "graph/graph-template.hpp"
template <typename T>
struct edge {
int src, to;
T cost;
edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}
edge &operator=(const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;
// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
UnweightedGraph g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
if (is_1origin) x--, y--;
g[x].push_back(y);
if (!is_directed) g[y].push_back(x);
}
return g;
}
// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
WeightedGraph<T> g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
cin >> c;
if (is_1origin) x--, y--;
g[x].emplace_back(x, y, c);
if (!is_directed) g[y].emplace_back(y, x, c);
}
return g;
}
// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
Edges<T> es;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
es.emplace_back(x, y, c);
}
return es;
}
// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
bool is_directed = false, bool is_1origin = true) {
vector<vector<T>> d(N, vector<T>(N, INF));
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
d[x][y] = c;
if (!is_directed) d[y][x] = c;
}
return d;
}
/**
* @brief グラフテンプレート
* @docs docs/graph/graph-template.md
*/
#line 7 "graph/lowlink.hpp"
// bridge ... 橋 (辺 (u, v) が u < v となるように格納)
// articulation point ... 関節点
template <typename G>
struct LowLink {
const G &g;
int N;
vector<int> ord, low, articulation;
vector<pair<int, int> > bridge;
LowLink(const G &_g) : g(_g), N(g.size()), ord(N, -1), low(N, -1) {
for (int i = 0, k = 0; i < N; i++) {
if (ord[i] == -1) {
k = dfs(i, k, -1);
}
}
}
int dfs(int idx, int k, int par) {
low[idx] = (ord[idx] = k++);
int cnt = 0;
bool arti = false, second = false;
for (auto &to : g[idx]) {
if (ord[to] == -1) {
cnt++;
k = dfs(to, k, idx);
low[idx] = min(low[idx], low[to]);
arti |= (par != -1) && (low[to] >= ord[idx]);
if (ord[idx] < low[to]) {
bridge.emplace_back(minmax(idx, (int)to));
}
} else if (to != par || second) {
low[idx] = min(low[idx], ord[to]);
} else {
second = true;
}
}
arti |= par == -1 && cnt > 1;
if (arti) articulation.push_back(idx);
return k;
}
};
#line 4 "graph/biconnected-components.hpp"
template <typename G>
struct BiConnectedComponents : LowLink<G> {
using LL = LowLink<G>;
vector<int> used;
vector<vector<pair<int, int> > > bc;
vector<pair<int, int> > tmp;
BiConnectedComponents(const G &_g) : LL(_g) { build(); }
void build() {
used.assign(this->g.size(), 0);
for (int i = 0; i < (int)used.size(); i++) {
if (!used[i]) dfs(i, -1);
}
}
void dfs(int idx, int par) {
used[idx] = true;
for (auto &to : this->g[idx]) {
if (to == par) continue;
if (!used[to] || this->ord[to] < this->ord[idx]) {
tmp.emplace_back(minmax<int>(idx, to));
}
if (!used[to]) {
dfs(to, idx);
if (this->low[to] >= this->ord[idx]) {
bc.emplace_back();
while(true) {
auto e = tmp.back();
bc.back().emplace_back(e);
tmp.pop_back();
if (e.first == min<int>(idx, to) && e.second == max<int>(idx, to)) {
break;
}
}
}
}
}
}
};
/**
* @brief 二重頂点連結分解
*/
二重頂点連結分解