O(m * log(n)) solution
Intuition\nImagine during Kruskal\'s algorithm we have processed some prefix of sorted by weight edges and following several edges (some group of edges G) are a
# Intuition\nImagine during Kruskal\'s algorithm we have processed some prefix of sorted by weight edges and following several edges (some group of edges `G`) are all edges of the graph with weight `w`. We will process such groups with equal weight together in described algorithm.\nAlso by DSU I mean Disjoint Set Union structure used in Kruskal\'s algorithm.\n##### Lemma 1:\nIf an edge from `G` has endpoints in different sets of current state of DSU (different connected components) then it\'s either *critical* or *pseudo-critical*.\n##### Lemma 2:\nConsider one more graph with nodes representing current different sets of DSU and edges from `G`. If an edge from `G` is a bridge in this graph, it is *critical*, otherwise (it is in some cycle) it\'s *pseudo-critical*.\n\n# Approach\nSo to decide whether the edge is *critical* or *pseudo-critical* we need to find all bridges in some graph with O(`|G|`) edges.\nOne way to do it is [special DFS](https://cp-algorithms.com/graph/bridge-searching.html).\nAnother way is [keeping special DSU for 2-edge-connected components](https://cp-algorithms.com/graph/bridge-searching-online.html). This way seems to be more appropriate as it automatically performs part of Kruskal\'s algorithm (DSU for connected components).\n\n# Complexity\n- Time complexity:\nO(m * log(n))\n\n- Space complexity:\nO(m)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        for (int i = 0; i < edges.size(); ++i) {\n            edges[i].push_back(i);\n        }\n        sort(edges.begin(), edges.end(), [] (const auto& x, const auto& y) {\n            return x[2] < y[2];\n        });\n        \n        init(n);\n        vector<vector<int>> ans(2);\n        \n        for (int i = 0; i < edges.size(); ) {\n            vector<int> good;\n            for (int start = i; i < edges.size() && edges[start][2] == edges[i][2]; ++i) {\n                if (find_cc(edges[i][0]) != find_cc(edges[i][1])) {\n                    good.push_back(i);\n                }\n            }\n            for (int i : good) {\n                add_edge(edges[i][0], edges[i][1]);\n            }\n            for (int i : good) {\n                ans[find_2ecc(edges[i][0]) == find_2ecc(edges[i][1])].push_back(edges[i][3]);\n            }\n        }\n        return ans;\n    }\n    \n\n    // taken from https://cp-algorithms.com/graph/bridge-searching-online.html:\n\n    vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;\n    int bridges;\n    int lca_iteration;\n    vector<int> last_visit;\n    \n    void init(int n) {\n        par.resize(n);\n        dsu_2ecc.resize(n);\n        dsu_cc.resize(n);\n        dsu_cc_size.resize(n);\n        lca_iteration = 0;\n        last_visit.assign(n, 0);\n        for (int i=0; i<n; ++i) {\n            dsu_2ecc[i] = i;\n            dsu_cc[i] = i;\n            dsu_cc_size[i] = 1;\n            par[i] = -1;\n        }\n        bridges = 0;\n    }\n\n    int find_2ecc(int v) {\n        if (v == -1)\n            return -1;\n        return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);\n    }\n\n    int find_cc(int v) {\n        v = find_2ecc(v);\n        return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);\n    }\n\n    void make_root(int v) {\n        v = find_2ecc(v);\n        int root = v;\n        int child = -1;\n        while (v != -1) {\n            int p = find_2ecc(par[v]);\n            par[v] = child;\n            dsu_cc[v] = root;\n            child = v;\n            v = p;\n        }\n        dsu_cc_size[root] = dsu_cc_size[child];\n    }\n\n    void merge_path (int a, int b) {\n        ++lca_iteration;\n        vector<int> path_a, path_b;\n        int lca = -1;\n        while (lca == -1) {\n            if (a != -1) {\n                a = find_2ecc(a);\n                path_a.push_back(a);\n                if (last_visit[a] == lca_iteration){\n                    lca = a;\n                    break;\n                    }\n                last_visit[a] = lca_iteration;\n                a = par[a];\n            }\n            if (b != -1) {\n                b = find_2ecc(b);\n                path_b.push_back(b);\n                if (last_visit[b] == lca_iteration){\n                    lca = b;\n                    break;\n                    }\n                last_visit[b] = lca_iteration;\n                b = par[b];\n            }\n\n        }\n\n        for (int v : path_a) {\n            dsu_2ecc[v] = lca;\n            if (v == lca)\n                break;\n            --bridges;\n        }\n        for (int v : path_b) {\n            dsu_2ecc[v] = lca;\n            if (v == lca)\n                break;\n            --bridges;\n        }\n    }\n\n    void add_edge(int a, int b) {\n        a = find_2ecc(a);\n        b = find_2ecc(b);\n        if (a == b)\n            return;\n\n        int ca = find_cc(a);\n        int cb = find_cc(b);\n\n        if (ca != cb) {\n            ++bridges;\n            if (dsu_cc_size[ca] > dsu_cc_size[cb]) {\n                swap(a, b);\n                swap(ca, cb);\n            }\n            make_root(a);\n            par[a] = dsu_cc[a] = b;\n            dsu_cc_size[cb] += dsu_cc_size[a];\n        } else {\n            merge_path(a, b);\n        }\n    }\n};\n```
['C++']