trash

a.cpp

#line 1 "Main.cpp"

#line 2 "nachia\\misc\\sorting.hpp"

#include <vector>
#include <cassert>
#include <algorithm>

namespace nachia{

template<class Iterator>
void EnsurePermutation(Iterator first, Iterator last){
    int n = std::distance(first, last);
    std::vector<int> vis(n, 0);
    for(Iterator i=first; i!=last; i++){
        assert(0 <= *i);
        assert(*i < n);
        assert(vis[*i] == 0);
        vis[*i] = 1;
    }
}

template<class T> std::vector<T> Permute(
    const std::vector<T>& src,
    const std::vector<int>& perm
){
    const bool DEBUG = true;
    int n = src.size();
    if constexpr (DEBUG){
        assert(perm.size() == src.size());
        EnsurePermutation(perm.begin(), perm.end());
    }
    std::vector<T> res;
    res.reserve(n);
    for(int i=0; i<n; i++) res.push_back(src[perm[i]]);
    return res;
}

template<class T> std::vector<T>& PermuteInPlace(
    std::vector<T>& src,
    std::vector<int> perm
){
    const bool DEBUG = true;
    int n = src.size();
    if constexpr (DEBUG){
        assert(perm.size() == src.size());
        EnsurePermutation(perm.begin(), perm.end());
    }
    for(int s=0; s<n; s++){
        int p = s;
        while(perm[p] != s){
            std::swap(src[p], src[perm[p]]);
            std::swap(p, perm[p]);
        }
        perm[p] = p;
    }
    return src;
}

// stable sort
std::vector<int> BucketSortPermutation(
    std::vector<int>::const_iterator first,
    std::vector<int>::const_iterator last,
    int maxVal
){
    const bool DEBUG = true;
    int n = last - first;
    if constexpr (DEBUG){
        for(auto itr = first; itr != last; itr++){
            assert(0 <= *itr);
            assert(*itr <= maxVal);
        }
    }
    std::vector<int> cnt(maxVal+2);
    std::vector<int> res(n);
    for(int i=0; i<n; i++) cnt[first[i]+1]++;
    for(int i=0; i<maxVal; i++) cnt[i+1] += cnt[i];
    for(int i=0; i<n; i++) res[cnt[first[i]]++] = i;
    return res;
}

// stable sort
template<class T, class Mapping>
std::vector<int> BucketSortPermutation(
    typename std::vector<T>::const_iterator first,
    typename std::vector<T>::const_iterator last,
    const Mapping& f,
    int maxVal
){
    std::vector<int> buf(last - first);
    auto bufitr = buf.begin();
    for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr);
    return BucketSortPermutation(buf.begin(), buf.end(), maxVal);
}

// stable sort
template<class T, class Mapping>
std::vector<T> BucketSort(
    std::vector<T> src,
    const Mapping& f,
    int maxVal
){
    return PermuteInPlace(src, BucketSortPermutation<T>(src.begin(), src.end(), f, maxVal));
}

}
#line 2 "nachia\\graph\\double-low.hpp"

#line 2 "nachia\\array\\csr-array.hpp"
#include <utility>
#line 5 "nachia\\array\\csr-array.hpp"

namespace nachia{

template<class Elem>
class CsrArray{
public:
    struct ListRange{
        using iterator = typename std::vector<Elem>::iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        Elem& operator[](int i) const { return begi[i]; }
    };
    struct ConstListRange{
        using iterator = typename std::vector<Elem>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const Elem& operator[](int i) const { return begi[i]; }
    };
private:
    int m_n;
    std::vector<Elem> m_list;
    std::vector<int> m_pos;
public:
    CsrArray() : m_n(0), m_list(), m_pos() {}
    static CsrArray Construct(int n, const std::vector<std::pair<int, Elem>>& items){
        CsrArray res;
        res.m_n = n;
        std::vector<int> buf(n+1, 0);
        for(auto& [u,v] : items){ ++buf[u]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.m_list.resize(buf[n]);
        for(int i=(int)items.size()-1; i>=0; i--){
            res.m_list[--buf[items[i].first]] = items[i].second;
        }
        res.m_pos = std::move(buf);
        return res;
    }
    static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
        CsrArray res;
        res.m_n = pos.size() - 1;
        res.m_list = std::move(list);
        res.m_pos = std::move(pos);
        return res;
    }
    ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    int size() const { return m_n; }
    int fullSize() const { return (int)m_list.size(); }
};

} // namespace nachia
#line 3 "nachia\\graph\\dfs-tree.hpp"

namespace nachia{

struct DfsTree{
    std::vector<int> dfsOrd;
    std::vector<int> parent;

    static DfsTree Construct(int n, const std::vector<std::pair<int, int>>& edges, bool OutOrd){
        DfsTree res;
        auto adj = CsrArray<int>::Construct(n, edges);
        res.dfsOrd.reserve(n);
        std::vector<int> eid(n, 0);
        std::vector<int> parent(n, -2);
        for(int s=0; s<n; s++) if(parent[s] == -2){
            int p = s;
            if(p >= n) p -= n;
            parent[p] = -1;
            while(0 <= p){
                if(eid[p] == (OutOrd ? (int)adj[p].size() : 0)) res.dfsOrd.push_back(p);
                if(eid[p] == (int)adj[p].size()){ p = parent[p]; continue; }
                int nx = adj[p][eid[p]++];
                if(parent[nx] != -2) continue;
                parent[nx] = p;
                p = nx;
            }
        }
        res.parent = std::move(parent);
        return res;
    }
};

} // namespace nachia
#line 5 "nachia\\graph\\double-low.hpp"

namespace nachia{

struct DoubleLowAndOrdering{
    std::vector<int> inOrder;
    std::vector<int> inIndex;
    std::vector<int> parent;
    std::vector<int> lowpt1;
    std::vector<int> lowpt2;
    std::vector<int> nd;
    std::vector<int> edgeOrd;
    CsrArray<int> adj;
    
    // input : simple undirected graph
    void calc(){
        int n = adj.size();
        {
            inOrder = {0};
            parent.assign(n, -1); parent[0] = -2;
            std::vector<int> EI(n, 0);
            int p = 0;
            while(p >= 0){
                if(EI[p] == adj[p].size()){ p = parent[p]; continue; }
                int q = adj[p][EI[p]++];
                if(parent[q] != -1) continue;
                parent[q] = p; p = q;
                inOrder.push_back(p);
            }
            inIndex.resize(n);
            for(int i=0; i<n; i++) inIndex[inOrder[i]] = i;
            lowpt1.resize(n);
            for(int i=0; i<n; i++) lowpt1[i] = inIndex[i];
            lowpt2.resize(n);
            for(int i=0; i<n; i++) lowpt2[i] = inIndex[i];
        }
        auto insertLow = [&](int p, int low){
            if(lowpt1[p] == low) return;
            if(lowpt1[p] > low) std::swap(lowpt1[p], low);
            if(lowpt2[p] == low) return;
            if(lowpt2[p] > low) std::swap(lowpt2[p], low);
        };
        nd.assign(n, 1);
        for(int vi=n-1; vi>=0; vi--){
            int v = inOrder[vi];
            for(auto& e : adj[v]) if(parent[v] != e && inIndex[e] < inIndex[v]){
                if(parent[e] != v) insertLow(v, inIndex[e]);
            }
            if(parent[v] < 0) continue;
            insertLow(parent[v], lowpt1[v]);
            insertLow(parent[v], lowpt2[v]);
            nd[parent[v]] += nd[v];
        }
    }

    // input : simple undirected graph
    DoubleLowAndOrdering(int n, std::vector<std::pair<int, int>> edges){
        {
            std::vector<std::pair<int, int>> xedges;
            for(auto& e : edges) xedges.push_back({ e.first, e.second });
            for(auto& e : edges) xedges.push_back({ e.second, e.first });
            adj = CsrArray<int>::Construct(n, std::move(xedges));
            calc();
        }
        for(auto& e : edges){
            int& v = e.first; int& w = e.second;
            if(parent[v] == w) std::swap(v, w);
            if(parent[w] != v) if(inIndex[v] < inIndex[w]) std::swap(v, w);
        }
        auto edgePriority = 
            [&](const std::pair<int, int>& tg) -> int {
                int v = tg.first, w = tg.second;
                if(v != parent[w]) return 3 * inIndex[w]+1;
                return 3 * lowpt1[w] + ((lowpt2[w] < inIndex[v]) ? 0 : 2);
            };
        edgeOrd = BucketSortPermutation<std::pair<int, int>>(edges.begin(), edges.end(), edgePriority, 3*n-1);
        PermuteInPlace(edges, edgeOrd);
        std::reverse(edges.begin(), edges.end());
        adj = CsrArray<int>::Construct(n, std::move(edges));
        calc();
    }
};

} // namespace nachia
#line 4 "Main.cpp"

#include <iostream>
#line 8 "Main.cpp"
#include <chrono>

struct SPQRTree{

struct Component;
struct Edge;

// {a,b} is a potential type-2 separation pair,
// and h is the highest numbered vertex in the component that would be split off
struct HABTriplet{
	int h, a, b;
	bool isEOS() const { return h == -1; }
	static HABTriplet getEOS() { return {-1,-1,-1}; }
};

struct SPQRNode{};
struct Edge{
	int from;
	int to;
	bool start;
	bool isTreeEdge;
	bool isVirtual;
	bool inGc;
	int component1;
	int component2;
};
struct Vertex{
	int parent;
	int treeArc;
	int degree;
	int lowpt1;
	int lowpt2;
	int nd;
	int unvisitedTreeArcCount = 0;
};
enum class ComponentType{ Unknown, S, P, R };
static std::string ComponentTypeString(ComponentType t){
	switch(t){
		case ComponentType::Unknown: return "Unknown";
		case ComponentType::S: return "S";
		case ComponentType::P: return "P";
		case ComponentType::R: return "R";
	}
	return "Undefined";
}
struct Component{
	std::vector<int> edges;
	ComponentType ty = ComponentType::Unknown;
};

std::vector<Vertex> vtx;
std::vector<Edge> edges;
std::vector<int> AdjNx;
std::vector<int> AdjHead;
std::vector<int> FrondNx, FrondHead, FrondTail;
std::vector<int> Estack;
std::vector<HABTriplet> Tstack;
int Eitr, Titr;
std::vector<Component> components;

void RemoveEdgeFromGc(int ei){
	auto& e = edges[ei];
	vtx[e.from].degree--;
	vtx[e.to].degree--;
	if(e.from > e.to) std::swap(e.from, e.to);
	e.inGc = false;
}

void AddEdgeToComponent(int c, int ei){
	components[c].edges.push_back(ei);
	edges[ei].component1 = c;
	RemoveEdgeFromGc(ei);
}

int NewComponent(std::vector<int> E){
	auto c = components.size();
	components.push_back(Component{});
	for(auto ei : E){
		RemoveEdgeFromGc(ei);
		edges[ei].component1 = c;
	}
	components[c].edges = std::move(E);
	return c;
}

void PushFrond(int v, int e){
	if(FrondTail[v] >= 0) FrondNx[FrondTail[v]] = e;
	FrondTail[v] = e;
	if(FrondHead[v] < 0) FrondHead[v] = e;
}

bool IsAnEdgeOf(int ei, int v, int w){
	auto& e = edges[ei];
	if(e.from == v && e.to == w) return true;
	if(e.from == w && e.to == v) return true;
	return false;
}

void InsertAdj(int ei, int v){ AdjNx[ei] = AdjHead[v]; AdjHead[v] = ei; }

int NewComponent2(std::vector<int> E, int v, int w, bool treeEdge){
	auto c = components.size();
	components.push_back(Component{});
	int ei = E.back() = edges.size();
	for(auto ei : E) if(ei != E.back()){
		RemoveEdgeFromGc(ei);
		edges[ei].component1 = c;
	}
	components[c].edges = std::move(E);
	AdjNx.push_back(-1);
	edges.emplace_back();
	auto& e = edges[ei];
	e.from = v;
	e.to = w;
	e.isTreeEdge = treeEdge;
	e.isVirtual = true;
	e.start = false;
	e.inGc = true;
	e.component1 = -1;
	e.component2 = c;
	vtx[v].degree++;
	vtx[w].degree++;
	if(treeEdge){
		vtx[w].treeArc = ei;
		vtx[w].parent = v;
		InsertAdj(ei, v);
	}
	else PushFrond(w, ei);
	return ei;
}

int FirstChild(int w){
	int& adj = AdjHead[w];
	while(adj >= 0 && !edges[adj].inGc) adj = AdjNx[adj];
	return (adj < 0) ? -1 : edges[adj].to;
}

int Parent(int x){ return vtx[x].parent; }
int Deg(int x){ return vtx[x].degree; }
bool DoStartAPath(int ei){ return edges[ei].start; }
int High(int x){
	for(int& e=FrondHead[x]; e>=0; e=FrondNx[e]) if(edges[e].inGc && !edges[e].isTreeEdge) return edges[e].from;
	return -1;
}
bool IsAdjacentToANotYetVisitedTreeArc(int x){ return vtx[x].unvisitedTreeArcCount != 0; }
int Root(){ return 0; }

std::vector<int> adjBuf;

void PathSearch(int v){
	auto t0 = std::chrono::high_resolution_clock::now();
	bool ret = false;
	while(v >= 0){
		int ei = adjBuf[v];
		int w = edges[ei].to;
		if(ret){
			Estack[++Eitr] = vtx[w].treeArc;
			vtx[v].unvisitedTreeArcCount--;
			// BEGIN : check for type-2 pairs
			while(true){
				int tmpa = Tstack[Titr].a;
				// deg(w) == 2 のケースは Tstack.back() == EOF でも適用される
				if(v != Root() && (tmpa == v || (Deg(w) == 2 && FirstChild(w) > w))); else break;
				int h = Tstack[Titr].h, a = Tstack[Titr].a, b = Tstack[Titr].b;
				if(a == v && Parent(b) == a){ Titr--; continue; }
                int x = FirstChild(w);
                int eab = -1;
                int ep = -1;
                if(Deg(w) == 2 && x > w){
                    // v -> w -> x : triangle を作れる
                    ep = NewComponent2({ Estack[Eitr], Estack[Eitr-1], -1 }, v, x, true);
                    Eitr -= 2;
                    if(IsAnEdgeOf(Estack[Eitr], v, x)) eab = Estack[Eitr--];
                }
                else{
                    Titr--;
                    int EitrR = Eitr;
                    while(Eitr >= 0){
                        int x = edges[Estack[Eitr]].from, y = edges[Estack[Eitr]].to;
                        if(a <= x && x <= h && a <= y && y <= h); else break;
                        if(IsAnEdgeOf(Estack[Eitr], a, b)){ eab = Estack[Eitr]; Estack[Eitr] = Estack[EitrR--]; }
                        Eitr--;
                    }
                    ep = NewComponent2(std::vector<int>(Estack.begin()+(Eitr+1), Estack.begin()+(EitrR+2)), a, b, true);
                    x = b;
                }
                if(eab != -1) ep = NewComponent2({ eab, ep, -1 }, v, b, true);
                Estack[++Eitr] = ep;
                w = x;
			}
			// END : check for type-2 pairs
			// BEGIN : check for a type-1 pair
			if(vtx[w].lowpt2 >= v && vtx[w].lowpt1 < v && (Parent(v) != Root() || IsAdjacentToANotYetVisitedTreeArc(v))){
				int EitrR = Eitr;
				while(Eitr >= 0){
					int x = edges[Estack[Eitr]].from, y = edges[Estack[Eitr]].to;
					if(!((w <= x && x < w+vtx[w].nd) || (w <= y && y < w+vtx[w].nd))) break;
					Eitr--;
				}
				auto ep = NewComponent2(std::vector<int>(Estack.begin()+(Eitr+1), Estack.begin()+(EitrR+2)), v, vtx[w].lowpt1, false);
				if(Eitr >= 0 && IsAnEdgeOf(Estack[Eitr], v, vtx[w].lowpt1)){
					ep = NewComponent2({ Estack[Eitr--], ep, -1 }, v, vtx[w].lowpt1, false);
				}
				if(vtx[w].lowpt1 != Parent(v)) Estack[++Eitr] = ep;
				else ep = NewComponent2({ ep, vtx[v].treeArc, -1 }, vtx[w].lowpt1, v, true);
			}
			// END : check for a type-1 pair
			if(DoStartAPath(ei)) while(!(Tstack[Titr--].isEOS()));
			int High_v = High(v);
			while(!(Tstack[Titr].isEOS())){
				auto hab = Tstack[Titr];
				if(hab.a != v && hab.b != v && High_v > hab.h) Titr--; else break;
			}
		}
		else{
			if(edges[ei].isTreeEdge){
				if(DoStartAPath(ei)){
					int h = w + vtx[w].nd - 1, a = vtx[w].lowpt1, b = v;
					while(!Tstack[Titr].isEOS() && Tstack[Titr].a > vtx[w].lowpt1){
						h = std::max(h, Tstack[Titr].h);
						b = Tstack[Titr].b;
						Titr--;
					}
					Tstack[++Titr] = HABTriplet{ h, a, b };
					Tstack[++Titr] = HABTriplet::getEOS();
				}
				v = w; ret = false; continue;
			}
			else{
				PushFrond(w, ei); // visit a frond
				if(DoStartAPath(ei)){
					int h = -1, b = v;
					while(!Tstack[Titr].isEOS() && Tstack[Titr].a > w){
						h = std::max(h, Tstack[Titr].h);
						b = Tstack[Titr].b;
						Titr--;
					}
					Tstack[++Titr] = HABTriplet{ (h<0 ? v : h), w, b };
				}
				if(w == Parent(v)) NewComponent2({ ei, vtx[v].treeArc, -1 }, w, v, true);
				else Estack[++Eitr] = ei;
			}
		}
		adjBuf[v] = AdjNx[adjBuf[v]]; ret = false;
		if(adjBuf[v] < 0){ v = Parent(v); ret = true; }
	}
	auto t1 = std::chrono::high_resolution_clock::now();
	std::cerr << "time PathSearch = " << (t1-t0).count() << " ns\n";
}


void InitializeSimple(int N, std::vector<int> eitrs){
	auto t0 = std::chrono::high_resolution_clock::now();
	adjBuf.resize(N);
	std::vector<int> edgeOrd, inOrder;
	{
		std::vector<std::pair<int, int>> tgedges;
		for(auto a : eitrs){
			tgedges.push_back({ edges[a].from, edges[a].to });
			edges[a].inGc = true;
		}
		nachia::DoubleLowAndOrdering doubleLow(N, std::move(tgedges));
		vtx.resize(N);
		for(int i=0; i<N; i++){
			int newid = doubleLow.inIndex[i];
			vtx[newid].lowpt1 = doubleLow.lowpt1[i];
			vtx[newid].lowpt2 = doubleLow.lowpt2[i];
			vtx[newid].parent = (doubleLow.parent[i] < 0) ? -1 : doubleLow.inIndex[doubleLow.parent[i]];
			vtx[newid].degree = 0;
			vtx[newid].nd = doubleLow.nd[i];
		}
		edgeOrd = std::move(doubleLow.edgeOrd);
		inOrder = std::move(doubleLow.inOrder);

		for(auto& e : edges){
			e.from = doubleLow.inIndex[e.from];
			e.to = doubleLow.inIndex[e.to];
		}
	}

	AdjHead.assign(N, -1);
	AdjNx.assign(edges.size(), -1);
	FrondNx.assign(edges.size()*2, -1);
	FrondHead.assign(N, -1);
	FrondTail.assign(N, -1);

	std::reverse(edgeOrd.begin(), edgeOrd.end());
	for(int i : edgeOrd){
		int ei = eitrs[i];
		auto& e = edges[ei];
		int& v = e.from;
		int& w = e.to;
		vtx[v].degree++; vtx[w].degree++;
		if(vtx[w].parent == v || vtx[v].parent == w) /* v --> w */ {
			if(vtx[v].parent == w) std::swap(v, w);
			e.isTreeEdge = true;
			e.start = true;
			InsertAdj(ei, v);
			vtx[w].treeArc = ei;
			vtx[v].unvisitedTreeArcCount++;
		}
		else /* v ~~> w */ {
			if(v < w) std::swap(v, w);
			e.isTreeEdge = false;
			e.start = true;
			InsertAdj(ei, v);
		}
	}
	for(int v=1; v<N; v++) edges[AdjHead[v]].start = false;

	adjBuf = AdjHead;
	Titr =  0; Tstack.assign(eitrs.size()*2, HABTriplet::getEOS());
	Eitr = -1; Estack.resize(eitrs.size()+1);
	PathSearch(0);

	if(Eitr) NewComponent(std::vector<int>(Estack.begin(), Estack.begin() + Eitr+1));

	for(auto& e : edges){
		e.from = inOrder[e.from];
		e.to = inOrder[e.to];
	}
	auto t1 = std::chrono::high_resolution_clock::now();
	std::cerr << "time InitializeSimple = " << (t1-t0).count() << " ns\n";
}

void FixEdges(){
	std::vector<int> Map(edges.size(), -1);
	int n = 0;
	for(size_t i=0; i<edges.size(); i++) if(edges[i].from != -1){
		Map[i] = n++;
		std::swap(edges[Map[i]], edges[i]);
	}
	for(auto& c : components) for(auto& e : c.edges) e = Map[e];
	edges.resize(n);
}

void FixComponents(){
	std::vector<int> Map(components.size(), -1);
	int n = 0;
	for(size_t i=0; i<components.size(); i++) if(components[i].ty != ComponentType::Unknown){
		Map[i] = n++;
		std::swap(components[Map[i]], components[i]);
	}
	for(auto& e : edges){
		e.component1 = Map[e.component1];
		e.component2 = Map[e.component2];
	}
	components.resize(n);
}

void Initialize(int N, std::vector<std::pair<int, int>> edges){
	auto t0 = std::chrono::high_resolution_clock::now();
	int initEdgeNum = edges.size();
	std::vector<int> st;
	{
		std::vector<int> I(initEdgeNum); // edge sort index
		for(auto& e : edges) e = std::minmax((int)e.first, (int)e.second);
		for(int i=0; i<(int)edges.size(); i++) I[i] = i;
		I = nachia::BucketSort(I, [&](int i){ return edges[i].second; }, N-1);
		I = nachia::BucketSort(I, [&](int i){ return edges[i].first; }, N-1);
		auto NewEmptyEdge = [&](std::pair<int, int> vw, bool isVirtual) -> int {
			Edge e;
			e.from = vw.first;
			e.to = vw.second;
			e.isVirtual = isVirtual;
			e.component1 = e.component2 = -1;
			this->edges.push_back(e);
			return this->edges.size() - 1;
		};
		auto NewPNode = [&](int a, int b) -> int {
			int c = components.size();
			components.push_back(Component());
			int ep = NewEmptyEdge({ this->edges[a].from, this->edges[a].to }, true);
			this->edges[a].component1 = c;
			this->edges[b].component1 = c;
			this->edges[ep].component2 = c;
			components[c].edges = { a, b, ep };
			components[c].ty = ComponentType::P;
			return ep;
		};
		st.push_back(NewEmptyEdge(edges[I[0]], false));
		for(int i=1; i<(int)I.size(); i++){
			int e1 = NewEmptyEdge(edges[I[i]], false), e2 = st.back();
			if(!st.empty() && this->edges[e1].from == this->edges[e2].from && this->edges[e1].to == this->edges[e2].to){
				st.back() = NewPNode(e1, e2);
			}
			else{
				st.push_back(e1);
			}
		}
	}

	InitializeSimple(N, st);

	for(auto& c : components) if(c.ty == ComponentType::Unknown){
		if(c.edges.size() != 3) c.ty = ComponentType::R;
		else{
			auto e1 = c.edges.begin();
			auto e2 = c.edges.begin(); e2++;
			if(IsAnEdgeOf(*e1, this->edges[*e2].from, this->edges[*e2].to)) c.ty = ComponentType::P;
			else c.ty = ComponentType::S;
		}
	}

	for(int ci=0; ci<(int)components.size(); ci++){
		auto& c = components[ci];
		if(c.ty != ComponentType::P && c.ty != ComponentType::S) continue;
		for(size_t i=0; i<c.edges.size(); i++){
			auto ei = c.edges[i];
			auto& e = this->edges[ei];
			if(!(e.isVirtual)) continue;
			auto ci2 = (e.component1 == ci) ? e.component2 : e.component1;
			auto& c2 = components[ci2];
			if(c2.ty != c.ty) continue;
			for(int e2i : c2.edges){
				if(e2i == ei) continue;
				c.edges.push_back(e2i);
				if(this->edges[e2i].component1 == ci2) this->edges[e2i].component1 = ci; else this->edges[e2i].component2 = ci;
			}
			c2.edges.clear();
            e.from = -1;
			std::swap(c.edges.back(), c.edges[i]); c.edges.pop_back(); i--;
			c2.ty = ComponentType::Unknown;
		}
	}

    FixEdges();
	FixComponents();
	auto t1 = std::chrono::high_resolution_clock::now();
	std::cerr << "time Initialize = " << (t1-t0).count() << " ns\n";
}

};

#line 2 "nachia\\misc\\fastio.hpp"

#include <cstdio>
#include <string>

namespace nachia{


const unsigned int INPUT_BUF_SIZE = 1 << 17;
const unsigned int OUTPUT_BUF_SIZE = 1 << 17;

char input_buf[INPUT_BUF_SIZE];

struct InputBufIterator{
private:
    unsigned int p = INPUT_BUF_SIZE;
public:
    using MyType = InputBufIterator;
    static bool is_whitespace(char ch){
        switch(ch){
            case ' ': case '\n': case '\r': case '\t': return true;
        }
        return false;
    }
    char seek_char(){
        if(p == INPUT_BUF_SIZE){
            size_t len = fread(input_buf, 1, INPUT_BUF_SIZE, stdin);
            if(len != INPUT_BUF_SIZE) input_buf[len] = '\0';
            p = 0;
        }
        return input_buf[p];
    }
    void skip_whitespace(){
        while(is_whitespace(seek_char())) p++;
    }
    unsigned int next_uint(){
        skip_whitespace();
        unsigned int buf = 0;
        while(true){
            char tmp = seek_char();
            if('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }
    int next_int(){
        skip_whitespace();
        if(seek_char() == '-'){
            p++;
            return (int)(-next_uint());
        }
        return (int)next_uint();
    }
    unsigned long long next_ulong(){
        skip_whitespace();
        unsigned long long buf = 0;
        while(true){
            char tmp = seek_char();
            if('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }
    long long next_long(){
        skip_whitespace();
        if(seek_char() == '-'){
            p++;
            return (long long)(-next_ulong());
        }
        return (long long)next_ulong();
    }
    char next_char(){
        skip_whitespace();
        char buf = seek_char();
        p++;
        return buf;
    }
    std::string next_token(){
        skip_whitespace();
        std::string buf;
        while(true){
            char ch = seek_char();
            if(is_whitespace(ch) || ch == '\0') break;
            buf.push_back(ch);
            p++;
        }
        return buf;
    }
    MyType& operator>>(unsigned int& dest){ dest = next_uint(); return *this; }
    MyType& operator>>(int& dest){ dest = next_int(); return *this; }
    MyType& operator>>(unsigned long& dest){ dest = next_ulong(); return *this; }
    MyType& operator>>(long& dest){ dest = next_long(); return *this; }
    MyType& operator>>(unsigned long long& dest){ dest = next_ulong(); return *this; }
    MyType& operator>>(long long& dest){ dest = next_long(); return *this; }
    MyType& operator>>(std::string& dest){ dest = next_token(); return *this; }
    MyType& operator>>(char& dest){ dest = next_char(); return *this; }
};


char output_buf[OUTPUT_BUF_SIZE] = {};

struct FastOutputTable{
    char dig3lz[1000][4];
    char dig3nlz[1000][4];
    FastOutputTable(){
        for(unsigned int d=0; d<1000; d++){
            unsigned int x = d;
            unsigned int i = 0;
            dig3lz[d][i++] = ('0' + x / 100 % 10);
            dig3lz[d][i++] = ('0' + x /  10 % 10);
            dig3lz[d][i++] = ('0' + x /   1 % 10);
            dig3lz[d][i++] = '\0';
        }
        for(unsigned int d=0; d<1000; d++){
            unsigned int x = d;
            unsigned int i = 0;
            if(x >= 100) dig3nlz[d][i++] = ('0' + x / 100 % 10);
            if(x >=  10) dig3nlz[d][i++] = ('0' + x /  10 % 10);
            if(x >=   1) dig3nlz[d][i++] = ('0' + x /   1 % 10);
            dig3nlz[d][i++] = '\0';
        }
    }
} fastoutput_table_inst;

struct OutputBufIterator{
    using MyType = OutputBufIterator;
    unsigned int p = 0;
    static constexpr unsigned int POW10(int d){ return (d<=0) ? 1 : (POW10(d-1)*10); }
    static constexpr unsigned long long POW10LL(int d){ return (d<=0) ? 1 : (POW10LL(d-1)*10); }
    void next_char(char c){
        output_buf[p++] = c;
        if(p == OUTPUT_BUF_SIZE){
            fwrite(output_buf, p, 1, stdout);
            p = 0;
        }
    }
    void next_eoln(){
        next_char('\n');
    }
    void next_cstr(const char* s){
        unsigned int i = 0;
        while(s[i]) next_char(s[i++]);
    }
    void next_dig9(unsigned int x){
        unsigned int y;
        y = x / POW10(6); x -= y * POW10(6);
        next_cstr(fastoutput_table_inst.dig3lz [y]);
        y = x / POW10(3); x -= y * POW10(3);
        next_cstr(fastoutput_table_inst.dig3lz [y]);
        y = x;
        next_cstr(fastoutput_table_inst.dig3lz [y]);
    }
    void next_uint(unsigned int x){
        unsigned int y = 0;
        if(x >= POW10(9)){
            y = x / POW10(9); x -= y * POW10(9);
            next_cstr(fastoutput_table_inst.dig3nlz[y]);
            next_dig9(x);
        }
        else if(x >= POW10(6)){
            y = x / POW10(6); x -= y * POW10(6);
            next_cstr(fastoutput_table_inst.dig3nlz[y]);
            y = x / POW10(3); x -= y * POW10(3);
            next_cstr(fastoutput_table_inst.dig3lz [y]);
            next_cstr(fastoutput_table_inst.dig3lz [x]);
        }
        else if(x >= POW10(3)){
            y = x / POW10(3); x -= y * POW10(3);
            next_cstr(fastoutput_table_inst.dig3nlz[y]);
            next_cstr(fastoutput_table_inst.dig3lz [x]);
        }
        else if(x >= 1){
            next_cstr(fastoutput_table_inst.dig3nlz[x]);
        }
        else{
            next_char('0');
        }
    }
    void next_int(int x){
        if(x >= 0) next_uint(x);
        else{
            next_char('-');
            next_uint((unsigned int)-x);
        }
    }
    void next_ulong(unsigned long long x){
        unsigned int y = 0;
        if(x >= POW10LL(18)){
            y = x / POW10LL(18); x -= y * POW10LL(18);
            next_uint(y);
            y = x / POW10LL(9); x -= y * POW10LL(9);
            next_dig9(y);
            next_dig9(x);
        }
        else if(x >= POW10LL(9)){
            y = x / POW10LL(9); x -= y * POW10LL(9);
            next_uint(y);
            next_dig9(x);
        }
        else{
            next_uint(x);
        }
    }
    void next_long(long long x){
        if(x >= 0) next_ulong(x);
        else{
            next_char('-');
            next_ulong((unsigned long long)-x);
        }
    }
    void write_to_file(bool flush = false){
        fwrite(output_buf, p, 1, stdout);
        if(flush) fflush(stdout);
        p = 0;
    }
    ~OutputBufIterator(){ write_to_file(); }
    MyType& operator<<(unsigned int tg){ next_uint(tg); return *this; }
    MyType& operator<<(unsigned long tg){ next_ulong(tg); return *this; }
    MyType& operator<<(unsigned long long tg){ next_ulong(tg); return *this; }
    MyType& operator<<(int tg){ next_int(tg); return *this; }
    MyType& operator<<(long tg){ next_long(tg); return *this; }
    MyType& operator<<(long long tg){ next_long(tg); return *this; }
    MyType& operator<<(const std::string& tg){ next_cstr(tg.c_str()); return *this; }
    MyType& operator<<(const char* tg){ next_cstr(tg); return *this; }
    MyType& operator<<(char tg){ next_char(tg); return *this; }
};

} // namespace nachia
#line 443 "Main.cpp"

int main() {
	nachia::InputBufIterator cin;
	nachia::OutputBufIterator cout;
	int N, M; cin >> N >> M;
	std::vector<std::pair<int,int>> edges(M);
	for(auto& e : edges){
		cin >> e.first >> e.second;
	}

	SPQRTree spqrTree;
	spqrTree.Initialize(N, edges);

	cout << (spqrTree.components.size()) << '\n';
	for(auto& c : spqrTree.components){
		cout << SPQRTree::ComponentTypeString(c.ty) << ' ' << c.edges.size();
		for(auto& e : c.edges){
			cout << ' ' << spqrTree.edges[e].from << ' ' << spqrTree.edges[e].to;
		}
		cout << '\n';
	}
    
    return 0;
}