# Problem - 1578C - Codeforces Cactus lady loves h...

Question

Problem - 1578C - Codeforces

Cactus lady loves her cactuses very much. Especially she likes a small cactus named Cing. Cing can be seen as a connected undirected graph in which every vertex lies on at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed.

She bought a special grid for her special little cactus Cing. This grid can be represented as a graph consisting of two paths of length $400\\,000$ , $u\_{(0, -200\\,000)} - u\_{(0, -199\\,999)} - \\ldots - u\_{(0, 200\\,000)}$ and $u\_{(1, -200\\,000)} - u\_{(1, -199\\,999)} - \\ldots - u\_{(1, 200\\,000)}$ , connected together by $400\\,001$ edges $(u\_{(0, i)}, u\_{(1, i)})$ for each $i$ . In other words, a grid can be seen as a ladder.

Cactus lady wants to know whether she can embed Cing into this grid, i.e., map each vertex of the cactus onto a separate vertex of the grid while each edge of the cactus will be mapped onto some edge of the grid.

Input

The first line contains an integer $t$ — the number of test cases.

Each test case begins with a line containing two integers $n$ and $m$ — the number of vertices and the number of edges in a given cactus, respectively ( $1 \\le n \\le 200\\,000$ ; $0 \\le m \\le 250\\,000$ ).

Each of the following $m$ lines contains two integers $v$ and $u$ , describing the edges of the cactus ( $1 \\le v, u \\le n, u \\ne v$ ).

The total sum of all $n$ in the input doesn't exceed $200\\,000$ .

Output

Print an answer for each test case in the same order the cases appear in the input.

For each test case print "No" in the first line, if no layout exists.

Otherwise print "Yes" in the first line, and the following $n$ lines describing the layout. The $i$ -th of these $n$ lines should contain two integers $x\_i$ and $y\_i$ , the location of the $i$ -th vertex ( $0 \\le x\_i \\le 1$ ; $-200\\,000 \\le y\_i \\le 200\\,000$ ).

Example

Input

Output

Note

Empty lines between test cases are for clarity. In real test cases there are no empty lines.

In these notes, we consider the embeddings for tests 2 and 4.

We start with the embedding for test 2.

Here goes the embedding for test 4.

. T YOU ARE PROHIBITED FROM LOOKING FOR THE SOLUTION ON THE INTERNET.

Answer 1

思路

这题不能只判断“最大度数不超过 3、所有环都是偶环”。

例如某些最大度数为 3 的树，仍然无法放进两行梯子中。真正的限制来自：沿着梯子的横坐标扫描时，每一列最多只有两个顶点，而且某一行被占用后，另一行能够向后利用的连续空位是有限的。

1. 梯子中的环

梯子中的任意简单环一定是一个 $2\times k$ 矩形的边界，因此：

环长必须是偶数；
环上只有四个角能够连接环外部分；
选定一条竖边作为环的左侧竖边后，另一条竖边唯一确定，它们在环上相距半个环长。

设环按顺序为

c_0,c_1,\ldots,c_{2k-1}.

若 $c_0c_1$ 是左侧竖边，则右侧竖边为

c_kc_{k+1}.

2. 两种扫描状态

把尚未绘制的部分向右展开。

单轨状态 `need(p -> v)`

边 $pv$ 已经被水平放置， $v$ 位于当前列；另一行当前为空。

定义：

need(p\to v)

表示为了完成 $v$ 一侧的整个连通分量，另一行在当前位置之前至少需要多少个连续空单元格。

如果只有一个后继并继续水平前进，空白长度增加 1，因此：

need(p\to v)=\max(1,need(v\to u)-1).

在分叉处：

一个分支水平向前；
一个分支通过当前列的竖边进入另一行；
竖向分支可以向后放置一条纯路径，并向前继续；
向后路径长度为 $L$ 时，需要 $L+1$ 个连续空位。

如果遇到环，则当前顶点必须是环的一个角。枚举环的两个方向，并检查：

环长为偶数；
所有连接环外的桥都位于四个角；
左下角向后的部分必须是一条纯路径；
右侧两个角继续形成单轨或双轨状态。

双轨状态 `pair(p -> v, q -> w)`

当前列上下两格都已经被 $v,w$ 占用。

此时两顶点都不能：

使用竖边分叉；
进入一个环；
同时产生两个后继。

因此每条轨道最多只能水平继续一个顶点：

两条都结束：成功；
一条结束：另一条从下一列进入单轨状态，初始空白长度为 1；
两条都继续：递归进入新的双轨状态。

3. 向后部分为什么必须是纯路径

当一个分支向后放入另一行时，它所在的另一侧行已经被主干占用，因此它只能沿唯一的一行一直延伸。

所以该方向上的整个连通分量必须：

不包含环；
不包含度数为 3 的顶点。

将每个环收缩成一个结点后，所有桥组成一棵树。通过树上子树统计，可以在线性时间内判断每条有向桥的一侧是否是这种纯路径，并得到路径长度。

4. 选择中心竖边

任何可行布局都可以选择一条竖边作为中心：

如果图是树且布局没有竖边，那么整个图只能是一条路径；路径显然可以重新布局，使任意一条边成为竖边。
如果有环，环本身一定包含两条竖边。

中心竖边有两种情况。

中心是一条桥

桥的两个端点不能位于环上。把两个端点剩余的边分别分配到左、右两侧，每侧最多有上下两个分量，然后使用单轨或双轨状态检查。

中心是环边

枚举环上的每条边作为左侧竖边，另一条对边自动确定。检查四个角向左右延伸的分量。

所有状态都会记住实现最优值的具体选择，最后反向构造坐标。

正确性要点

单轨状态完整枚举了当前顶点可使用的两个剩余方向：水平和竖直。
双轨状态中，两格均被占用，因此只能水平前进，不存在遗漏的合法分叉。
一个环在梯子中的形状唯一是矩形边界，枚举一条竖边及两个方向即可覆盖所有环布局。
向后放置的部分只能占据一条直线，因此“不含环且不含三度点”既是必要条件，也是充分条件。
任意布局都存在一条可作为中心的竖边，枚举所有桥和环边不会漏解。
构造过程中，每一次向后放置都不超过状态记录的连续空位长度，因此不会发生顶点重叠。

复杂度

每条有向桥状态只计算一次，双轨状态沿确定的桥链推进。

O(n+m)

空间复杂度同样为：

O(n+m).

C++17

cpp
#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

struct Adj {
    int to, id;
};

struct NeedChoice {
    enum Type { FAIL, END, HORIZ, VERT, BRANCH, CYCLE } type = FAIL;

    int nextDir = -1;

    int hDir = -1;
    int vertDir = -1;
    int backDir = -1;
    int fwdDir = -1;

    int cycStep = 0;
};

struct PairChoice {
    enum Type { PFAIL, PEND, ONE1, ONE2, BOTH } type = PFAIL;
    int d1 = -1;
    int d2 = -1;
};

struct PairData {
    unsigned char status = 0;
    bool value = false;
    PairChoice choice;
};

struct State {
    int type; // 0 = need, 1 = pair
    int a, b;
};

struct Task {
    int type; // 0 = need, 1 = pair
    int d1, d2;
    int row;
    int col;
    int sign;
    int gap;
};

struct CentralChoice {
    int type = -1; // 0 = bridge, 1 = cycle

    int edge = -1;
    int lu = -1, ru = -1;
    int lv = -1, rv = -1;

    int cycle = -1;
    int start = -1;
};

class Solver {
public:
    int n, m;

    vector<int> edgeU, edgeV;
    vector<vector<Adj>> graph;
    vector<vector<Adj>> bridgeGraph;

    vector<char> isCycleEdge;

    vector<vector<int>> cycles;
    vector<int> cycleId;
    vector<int> cyclePos;
    vector<int> cycleAttachmentCount;

    vector<int> componentId;
    vector<vector<pair<int, int>>> componentTree;

    vector<int> componentSize;
    vector<int> componentCycles;
    vector<int> componentDegreeThree;

    vector<int> componentParent;
    vector<int> componentParentEdge;
    vector<int> componentOrder;

    vector<int> subtreeSize;
    vector<int> subtreeCycles;
    vector<int> subtreeDegreeThree;

    // rayLength[d] != -1 iff the component in direction d
    // is a path whose attachment vertex is an endpoint.
    vector<int> rayLength;

    vector<int> needValue;
    vector<unsigned char> needStatus;
    vector<NeedChoice> needChoice;

    unordered_map<unsigned long long, PairData> pairMemo;

    vector<int> answerX;
    vector<int> answerY;

    CentralChoice central;

    Solver(int n, int m) : n(n), m(m) {
        edgeU.resize(m);
        edgeV.resize(m);

        graph.assign(n, {});
        bridgeGraph.assign(n, {});

        isCycleEdge.assign(m, false);

        cycleId.assign(n, -1);
        cyclePos.assign(n, -1);

        rayLength.assign(2 * m, -1);

        needValue.assign(2 * m, -1);
        needStatus.assign(2 * m, 0);
        needChoice.resize(2 * m);

        answerX.assign(n, -1);
        answerY.assign(n, INT_MAX);

        pairMemo.reserve(max(16, 8 * n));
        pairMemo.max_load_factor(0.7f);
    }

    void addEdge(int id, int u, int v) {
        edgeU[id] = u;
        edgeV[id] = v;

        graph[u].push_back({v, id});
        graph[v].push_back({u, id});
    }

    int directionId(int edge, int from) const {
        return edgeU[edge] == from ? 2 * edge : 2 * edge + 1;
    }

    int directionFrom(int direction) const {
        int edge = direction / 2;
        return direction % 2 == 0 ? edgeU[edge] : edgeV[edge];
    }

    int directionTo(int direction) const {
        int edge = direction / 2;
        return direction % 2 == 0 ? edgeV[edge] : edgeU[edge];
    }

    unsigned long long pairKey(int d1, int d2) const {
        return
            (static_cast<unsigned long long>(
                static_cast<unsigned int>(d1)
            ) << 32)
            | static_cast<unsigned int>(d2);
    }

    bool findCycles() {
        vector<int> state(n, 0);
        vector<int> parent(n, -1);
        vector<int> parentEdge(n, -1);
        vector<int> depth(n, 0);
        vector<int> iteratorIndex(n, 0);

        for (int root = 0; root < n; ++root) {
            if (state[root] != 0) {
                continue;
            }

            vector<int> stack;
            stack.push_back(root);
            state[root] = 1;

            while (!stack.empty()) {
                int vertex = stack.back();

                if (iteratorIndex[vertex] ==
                    static_cast<int>(graph[vertex].size())) {
                    state[vertex] = 2;
                    stack.pop_back();
                    continue;
                }

                Adj edge = graph[vertex][iteratorIndex[vertex]++];

                if (edge.id == parentEdge[vertex]) {
                    continue;
                }

                int to = edge.to;

                if (state[to] == 0) {
                    parent[to] = vertex;
                    parentEdge[to] = edge.id;
                    depth[to] = depth[vertex] + 1;
                    state[to] = 1;
                    stack.push_back(to);
                } else if (state[to] == 1 &&
                           depth[to] < depth[vertex]) {
                    vector<int> cycle;

                    int current = vertex;
                    while (current != to) {
                        cycle.push_back(current);
                        current = parent[current];
                    }

                    cycle.push_back(to);
                    reverse(cycle.begin(), cycle.end());

                    int id = static_cast<int>(cycles.size());

                    for (int i = 0;
                         i < static_cast<int>(cycle.size());
                         ++i) {
                        int v = cycle[i];

                        if (cycleId[v] != -1) {
                            return false;
                        }

                        cycleId[v] = id;
                        cyclePos[v] = i;
                    }

                    current = vertex;

                    while (current != to) {
                        isCycleEdge[parentEdge[current]] = true;
                        current = parent[current];
                    }

                    isCycleEdge[edge.id] = true;
                    cycles.push_back(move(cycle));
                }
            }
        }

        return true;
    }

    void buildBridgeGraph() {
        for (int edge = 0; edge < m; ++edge) {
            if (isCycleEdge[edge]) {
                continue;
            }

            int u = edgeU[edge];
            int v = edgeV[edge];

            bridgeGraph[u].push_back({v, edge});
            bridgeGraph[v].push_back({u, edge});
        }

        cycleAttachmentCount.assign(cycles.size(), 0);

        for (int id = 0;
             id < static_cast<int>(cycles.size());
             ++id) {
            int count = 0;

            for (int vertex : cycles[id]) {
                if (!bridgeGraph[vertex].empty()) {
                    ++count;
                }
            }

            cycleAttachmentCount[id] = count;
        }
    }

    void buildComponentTree() {
        componentId.assign(n, -1);

        componentSize.clear();
        componentCycles.clear();
        componentDegreeThree.clear();

        for (int id = 0;
             id < static_cast<int>(cycles.size());
             ++id) {
            int component = static_cast<int>(componentSize.size());
            int degreeThree = 0;

            for (int vertex : cycles[id]) {
                componentId[vertex] = component;

                if (graph[vertex].size() == 3) {
                    ++degreeThree;
                }
            }

            componentSize.push_back(cycles[id].size());
            componentCycles.push_back(1);
            componentDegreeThree.push_back(degreeThree);
        }

        for (int vertex = 0; vertex < n; ++vertex) {
            if (componentId[vertex] != -1) {
                continue;
            }

            int component = static_cast<int>(componentSize.size());

            componentId[vertex] = component;
            componentSize.push_back(1);
            componentCycles.push_back(0);
            componentDegreeThree.push_back(
                graph[vertex].size() == 3 ? 1 : 0
            );
        }

        int components = componentSize.size();

        componentTree.assign(components, {});

        for (int edge = 0; edge < m; ++edge) {
            if (isCycleEdge[edge]) {
                continue;
            }

            int left = componentId[edgeU[edge]];
            int right = componentId[edgeV[edge]];

            componentTree[left].push_back({right, edge});
            componentTree[right].push_back({left, edge});
        }

        componentParent.assign(components, -1);
        componentParentEdge.assign(components, -1);
        componentOrder.clear();
        componentOrder.reserve(components);

        vector<int> stack = {0};
        componentParent[0] = -2;

        while (!stack.empty()) {
            int vertex = stack.back();
            stack.pop_back();

            componentOrder.push_back(vertex);

            for (auto [to, edge] : componentTree[vertex]) {
                if (to == componentParent[vertex]) {
                    continue;
                }

                componentParent[to] = vertex;
                componentParentEdge[to] = edge;
                stack.push_back(to);
            }
        }

        subtreeSize = componentSize;
        subtreeCycles = componentCycles;
        subtreeDegreeThree = componentDegreeThree;

        for (int i = components - 1; i > 0; --i) {
            int vertex = componentOrder[i];
            int parent = componentParent[vertex];

            subtreeSize[parent] += subtreeSize[vertex];
            subtreeCycles[parent] += subtreeCycles[vertex];
            subtreeDegreeThree[parent] +=
                subtreeDegreeThree[vertex];
        }

        int totalSize = subtreeSize[0];
        int totalCycles = subtreeCycles[0];
        int totalDegreeThree = subtreeDegreeThree[0];

        auto setRay = [&](int from,
                          int edge,
                          int size,
                          int cycleCount,
                          int degreeThreeCount) {
            int direction = directionId(edge, from);

            if (cycleCount == 0 && degreeThreeCount == 0) {
                rayLength[direction] = size;
            }
        };

        for (int edge = 0; edge < m; ++edge) {
            if (isCycleEdge[edge]) {
                continue;
            }

            int u = edgeU[edge];
            int v = edgeV[edge];

            int componentU = componentId[u];
            int componentV = componentId[v];

            if (componentParent[componentV] == componentU) {
                setRay(
                    u,
                    edge,
                    subtreeSize[componentV],
                    subtreeCycles[componentV],
                    subtreeDegreeThree[componentV]
                );

                setRay(
                    v,
                    edge,
                    totalSize - subtreeSize[componentV],
                    totalCycles - subtreeCycles[componentV],
                    totalDegreeThree -
                        subtreeDegreeThree[componentV]
                );
            } else {
                setRay(
                    v,
                    edge,
                    subtreeSize[componentU],
                    subtreeCycles[componentU],
                    subtreeDegreeThree[componentU]
                );

                setRay(
                    u,
                    edge,
                    totalSize - subtreeSize[componentU],
                    totalCycles - subtreeCycles[componentU],
                    totalDegreeThree -
                        subtreeDegreeThree[componentU]
                );
            }
        }
    }

    vector<int> childrenDirections(int vertex,
                                   int parent) const {
        vector<int> result;

        for (Adj edge : bridgeGraph[vertex]) {
            if (edge.to != parent) {
                result.push_back(directionId(edge.id, vertex));
            }
        }

        return result;
    }

    struct VerticalPlan {
        int back = -1;
        int forward = -1;
        int length = 0;
    };

    vector<VerticalPlan>
    getVerticalPlans(int verticalDirection) const {
        int parent = directionFrom(verticalDirection);
        int vertex = directionTo(verticalDirection);

        if (cycleId[vertex] != -1) {
            return {};
        }

        vector<int> children =
            childrenDirections(vertex, parent);

        vector<VerticalPlan> result;

        if (children.empty()) {
            result.push_back({-1, -1, 0});
        } else if (children.size() == 1) {
            result.push_back({-1, children[0], 0});

            if (rayLength[children[0]] != -1) {
                result.push_back({
                    children[0],
                    -1,
                    rayLength[children[0]]
                });
            }
        } else if (children.size() == 2) {
            if (rayLength[children[0]] != -1) {
                result.push_back({
                    children[0],
                    children[1],
                    rayLength[children[0]]
                });
            }

            if (rayLength[children[1]] != -1) {
                result.push_back({
                    children[1],
                    children[0],
                    rayLength[children[1]]
                });
            }
        }

        return result;
    }

    int getCycleVertex(int id,
                       int position,
                       int step,
                       int offset) const {
        int length = cycles[id].size();

        long long index =
            position + 1LL * step * offset;

        index %= length;

        if (index < 0) {
            index += length;
        }

        return cycles[id][index];
    }

    bool getCycleOrientation(
        int id,
        int position,
        int step,
        int incomingParent,
        int& c0,
        int& c1,
        int& ck,
        int& ck1,
        int& backDirection,
        int& bottomOutput,
        int& topOutput,
        bool hasIncoming
    ) const {
        int length = cycles[id].size();

        if (length % 2 != 0) {
            return false;
        }

        int half = length / 2;

        c0 = getCycleVertex(id, position, step, 0);
        c1 = getCycleVertex(id, position, step, 1);
        ck = getCycleVertex(id, position, step, half);
        ck1 = getCycleVertex(id, position, step, half + 1);

        int attachments =
            static_cast<int>(!bridgeGraph[c0].empty()) +
            static_cast<int>(!bridgeGraph[c1].empty()) +
            static_cast<int>(!bridgeGraph[ck].empty()) +
            static_cast<int>(!bridgeGraph[ck1].empty());

        if (attachments != cycleAttachmentCount[id]) {
            return false;
        }

        if (hasIncoming) {
            if (bridgeGraph[c0].size() != 1 ||
                bridgeGraph[c0][0].to != incomingParent) {
                return false;
            }
        }

        backDirection = -1;
        bottomOutput = -1;
        topOutput = -1;

        if (!bridgeGraph[c1].empty()) {
            backDirection =
                directionId(bridgeGraph[c1][0].id, c1);

            if (rayLength[backDirection] == -1) {
                return false;
            }
        }

        if (!bridgeGraph[ck].empty()) {
            bottomOutput =
                directionId(bridgeGraph[ck][0].id, ck);
        }

        if (!bridgeGraph[ck1].empty()) {
            topOutput =
                directionId(bridgeGraph[ck1][0].id, ck1);
        }

        return true;
    }

    int getStatus(const State& state) {
        if (state.type == 0) {
            return needStatus[state.a];
        }

        return pairMemo[pairKey(state.a, state.b)].status;
    }

    void setStatus(const State& state, int value) {
        if (state.type == 0) {
            needStatus[state.a] =
                static_cast<unsigned char>(value);
        } else {
            pairMemo[pairKey(state.a, state.b)].status =
                static_cast<unsigned char>(value);
        }
    }

    void addSideDependency(vector<State>& dependencies,
                           int d1,
                           int d2) {
        if (d1 == -1 && d2 == -1) {
            return;
        }

        if (d1 == -1) {
            dependencies.push_back({0, d2, -1});
        } else if (d2 == -1) {
            dependencies.push_back({0, d1, -1});
        } else {
            dependencies.push_back({1, d1, d2});
        }
    }

    vector<State> collectDependencies(const State& state) {
        vector<State> dependencies;

        if (state.type == 1) {
            int d1 = state.a;
            int d2 = state.b;

            int v = directionTo(d1);
            int p = directionFrom(d1);

            int w = directionTo(d2);
            int q = directionFrom(d2);

            if (cycleId[v] != -1 || cycleId[w] != -1) {
                return dependencies;
            }

            vector<int> first =
                childrenDirections(v, p);

            vector<int> second =
                childrenDirections(w, q);

            if (first.size() > 1 || second.size() > 1) {
                return dependencies;
            }

            if (first.empty() && second.empty()) {
                return dependencies;
            }

            if (first.empty()) {
                dependencies.push_back({0, second[0], -1});
            } else if (second.empty()) {
                dependencies.push_back({0, first[0], -1});
            } else {
                dependencies.push_back({
                    1,
                    first[0],
                    second[0]
                });
            }

            return dependencies;
        }

        int direction = state.a;
        int parent = directionFrom(direction);
        int vertex = directionTo(direction);

        if (cycleId[vertex] != -1) {
            int id = cycleId[vertex];
            int position = cyclePos[vertex];

            for (int step : {1, -1}) {
                int c0, c1, ck, ck1;
                int back, bottom, top;

                if (getCycleOrientation(
                    id,
                    position,
                    step,
                    parent,
                    c0,
                    c1,
                    ck,
                    ck1,
                    back,
                    bottom,
                    top,
                    true
                )) {
                    addSideDependency(
                        dependencies,
                        bottom,
                        top
                    );
                }
            }

            return dependencies;
        }

        vector<int> children =
            childrenDirections(vertex, parent);

        if (children.size() == 1) {
            dependencies.push_back({
                0,
                children[0],
                -1
            });

            for (VerticalPlan plan :
                 getVerticalPlans(children[0])) {
                if (plan.forward != -1) {
                    dependencies.push_back({
                        0,
                        plan.forward,
                        -1
                    });
                }
            }
        } else if (children.size() == 2) {
            for (int choice = 0; choice < 2; ++choice) {
                int horizontal = children[choice];
                int vertical = children[choice ^ 1];

                for (VerticalPlan plan :
                     getVerticalPlans(vertical)) {
                    if (plan.forward == -1) {
                        dependencies.push_back({
                            0,
                            horizontal,
                            -1
                        });
                    } else {
                        dependencies.push_back({
                            1,
                            horizontal,
                            plan.forward
                        });
                    }
                }
            }
        }

        return dependencies;
    }

    bool sideAlreadyCalculated(int d1, int d2) {
        if (d1 == -1 && d2 == -1) {
            return true;
        }

        if (d1 == -1) {
            return needValue[d2] <= 1;
        }

        if (d2 == -1) {
            return needValue[d1] <= 1;
        }

        return pairMemo[pairKey(d1, d2)].value;
    }

    void calculatePair(int d1, int d2) {
        PairData& data = pairMemo[pairKey(d1, d2)];

        data.value = false;
        data.choice = PairChoice();

        int v = directionTo(d1);
        int p = directionFrom(d1);

        int w = directionTo(d2);
        int q = directionFrom(d2);

        if (cycleId[v] != -1 || cycleId[w] != -1) {
            return;
        }

        vector<int> first =
            childrenDirections(v, p);

        vector<int> second =
            childrenDirections(w, q);

        if (first.size() > 1 || second.size() > 1) {
            return;
        }

        if (first.empty() && second.empty()) {
            data.value = true;
            data.choice.type = PairChoice::PEND;
            return;
        }

        if (first.empty()) {
            if (needValue[second[0]] <= 1) {
                data.value = true;
                data.choice.type = PairChoice::ONE2;
                data.choice.d1 = second[0];
            }

            return;
        }

        if (second.empty()) {
            if (needValue[first[0]] <= 1) {
                data.value = true;
                data.choice.type = PairChoice::ONE1;
                data.choice.d1 = first[0];
            }

            return;
        }

        PairData& next =
            pairMemo[pairKey(first[0], second[0])];

        if (next.value) {
            data.value = true;
            data.choice.type = PairChoice::BOTH;
            data.choice.d1 = first[0];
            data.choice.d2 = second[0];
        }
    }

    void calculateNeed(int direction) {
        int parent = directionFrom(direction);
        int vertex = directionTo(direction);

        int best = INF;
        NeedChoice bestChoice;

        auto consider = [&](int value,
                            const NeedChoice& choice) {
            if (value < best) {
                best = value;
                bestChoice = choice;
            }
        };

        if (cycleId[vertex] != -1) {
            int id = cycleId[vertex];
            int position = cyclePos[vertex];

            for (int step : {1, -1}) {
                int c0, c1, ck, ck1;
                int back, bottom, top;

                if (!getCycleOrientation(
                    id,
                    position,
                    step,
                    parent,
                    c0,
                    c1,
                    ck,
                    ck1,
                    back,
                    bottom,
                    top,
                    true
                )) {
                    continue;
                }

                if (!sideAlreadyCalculated(bottom, top)) {
                    continue;
                }

                NeedChoice choice;
                choice.type = NeedChoice::CYCLE;
                choice.cycStep = step;

                int backwardLength =
                    back == -1 ? 0 : rayLength[back];

                consider(backwardLength + 1, choice);
            }

            needValue[direction] = best;
            needChoice[direction] = bestChoice;
            return;
        }

        vector<int> children =
            childrenDirections(vertex, parent);

        if (children.empty()) {
            best = 1;
            bestChoice.type = NeedChoice::END;
        } else if (children.size() == 1) {
            int child = children[0];

            if (needValue[child] < INF) {
                NeedChoice choice;
                choice.type = NeedChoice::HORIZ;
                choice.nextDir = child;

                consider(
                    max(1, needValue[child] - 1),
                    choice
                );
            }

            for (VerticalPlan plan :
                 getVerticalPlans(child)) {
                if (plan.forward != -1 &&
                    needValue[plan.forward] > 1) {
                    continue;
                }

                NeedChoice choice;
                choice.type = NeedChoice::VERT;
                choice.vertDir = child;
                choice.backDir = plan.back;
                choice.fwdDir = plan.forward;

                consider(plan.length + 1, choice);
            }
        } else if (children.size() == 2) {
            for (int selected = 0;
                 selected < 2;
                 ++selected) {
                int horizontal = children[selected];
                int vertical = children[selected ^ 1];

                for (VerticalPlan plan :
                     getVerticalPlans(vertical)) {
                    bool possible;

                    if (plan.forward == -1) {
                        possible =
                            needValue[horizontal] <= 1;
                    } else {
                        possible = pairMemo[
                            pairKey(
                                horizontal,
                                plan.forward
                            )
                        ].value;
                    }

                    if (!possible) {
                        continue;
                    }

                    NeedChoice choice;
                    choice.type = NeedChoice::BRANCH;
                    choice.hDir = horizontal;
                    choice.vertDir = vertical;
                    choice.backDir = plan.back;
                    choice.fwdDir = plan.forward;

                    consider(plan.length + 1, choice);
                }
            }
        }

        needValue[direction] = best;
        needChoice[direction] = bestChoice;
    }

    void ensureCalculated(State root) {
        vector<State> stack;
        stack.push_back(root);

        while (!stack.empty()) {
            State state = stack.back();

            int status = getStatus(state);

            if (status == 2) {
                stack.pop_back();
                continue;
            }

            if (status == 0) {
                setStatus(state, 1);
            }

            vector<State> dependencies =
                collectDependencies(state);

            bool pushed = false;

            for (State dependency : dependencies) {
                if (getStatus(dependency) == 0) {
                    stack.push_back(dependency);
                    pushed = true;
                    break;
                }
            }

            if (pushed) {
                continue;
            }

            if (state.type == 0) {
                calculateNeed(state.a);
            } else {
                calculatePair(state.a, state.b);
            }

            setStatus(state, 2);
            stack.pop_back();
        }
    }

    bool oneSidePossible(int direction) {
        ensureCalculated({0, direction, -1});
        return needValue[direction] <= 1;
    }

    bool pairPossible(int d1, int d2) {
        ensureCalculated({1, d1, d2});
        return pairMemo[pairKey(d1, d2)].value;
    }

    bool sidePossible(int d1, int d2) {
        if (d1 == -1 && d2 == -1) {
            return true;
        }

        if (d1 == -1) {
            return oneSidePossible(d2);
        }

        if (d2 == -1) {
            return oneSidePossible(d1);
        }

        return pairPossible(d1, d2);
    }

    vector<pair<int, int>>
    getAssignments(const vector<int>& directions) const {
        if (directions.empty()) {
            return {{-1, -1}};
        }

        if (directions.size() == 1) {
            return {
                {directions[0], -1},
                {-1, directions[0]}
            };
        }

        if (directions.size() == 2) {
            return {
                {directions[0], directions[1]},
                {directions[1], directions[0]}
            };
        }

        return {};
    }

    int onlyBridgeDirection(int vertex) const {
        if (bridgeGraph[vertex].empty()) {
            return -1;
        }

        return directionId(
            bridgeGraph[vertex][0].id,
            vertex
        );
    }

    bool findCentralObject() {
        for (int edge = 0; edge < m; ++edge) {
            if (isCycleEdge[edge]) {
                continue;
            }

            int u = edgeU[edge];
            int v = edgeV[edge];

            if (cycleId[u] != -1 ||
                cycleId[v] != -1) {
                continue;
            }

            vector<int> directionsU;
            vector<int> directionsV;

            for (Adj adjacent : bridgeGraph[u]) {
                if (adjacent.id != edge) {
                    directionsU.push_back(
                        directionId(adjacent.id, u)
                    );
                }
            }

            for (Adj adjacent : bridgeGraph[v]) {
                if (adjacent.id != edge) {
                    directionsV.push_back(
                        directionId(adjacent.id, v)
                    );
                }
            }

            for (auto [leftU, rightU] :
                 getAssignments(directionsU)) {
                for (auto [leftV, rightV] :
                     getAssignments(directionsV)) {
                    if (sidePossible(leftU, leftV) &&
                        sidePossible(rightU, rightV)) {
                        central.type = 0;
                        central.edge = edge;

                        central.lu = leftU;
                        central.ru = rightU;
                        central.lv = leftV;
                        central.rv = rightV;

                        return true;
                    }
                }
            }
        }

        for (int id = 0;
             id < static_cast<int>(cycles.size());
             ++id) {
            int length = cycles[id].size();

            if (length % 2 != 0) {
                continue;
            }

            int half = length / 2;

            for (int start = 0;
                 start < length;
                 ++start) {
                int c0 = cycles[id][start];
                int c1 = cycles[id][(start + 1) % length];
                int ck = cycles[id][(start + half) % length];
                int ck1 =
                    cycles[id][(start + half + 1) % length];

                int attachments =
                    static_cast<int>(
                        !bridgeGraph[c0].empty()
                    ) +
                    static_cast<int>(
                        !bridgeGraph[c1].empty()
                    ) +
                    static_cast<int>(
                        !bridgeGraph[ck].empty()
                    ) +
                    static_cast<int>(
                        !bridgeGraph[ck1].empty()
                    );

                if (attachments !=
                    cycleAttachmentCount[id]) {
                    continue;
                }

                int d0 = onlyBridgeDirection(c0);
                int d1 = onlyBridgeDirection(c1);
                int dk = onlyBridgeDirection(ck);
                int dk1 = onlyBridgeDirection(ck1);

                if (sidePossible(d0, d1) &&
                    sidePossible(dk, dk1)) {
                    central.type = 1;
                    central.cycle = id;
                    central.start = start;
                    return true;
                }
            }
        }

        return false;
    }

    void put(int vertex, int row, int column) {
        if (answerY[vertex] != INT_MAX) {
            if (answerX[vertex] != row ||
                answerY[vertex] != column) {
                throw runtime_error(
                    "Inconsistent placement"
                );
            }

            return;
        }

        answerX[vertex] = row;
        answerY[vertex] = column;
    }

    void placeRay(int direction,
                  int row,
                  int column,
                  int step) {
        int previous = directionFrom(direction);
        int current = directionTo(direction);

        while (true) {
            put(current, row, column);

            int next = -1;

            for (Adj edge : bridgeGraph[current]) {
                if (edge.to == previous) {
                    continue;
                }

                if (next != -1) {
                    throw runtime_error("Invalid ray");
                }

                next = edge.to;
            }

            if (next == -1) {
                break;
            }

            previous = current;
            current = next;
            column += step;
        }
    }

    void pushSide(vector<Task>& tasks,
                  int d1,
                  int d2,
                  int firstRow,
                  int column,
                  int sign) {
        if (d1 == -1 && d2 == -1) {
            return;
        }

        if (d1 == -1) {
            tasks.push_back({
                0,
                d2,
                -1,
                1 - firstRow,
                column,
                sign,
                1
            });
        } else if (d2 == -1) {
            tasks.push_back({
                0,
                d1,
                -1,
                firstRow,
                column,
                sign,
                1
            });
        } else {
            tasks.push_back({
                1,
                d1,
                d2,
                firstRow,
                column,
                sign,
                0
            });
        }
    }

    void construct() {
        vector<Task> tasks;

        if (central.type == 0) {
            int edge = central.edge;
            int u = edgeU[edge];
            int v = edgeV[edge];

            put(u, 0, 0);
            put(v, 1, 0);

            pushSide(
                tasks,
                central.lu,
                central.lv,
                0,
                -1,
                -1
            );

            pushSide(
                tasks,
                central.ru,
                central.rv,
                0,
                1,
                1
            );
        } else {
            int id = central.cycle;
            int length = cycles[id].size();
            int half = length / 2;
            int start = central.start;

            auto at = [&](int offset) {
                return cycles[id][
                    (start + offset) % length
                ];
            };

            put(at(0), 0, 0);

            for (int i = 1; i <= half; ++i) {
                put(at(i), 1, i - 1);
            }

            for (int i = half + 1;
                 i < length;
                 ++i) {
                put(at(i), 0, length - i);
            }

            int d0 = onlyBridgeDirection(at(0));
            int d1 = onlyBridgeDirection(at(1));
            int dk = onlyBridgeDirection(at(half));
            int dk1 =
                onlyBridgeDirection(at(half + 1));

            pushSide(tasks, d0, d1, 0, -1, -1);
            pushSide(tasks, dk, dk1, 1, half, 1);
        }

        while (!tasks.empty()) {
            Task task = tasks.back();
            tasks.pop_back();

            if (task.type == 1) {
                int first = task.d1;
                int second = task.d2;

                int v = directionTo(first);
                int w = directionTo(second);

                put(v, task.row, task.col);
                put(w, 1 - task.row, task.col);

                PairChoice choice =
                    pairMemo[
                        pairKey(first, second)
                    ].choice;

                if (choice.type == PairChoice::PEND) {
                    continue;
                }

                if (choice.type == PairChoice::ONE1) {
                    tasks.push_back({
                        0,
                        choice.d1,
                        -1,
                        task.row,
                        task.col + task.sign,
                        task.sign,
                        1
                    });
                } else if (
                    choice.type == PairChoice::ONE2
                ) {
                    tasks.push_back({
                        0,
                        choice.d1,
                        -1,
                        1 - task.row,
                        task.col + task.sign,
                        task.sign,
                        1
                    });
                } else if (
                    choice.type == PairChoice::BOTH
                ) {
                    tasks.push_back({
                        1,
                        choice.d1,
                        choice.d2,
                        task.row,
                        task.col + task.sign,
                        task.sign,
                        0
                    });
                } else {
                    throw runtime_error(
                        "Invalid pair choice"
                    );
                }

                continue;
            }

            int direction = task.d1;
            int parent = directionFrom(direction);
            int vertex = directionTo(direction);

            put(vertex, task.row, task.col);

            NeedChoice choice = needChoice[direction];

            if (needValue[direction] > task.gap) {
                throw runtime_error(
                    "Insufficient free space"
                );
            }

            if (choice.type == NeedChoice::END) {
                continue;
            }

            if (choice.type == NeedChoice::HORIZ) {
                tasks.push_back({
                    0,
                    choice.nextDir,
                    -1,
                    task.row,
                    task.col + task.sign,
                    task.sign,
                    task.gap + 1
                });

                continue;
            }

            if (choice.type == NeedChoice::VERT ||
                choice.type == NeedChoice::BRANCH) {
                int vertical = choice.vertDir;
                int verticalVertex =
                    directionTo(vertical);

                int otherRow = 1 - task.row;

                put(
                    verticalVertex,
                    otherRow,
                    task.col
                );

                if (choice.backDir != -1) {
                    placeRay(
                        choice.backDir,
                        otherRow,
                        task.col - task.sign,
                        -task.sign
                    );
                }

                if (choice.type ==
                    NeedChoice::BRANCH) {
                    if (choice.fwdDir != -1) {
                        tasks.push_back({
                            1,
                            choice.hDir,
                            choice.fwdDir,
                            task.row,
                            task.col + task.sign,
                            task.sign,
                            0
                        });
                    } else {
                        tasks.push_back({
                            0,
                            choice.hDir,
                            -1,
                            task.row,
                            task.col + task.sign,
                            task.sign,
                            1
                        });
                    }
                } else if (choice.fwdDir != -1) {
                    tasks.push_back({
                        0,
                        choice.fwdDir,
                        -1,
                        otherRow,
                        task.col + task.sign,
                        task.sign,
                        1
                    });
                }

                continue;
            }

            if (choice.type == NeedChoice::CYCLE) {
                int id = cycleId[vertex];
                int position = cyclePos[vertex];
                int length = cycles[id].size();
                int half = length / 2;
                int step = choice.cycStep;

                int otherRow = 1 - task.row;

                auto at = [&](int offset) {
                    return getCycleVertex(
                        id,
                        position,
                        step,
                        offset
                    );
                };

                for (int i = 1; i <= half; ++i) {
                    put(
                        at(i),
                        otherRow,
                        task.col +
                            task.sign * (i - 1)
                    );
                }

                for (int i = half + 1;
                     i < length;
                     ++i) {
                    put(
                        at(i),
                        task.row,
                        task.col +
                            task.sign * (length - i)
                    );
                }

                int back = -1;
                int bottom = -1;
                int top = -1;

                if (!bridgeGraph[at(1)].empty()) {
                    back = directionId(
                        bridgeGraph[at(1)][0].id,
                        at(1)
                    );
                }

                if (!bridgeGraph[at(half)].empty()) {
                    bottom = directionId(
                        bridgeGraph[at(half)][0].id,
                        at(half)
                    );
                }

                if (!bridgeGraph[
                        at(half + 1)
                    ].empty()) {
                    top = directionId(
                        bridgeGraph[
                            at(half + 1)
                        ][0].id,
                        at(half + 1)
                    );
                }

                if (back != -1) {
                    placeRay(
                        back,
                        otherRow,
                        task.col - task.sign,
                        -task.sign
                    );
                }

                pushSide(
                    tasks,
                    bottom,
                    top,
                    otherRow,
                    task.col + task.sign * half,
                    task.sign
                );

                continue;
            }

            throw runtime_error("Invalid need choice");
        }
    }

    bool solve() {
        if (n == 1) {
            answerX[0] = 0;
            answerY[0] = 0;
            return true;
        }

        for (int vertex = 0; vertex < n; ++vertex) {
            if (graph[vertex].size() > 3) {
                return false;
            }
        }

        if (!findCycles()) {
            return false;
        }

        buildBridgeGraph();
        buildComponentTree();

        if (!findCentralObject()) {
            return false;
        }

        construct();

        vector<pair<int, int>> occupied;
        occupied.reserve(n);

        for (int vertex = 0; vertex < n; ++vertex) {
            if (answerY[vertex] == INT_MAX) {
                return false;
            }

            if (answerY[vertex] < -200000 ||
                answerY[vertex] > 200000) {
                return false;
            }

            occupied.push_back({
                answerX[vertex],
                answerY[vertex]
            });
        }

        sort(occupied.begin(), occupied.end());

        if (adjacent_find(
                occupied.begin(),
                occupied.end()
            ) != occupied.end()) {
            return false;
        }

        for (int edge = 0; edge < m; ++edge) {
            int u = edgeU[edge];
            int v = edgeV[edge];

            int distance =
                abs(answerX[u] - answerX[v]) +
                abs(answerY[u] - answerY[v]);

            if (distance != 1) {
                return false;
            }
        }

        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;

    while (testCases--) {
        int n, m;
        cin >> n >> m;

        Solver solver(n, m);

        for (int edge = 0; edge < m; ++edge) {
            int u, v;
            cin >> u >> v;

            --u;
            --v;

            solver.addEdge(edge, u, v);
        }

        bool possible = false;

        try {
            possible = solver.solve();
        } catch (...) {
            possible = false;
        }

        if (!possible) {
            cout << "No\n";
            continue;
        }

        cout << "Yes\n";

        for (int vertex = 0; vertex < n; ++vertex) {
            cout << solver.answerX[vertex]
                 << ' '
                 << solver.answerY[vertex]
                 << '\n';
        }
    }

    return 0;
}

Pregunta

Problem - 1578C - Codeforces

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Pensamiento

Respuesta

思路

1. 梯子中的环

2. 两种扫描状态

单轨状态 need(p -> v)

双轨状态 pair(p -> v, q -> w)

3. 向后部分为什么必须是纯路径

4. 选择中心竖边

中心是一条桥

中心是环边

正确性要点

复杂度

C++17

Compartir este Q&A

单轨状态 `need(p -> v)`

双轨状态 `pair(p -> v, q -> w)`