#include using namespace std; struct Edge{ int id, source, target; Edge(int id, int source, int target): id(id), source(source), target(target){} // 出力 friend ostream &operator<<(ostream &os, const Edge &e) { return os << "id: " << e.id << ", source: " << e.source << ", target: " << e.target; } }; struct Graph{ using E=Edge; vector> inc; vector edge; Graph(int N=0){ inc.resize(N); } // 頂点数 int order(){return inc.size();} // 辺の数 int size(){return edge.size();} // 頂点を1個追加する. int add_vertex(){ inc.emplace_back(vector()); return inc.size()-1; } // 頂点をk個追加する. vector add_vertices(int k){ vector I; for (; k--; k>=0){ I.emplace_back(add_vertex()); } return I; } // 無向辺 uv を加える. int add_edge(int u, int v){ int i=size(); inc[u].emplace_back(E(i,u,v)); inc[v].emplace_back(E(i,v,u)); edge.emplace_back(E(i,u,v)); return i; } // 無向辺 e を加える. int add_edge(const Edge &e){ return add_edge(e.source, e.target); } // walk を加える. vector add_walk(const vector &walk){ vector J; for (int i=0; i<(int)walk.size()-1; i++){ J.emplace_back(add_edge(walk[i], walk[i+1])); } return J; } Edge get_edge(int j){ return edge[j]; } // cycle を加える. vector add_cycle(const vector &cycle){ vector J=add_walk(cycle); J.emplace_back(add_edge(cycle.back(),cycle.front())); return J; } // 頂点 v を含む連結成分を出力する. vector connected_component(int v){ vector C; vector T(order(),false); T[v]=true; deque Q{v}; while (!Q.empty()){ int x=Q.front(); Q.pop_front(); C.emplace_back(x); for (E &e:inc[x]){ int t=e.target; if (!T[t]){ T[t]=true; Q.push_back(t); } } } return C; } // u,v は連結かどうかを求める. bool is_connected_vertex(int u, int v){ if (u==v) return true; vector T(order(), false); T[u]=true; deque Q{u}; while (!Q.empty()){ int x=Q.front(); Q.pop_front(); for (E &e:inc[x]){ int t=e.target; if (T[t]==false){ T[t]=true; Q.push_back(t); if (t==v) return true; } } } return false; } // 2 頂点 u,v 間の距離を求める. int distance(int u, int v){ if (u==v) return 0; vector T(order(),-1); T[u]=0; deque Q{u}; while (!Q.empty()){ int x=Q.front(); Q.pop_front(); for (E &e:inc[x]){ int t=e.target; if (T[t]==-1){ T[t]=T[x]+1; Q.push_back(t); if (t==v) return T[t]; } } } return -1; } // 頂点 u 間からの距離を求める. vector distance_all(int u){ vector T(order(),-1); T[u]=0; deque Q{u}; while (!Q.empty()){ int x=Q.front(); Q.pop_front(); for (E &e:inc[x]){ int t=e.target; if (T[t]==-1){ T[t]=T[x]+1; Q.push_back(t); } } } return T; } // u-v 間の最短路を求める (存在しない場合, []). vector shortest_path(int u, int v){ if (u==v) return vector{u}; vector T(order(),-1); deque Q{u}; while (!Q.empty()){ int x=Q.front(); Q.pop_front(); for (auto &e:inc[x]){ int y=e.target; if (T[y]==-1){ T[y]=x; Q.push_back(y); if (y==v){ vector P{v}; int a=v; while (a!=u){ a=T[a]; P.emplace_back(a); } reverse(P.begin(), P.end()); return P; } } } } return vector{}; } }; struct Connected_Component_Decomposition{ vector> component; vector id; public: Connected_Component_Decomposition(Graph &G){ calculate(G); } private: int k; void calculate(Graph &G){ int N=G.order(); component.clear(); id.assign(N,-1); k=0; for (int v=0; v()); dfs(G,v); k++; } } } void dfs(Graph &G, int v){ id[v]=k; component.back().emplace_back(v); for (auto &e: G.inc[v]){ if (id[e.target]==-1) dfs(G,e.target); } } public: inline int component_number() const {return component.size();} inline bool is_connected(const int &u, const int &v) const {return id[u]==id[v];} }; struct Lowlink{ vector used, bridge, articulation; vector ord, low; Lowlink(Graph &G){ int N=G.order(), M=G.size(); used.assign(N,false); ord.assign(N,0); low.assign(N,0); bridge.assign(M,false); articulation.assign(N,false); int k=0; for (int i=0; i=2) is_arti=true; if (is_arti) articulation[v]=true; return k; } }; int main(){ int N,M,Q; cin >> N >> M >> Q; Graph G(N+1); int u,v; for (int j=0; j