<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

430. Unit-distance graph
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A graph is called unit-distance graph when it's possible to map its vertices to points on a plane in such a way that the distance between the points that correspond to vertices that are connected by an edge is exactly 1, and the distance between the points that correspond to vertices that are not connected by an edge is not equal to 1 (but still greater than 0).

Given a graph, find out whether it's a unit-distance graph, and if yes, output the corresponding points on the plane.

Input
The first line of the input file contains two integers n and m — the number of vertices and edges of the graph (1 ≤ n ≤ 7). The next m lines contain two distinct integers each, describing two vertices connected by an edge (the vertices are numbered starting from 0). Every two vertices can be connected by at most one edge.

Output
If the graph is unit-distance, print "Yes" (without quotes) on the first line of output file, otherwise print "No" (without quotes). In the former case, then print n lines, each containing two floating-point numbers not exceeding 100 by absolute value — the coordinates of the corresponding points in the order the vertices are numbered. Your solution will be considered correct if no two points are closer than 10-2, the distance between points corresponding to connected vertices differs from 1 by no more than 10-7, and the distance between two points corresponding to non-connected vertices differs from 1 by at least 10-2.

Example(s)
sample input
sample output
4 6
0 1
0 2
0 3
2 1
3 1
2 3
No

sample input
sample output
5 6
0 1
1 2
2 3
3 0
3 4
4 0
Yes
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0
-0.8660254037844386 0.5

<|response|>
## 1) Abridged problem statement

Given an undirected simple graph with 1 ≤ n ≤ 7, decide whether it can be drawn in the plane so that:

- For every edge (u,v), the Euclidean distance between points u and v is exactly 1 (tolerance 10^-7).
- For every non-edge (u,v), the distance is not equal to 1 and must differ from 1 by at least 10^-2.
- Any two vertices must be at least 10^-2 apart.
- Output coordinates (absolute value ≤ 100) if possible, otherwise output No.

---

## 2) Key observations

1. **Very small n (≤ 7)**. Only up to C(7,2) = 21 vertex pairs exist, so we can afford heavy constant-factor work: many iterations, random restarts, etc.

2. **Constraints are geometric equalities/inequalities**. Edge constraints are exact equalities d_uv = 1. Non-edges are "avoid a band" around 1: |d_uv - 1| ≥ 10^-2. This resembles a continuous feasibility problem.

3. **Convert feasibility into optimization ("energy minimization")**. Instead of solving with combinatorial geometry, we can search for coordinates minimizing a penalty function:
   - edges: penalize deviation from 1
   - non-edges: penalize only when too close to 1 (inside forbidden band)
   - distinctness: penalize if points get too close

4. **Use gradient descent + random restarts**. The penalty is non-convex, so a single run can get stuck. Random initialization and multiple restarts greatly increase success chance within the time limit.

---

## 3) Full solution approach

**Variables**: assign each vertex i planar coordinates (x_i, y_i). d_ij = sqrt((x_i-x_j)^2 + (y_i-y_j)^2).

**Penalty function** — three parts:

1. Edge penalty (always active): (d_ij - 1)^2.

2. Non-edge forbidden band (only if |d_ij - 1| < ε = 10^-2): pick nearest safe boundary T = 1 - ε if d_ij < 1, else T = 1 + ε. Add (d_ij - T)^2.

3. Distinctness (if d_ij < δ = 10^-2): add (d_ij - δ)^2.

**Gradient** for a term (d_ij - T)^2:

    ∇_{p_i} = 2(d_ij - T) * (p_i - p_j) / d_ij

Implementation: dx = x_i - x_j, dy = y_i - y_j, d = sqrt(dx^2 + dy^2) + 1e-12, g = 2(d - T)/d; add (g*dx, g*dy) to vertex i, subtract from j.

**Optimization loop**:
1. Randomly initialize all points in [-7, 7]^2.
2. Run gradient descent for 10,000 iterations with lr = 0.05, decayed by factor 0.999 each step.
3. Verify with strict tolerances: edge |d - 1| ≤ 10^-7, non-edge |d - 1| ≥ 10^-2, distinctness d ≥ 10^-2.
4. If valid, print Yes + coordinates. Repeat restarts until 0.6s elapsed; then print No.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const long double EPS_EDGE = 1e-7;
const long double EPS_NON_EDGE = 1e-2;
const long double EPS_DISTINCT = 1e-2;
const long double MAX_COORD = 7.0;
const long double TIME_LIMIT = 0.6;
const long double LR_START = 0.05;
const long double LR_DECAY = 0.999;
const int MAX_ITERS = 10000;

int n, m;
vector<pair<int, int>> edges;
vector<vector<bool>> adj;
vector<long double> x, y;

void read() {
    cin >> n >> m;
    adj.assign(n, vector<bool>(n, false));
    x.resize(n);
    y.resize(n);
    edges.clear();
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.emplace_back(u, v);
        adj[u][v] = adj[v][u] = true;
    }
}

bool verify_solution() {
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            long double dx = x[i] - x[j];
            long double dy = y[i] - y[j];
            long double d = sqrt(dx * dx + dy * dy);

            if(d < EPS_DISTINCT) {
                return false;
            }
            if(adj[i][j]) {
                if(fabsl(d - 1.0) > EPS_EDGE) {
                    return false;
                }
            } else {
                if(fabsl(d - 1.0) < EPS_NON_EDGE) {
                    return false;
                }
            }
        }
    }
    return true;
}

void solve() {
    // We can solve the unit-distance graph problem by formulating it as a
    // continuous optimization problem and applying gradient descent with random
    // restarts. For each vertex i (0 ≤ i < n), we assign two variables for the
    // coordinates (x_i, y_i). Let d_ij = sqrt((x_i - x_j)^2 + (y_i - y_j)^2)
    // be the Euclidean distance between vertices i and j. The we can minimize a
    // total energy E consisting of three parts:
    //
    //     1) Edge length constraints. For every edge (i, j), the distance must
    //        be exactly 1. We penalize squared deviation from 1:
    //            E_edge = sum_{(i,j) in edges} (d_ij - 1)^2
    //
    //     2) Non-edge forbidden band. For non-edges, the distance must NOT be
    //        close to 1. We introduce a forbidden band of width 1e-2 around 1.
    //        Only when a non-edge distance enters this band do we penalize it:
    //            For (i, j) not an edge:
    //                if |d_ij - 1| < 1e-2:
    //                    target = 1 - 1e-2           if d_ij < 1
    //                             1 + 1e-2           if d_ij > 1
    //                    E_nonedge += (d_ij - target)^2
    //
    //     3) All points must remain distinct. If two points get closer than
    //        1e-2, we push them apart:
    //
    //            E_distinct += max(0, 1e-2 - d_ij)^2
    //
    // The total energy is then:
    //     E = E_edge + E_nonedge + E_distinct
    //
    // Let's optimize this with gradient descent.
    // For the (d_ij - T)^2 terms, the gradient for point i is the below:
    //
    //     d/d(x_i, y_i) = 2 (d_ij - T) * ((x_i - x_j), (y_i - y_j)) / d_ij
    //
    // While for point j, we directly have the negative. This can be shown from:
    //
    //     d_ij = |p_i - p_j|
    //         and
    //     grad{p_i} d_ij = (p_i - p_j) / d_ij
    //
    // To optimize this, we might have to tune the learning rate a bit, and make
    // some restarts, but it's doable for the given constraints. We should note
    // that we have branching in this solution, so the initialization does
    // matter and the function isn't convex and we might end up in a state where
    // it's impossible to satisfy the (2) constraints. This lack of convexity is
    // why we end up making multiple restarts. Alternatively, we could have went
    // for a SGD-like approach of considering smaller batches instead of the
    // full loss.

    auto start = clock();
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_real_distribution<long double> init(-MAX_COORD, MAX_COORD);

    while((long double)(clock() - start) / CLOCKS_PER_SEC < TIME_LIMIT) {
        for(int i = 0; i < n; i++) {
            x[i] = init(rng);
            y[i] = init(rng);
        }

        long double lr = LR_START;
        for(int iter = 0; iter < MAX_ITERS; iter++) {
            vector<long double> gx(n, 0), gy(n, 0);

            for(int i = 0; i < n; i++) {
                for(int j = i + 1; j < n; j++) {
                    long double dx = x[i] - x[j];
                    long double dy = y[i] - y[j];
                    long double d = sqrt(dx * dx + dy * dy) + 1e-12;

                    if(adj[i][j]) {
                        long double diff = d - 1.0;
                        long double g = 2 * diff / d;
                        gx[i] += g * dx;
                        gy[i] += g * dy;
                        gx[j] -= g * dx;
                        gy[j] -= g * dy;
                    } else {
                        if(abs(d - 1.0) < EPS_NON_EDGE) {
                            long double target =
                                (d < 1.0 ? 1.0 - EPS_NON_EDGE
                                         : 1.0 + EPS_NON_EDGE);
                            long double diff = d - target;
                            long double g = 2 * diff / d;
                            gx[i] += g * dx;
                            gy[i] += g * dy;
                            gx[j] -= g * dx;
                            gy[j] -= g * dy;
                        }
                    }

                    if(d < EPS_DISTINCT) {
                        long double diff = d - EPS_DISTINCT;
                        long double g = 2 * diff / d;
                        gx[i] += g * dx;
                        gy[i] += g * dy;
                        gx[j] -= g * dx;
                        gy[j] -= g * dy;
                    }
                }
            }

            for(int i = 0; i < n; i++) {
                x[i] -= lr * gx[i];
                y[i] -= lr * gy[i];
            }

            lr *= LR_DECAY;
        }

        if(verify_solution()) {
            cout << "Yes\n";
            cout << fixed << setprecision(12);
            for(int i = 0; i < n; i++) {
                cout << x[i] << " " << y[i] << "\n";
            }
            return;
        }
    }

    cout << "No\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }
    return 0;
}
```

---

## 5) Python implementation

```python
import sys, time, math, random

EPS_EDGE = 1e-7
EPS_NON_EDGE = 1e-2
EPS_DISTINCT = 1e-2

MAX_COORD = 7.0
TIME_LIMIT = 0.6
LR_START = 0.05
LR_DECAY = 0.999
MAX_ITERS = 10000


def verify(n, adj, xs, ys):
    for i in range(n):
        for j in range(i + 1, n):
            dx = xs[i] - xs[j]
            dy = ys[i] - ys[j]
            d = math.hypot(dx, dy)

            if d < EPS_DISTINCT:
                return False

            if adj[i][j]:
                if abs(d - 1.0) > EPS_EDGE:
                    return False
            else:
                if abs(d - 1.0) < EPS_NON_EDGE:
                    return False

    return True


def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    adj = [[False] * n for _ in range(n)]
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        adj[u][v] = adj[v][u] = True

    xs = [0.0] * n
    ys = [0.0] * n

    start = time.perf_counter()

    while time.perf_counter() - start < TIME_LIMIT:
        for i in range(n):
            xs[i] = random.uniform(-MAX_COORD, MAX_COORD)
            ys[i] = random.uniform(-MAX_COORD, MAX_COORD)

        lr = LR_START

        for _ in range(MAX_ITERS):
            gx = [0.0] * n
            gy = [0.0] * n

            for i in range(n):
                xi, yi = xs[i], ys[i]
                for j in range(i + 1, n):
                    dx = xi - xs[j]
                    dy = yi - ys[j]
                    d = math.hypot(dx, dy) + 1e-12

                    if adj[i][j]:
                        diff = d - 1.0
                        g = 2.0 * diff / d
                        gx[i] += g * dx
                        gy[i] += g * dy
                        gx[j] -= g * dx
                        gy[j] -= g * dy

                    else:
                        if abs(d - 1.0) < EPS_NON_EDGE:
                            target = (1.0 - EPS_NON_EDGE) if d < 1.0 else (1.0 + EPS_NON_EDGE)
                            diff = d - target
                            g = 2.0 * diff / d
                            gx[i] += g * dx
                            gy[i] += g * dy
                            gx[j] -= g * dx
                            gy[j] -= g * dy

                    if d < EPS_DISTINCT:
                        diff = d - EPS_DISTINCT
                        g = 2.0 * diff / d
                        gx[i] += g * dx
                        gy[i] += g * dy
                        gx[j] -= g * dx
                        gy[j] -= g * dy

            for i in range(n):
                xs[i] -= lr * gx[i]
                ys[i] -= lr * gy[i]

            lr *= LR_DECAY

        if verify(n, adj, xs, ys):
            out = ["Yes"]
            for i in range(n):
                out.append(f"{xs[i]:.12f} {ys[i]:.12f}")
            sys.stdout.write("\n".join(out))
            return

    sys.stdout.write("No")


if __name__ == "__main__":
    solve()
```
