Preparando MOJI
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.
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$$$.
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$$$).
5 4 3 1 2 2 3 3 4 8 7 1 2 3 2 2 4 4 5 4 6 6 7 6 8 5 4 1 2 1 3 1 4 1 5 8 9 1 2 2 3 3 4 1 4 4 5 5 6 6 7 7 8 5 8 10 10 1 2 2 3 3 4 4 5 5 6 6 1 3 7 4 8 1 9 6 10
Yes 0 0 0 1 1 1 1 2 Yes 0 3 1 3 1 4 1 2 0 2 1 1 0 1 1 0 No Yes 0 0 1 0 1 1 0 1 0 2 0 3 1 3 1 2 Yes 1 1 1 2 1 3 0 3 0 2 0 1 1 4 0 4 1 0 0 0
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.
Informação
Provedor Codeforces
Código CF1578C
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:18:02
Relacionados