<|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.

487. Courier's Route
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



There are N towns in a kingdom, numbered from 1 to N, with the capital having the number 1. Each town is enclosed in a city wall with 4 gates. The gates are also numbered, with the gates of the city i (1 ≤ i ≤ N) numbered 4· i-3, 4· i-2, 4· i-1, 4· i. At each gate is exactly one road that leads to some gate of another town (note that there may be more than one road between two towns). All the roads can be travelled in both directions. Due to a system of bridges and tunnels, the roads do not intersect outside the towns.

A royal courier has to post copies of an Important Royal Decree on the outer sides of all gates of all towns. The courier can freely move from one gate to another in any town, but outside of towns, he's allowed to travel only along the roads. The courier starts from the capital and has to return to the capital after completing the assignment.

Is it possible for the courier to do this, passing each gate exactly once? Exiting a town through a gate only to post the decree on the outer side of the gate and immediately returning to the town counts as passing the gate once.

Input
The first line of the input file contains N (2 ≤ N ≤ 1000). Each of the following 2· N lines describes one road and contains two integers, separated by a space: the numbers of the two gates connected by the road.

Output
The first line of the output file should contain the word "Yes" or "No" (without the quotes) depending on whether the courier's assignment can be completed while passing each gate exactly once. In case it is possible, the second line of the file should contain 4· N integers, separated by spaces: the numbers of the gates in the order the courier passes them. If there are several solutions, output any one of them.

Example(s)
sample input
sample output
4
1 9
2 10
3 13
4 8
5 11
6 14
7 16
15 12
Yes
1 3 13 14 16 15 12 9 10 11 5 6 7 8 4 2

<|response|>
## 1. Abridged Problem Statement

There are `N` towns, each with exactly `4` gates, so there are `4N` gates total.

Each gate is connected by exactly one bidirectional road to a gate of another town. The courier may move freely between gates inside the same town, but outside towns he can only move along roads.

The courier starts in the capital town `1`, must pass every gate exactly once, and must return to the capital.

We need to decide whether such a route exists. If it exists, output `"Yes"` and one valid order of the `4N` gates passed by the courier. Otherwise output `"No"`.

---

## 2. Key Observations

### Observation 1: Roads form a perfect matching on gates

Every gate has exactly one outside road. Therefore, if we treat gates as vertices, the roads pair up all `4N` gates into `2N` fixed edges.

Let:

```text
road[g] = the gate connected to gate g by the outside road
```

---

### Observation 2: Inside each town, we only need to decide pairs of gates

Inside a town, the courier can move freely from any gate to any other gate.

Since each gate must be passed exactly once, inside every town the route must connect its `4` gates into two internal transitions, i.e. a perfect matching of the four gates.

For example, for gates:

```text
a b c d
```

we may choose internal pairs:

```text
(a, b), (c, d)
```

or

```text
(a, c), (b, d)
```

or

```text
(a, d), (b, c)
```

Let:

```text
mate[g] = the gate paired with g inside the same town
```

---

### Observation 3: Roads + internal pairings create cycles

Every gate has exactly two incident edges in the constructed route graph:

1. its fixed outside road edge,
2. its chosen internal edge.

Therefore every gate has degree `2`.

A finite graph where every vertex has degree `2` is a disjoint union of cycles.

So our goal is:

> Choose the internal pairings so that all gates belong to one single cycle.

That single cycle is exactly the courier's route.

---

### Observation 4: We can merge cycles by changing pairings inside one town

Start with any internal pairing, for example in every town:

```text
(4i - 3, 4i - 2)
(4i - 1, 4i)
```

This creates some number of cycles.

Consider the cycle containing gate `1`, called the capital cycle.

If there is a town with exactly two gates in the capital cycle, then:

- those two gates form one internal pair,
- the other two gates form another internal pair in some other cycle.

Suppose the gates are:

```text
capital cycle gates: x1, x2
other cycle gates:   y1, y2
```

Currently the internal pairs are:

```text
x1 -- x2
y1 -- y2
```

We can replace them by:

```text
x1 -- y1
x2 -- y2
```

This splices the two cycles into one larger cycle.

So each such operation reduces the number of cycles by one.

---

### Observation 5: If no such town exists, the answer is impossible

If there are multiple cycles, but no town has exactly two gates in the capital cycle, then every town has either:

- all `4` gates in the capital cycle, or
- no gates in the capital cycle.

Also, there cannot be a road from a capital-cycle town to an outside town, because a road edge would put both endpoints in the same cycle.

So the capital part is disconnected from the rest of the kingdom. The courier cannot visit all gates and return.

Therefore the answer is `"No"`.

---

## 3. Full Solution Approach

### Step 1: Read the road matching

There are `4N` gates and `2N` roads.

Store the road partner of every gate:

```cpp
road[a] = b;
road[b] = a;
```

---

### Step 2: Initialize arbitrary internal pairings

For every town, initially pair its gates as:

```text
(4i - 3, 4i - 2)
(4i - 1, 4i)
```

Using zero-based town index `town`, with:

```text
base = 4 * town + 1
```

the gates are:

```text
base, base + 1, base + 2, base + 3
```

and we set:

```text
base     <-> base + 1
base + 2 <-> base + 3
```

---

### Step 3: Label current cycles

Using `road[]` and `mate[]`, every gate has degree `2`.

To label cycles, start from every unvisited gate and walk through the graph. At each gate, there are exactly two neighbors:

```text
road[cur]
mate[cur]
```

If we came from `prev`, the next gate is the neighbor that is not `prev`.

This gives the component or cycle number of every gate.

---

### Step 4: Repeatedly merge cycles into the capital cycle

After labeling cycles:

- If there is only one cycle, we are done.
- Otherwise, find a town with exactly two gates in the cycle containing gate `1`.

If such a town exists, re-pair its four gates across the two cycles, merging them.

If no such town exists, output `"No"`.

---

### Step 5: Output the final cycle

Once all gates belong to one cycle, traverse that cycle starting from gate `1` and output the order of visited gates.

The route contains exactly `4N` gates.

---

### Complexity

There are `4N` gates.

Each cycle-labeling pass costs `O(N)`.  
Each merge decreases the number of cycles by one, and there are at most `O(N)` cycles.

Total complexity:

```text
O(N^2)
```

For `N <= 1000`, this is easily fast enough.

---

## 4. C++ Implementation with Detailed Comments

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

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

    int n;
    cin >> n;

    // Total number of gates.
    int totalGates = 4 * n;

    // road[g] is the gate connected to g by the fixed outside road.
    // Gates are numbered from 1 to 4n, so index 0 is unused.
    vector<int> road(totalGates + 1, 0);

    // Read the 2n roads.
    for (int i = 0; i < 2 * n; i++) {
        int a, b;
        cin >> a >> b;

        road[a] = b;
        road[b] = a;
    }

    // mate[g] is the chosen internal partner of gate g inside its town.
    vector<int> mate(totalGates + 1, 0);

    // Initially pair gates in each town as:
    // (base, base + 1) and (base + 2, base + 3).
    for (int town = 0; town < n; town++) {
        int base = 4 * town + 1;

        mate[base] = base + 1;
        mate[base + 1] = base;

        mate[base + 2] = base + 3;
        mate[base + 3] = base + 2;
    }

    // comp[g] stores the current cycle/component number of gate g.
    vector<int> comp(totalGates + 1, -1);

    auto labelCycles = [&]() {
        // Reset component labels.
        fill(comp.begin(), comp.end(), -1);

        int cycleCount = 0;

        // Try to start a traversal from every unvisited gate.
        for (int start = 1; start <= totalGates; start++) {
            if (comp[start] != -1) {
                continue;
            }

            int cur = start;
            int prev = -1;

            // Since every vertex has degree 2, walking forward eventually
            // returns to the start and describes exactly one cycle.
            do {
                comp[cur] = cycleCount;

                // Current gate has two neighbors: road[cur] and mate[cur].
                // Continue to the neighbor that is not the previous gate.
                int nxt;
                if (road[cur] != prev) {
                    nxt = road[cur];
                } else {
                    nxt = mate[cur];
                }

                prev = cur;
                cur = nxt;

            } while (cur != start);

            cycleCount++;
        }

        return cycleCount;
    };

    // Repeatedly merge other cycles into the cycle containing gate 1.
    while (true) {
        int cycles = labelCycles();

        // If there is only one cycle, it gives a valid courier route.
        if (cycles == 1) {
            break;
        }

        // Component number of the cycle containing the capital gate 1.
        int capitalCycle = comp[1];

        // We need a town with exactly two gates in the capital cycle.
        int chosenBase = -1;

        for (int town = 0; town < n; town++) {
            int base = 4 * town + 1;

            int countInside = 0;
            for (int k = 0; k < 4; k++) {
                int gate = base + k;
                if (comp[gate] == capitalCycle) {
                    countInside++;
                }
            }

            if (countInside == 2) {
                chosenBase = base;
                break;
            }
        }

        // If no such town exists, the capital part is disconnected
        // from the rest, so no valid route is possible.
        if (chosenBase == -1) {
            cout << "No\n";
            return 0;
        }

        // Split the four gates of the chosen town into:
        // - gates inside the capital cycle,
        // - gates outside the capital cycle.
        vector<int> inside;
        vector<int> outside;

        for (int k = 0; k < 4; k++) {
            int gate = chosenBase + k;

            if (comp[gate] == capitalCycle) {
                inside.push_back(gate);
            } else {
                outside.push_back(gate);
            }
        }

        // There must be exactly two gates in each group.
        //
        // Before:
        //   inside[0] -- inside[1]
        //   outside[0] -- outside[1]
        //
        // After:
        //   inside[0] -- outside[0]
        //   inside[1] -- outside[1]
        //
        // This merges the two cycles into one.
        mate[inside[0]] = outside[0];
        mate[outside[0]] = inside[0];

        mate[inside[1]] = outside[1];
        mate[outside[1]] = inside[1];
    }

    // Now all gates are in one cycle. Traverse it to output the route.
    vector<int> answer;
    answer.reserve(totalGates);

    int cur = 1;
    int prev = -1;

    do {
        answer.push_back(cur);

        // Continue along the cycle.
        int nxt;
        if (road[cur] != prev) {
            nxt = road[cur];
        } else {
            nxt = mate[cur];
        }

        prev = cur;
        cur = nxt;

    } while (cur != 1);

    cout << "Yes\n";

    for (int i = 0; i < (int)answer.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n = data[0]

    # Total number of gates.
    total_gates = 4 * n

    # road[g] is the gate connected to g by the outside road.
    # Index 0 is unused.
    road = [0] * (total_gates + 1)

    idx = 1

    # Read the 2n roads.
    for _ in range(2 * n):
        a = data[idx]
        b = data[idx + 1]
        idx += 2

        road[a] = b
        road[b] = a

    # mate[g] is the internal partner of gate g inside its town.
    mate = [0] * (total_gates + 1)

    # Initial internal pairing:
    # For each town:
    #   (base, base + 1)
    #   (base + 2, base + 3)
    for town in range(n):
        base = 4 * town + 1

        mate[base] = base + 1
        mate[base + 1] = base

        mate[base + 2] = base + 3
        mate[base + 3] = base + 2

    # comp[g] stores the current cycle/component number of gate g.
    comp = [-1] * (total_gates + 1)

    def label_cycles():
        """
        Label all current cycles in the graph formed by road[] and mate[].

        Every gate has degree exactly 2:
        - one road edge,
        - one internal mate edge.

        Therefore the graph is a disjoint union of cycles.
        """

        # Reset labels.
        for i in range(total_gates + 1):
            comp[i] = -1

        cycle_count = 0

        # Start a traversal from every unvisited gate.
        for start in range(1, total_gates + 1):
            if comp[start] != -1:
                continue

            cur = start
            prev = 0

            while True:
                comp[cur] = cycle_count

                # The two neighbors are road[cur] and mate[cur].
                # Choose the one that is not the previous gate.
                if road[cur] != prev:
                    nxt = road[cur]
                else:
                    nxt = mate[cur]

                prev, cur = cur, nxt

                # We have completed this cycle.
                if cur == start:
                    break

            cycle_count += 1

        return cycle_count

    # Merge cycles until only one remains.
    while True:
        cycles = label_cycles()

        # A single cycle gives the required route.
        if cycles == 1:
            break

        # Cycle containing gate 1, the capital cycle.
        capital_cycle = comp[1]

        chosen_base = -1

        # Find a town with exactly two gates in the capital cycle.
        for town in range(n):
            base = 4 * town + 1

            count_inside = 0

            for k in range(4):
                gate = base + k
                if comp[gate] == capital_cycle:
                    count_inside += 1

            if count_inside == 2:
                chosen_base = base
                break

        # If no such town exists, the capital cycle is separated from
        # remaining cycles, so a full route is impossible.
        if chosen_base == -1:
            print("No")
            return

        inside = []
        outside = []

        # Split the chosen town's gates.
        for k in range(4):
            gate = chosen_base + k

            if comp[gate] == capital_cycle:
                inside.append(gate)
            else:
                outside.append(gate)

        # Re-pair the gates to merge two cycles.
        #
        # Before:
        #   inside[0] -- inside[1]
        #   outside[0] -- outside[1]
        #
        # After:
        #   inside[0] -- outside[0]
        #   inside[1] -- outside[1]
        mate[inside[0]] = outside[0]
        mate[outside[0]] = inside[0]

        mate[inside[1]] = outside[1]
        mate[outside[1]] = inside[1]

    # Now all gates belong to one cycle.
    # Traverse that cycle from gate 1.
    answer = []

    cur = 1
    prev = 0

    while True:
        answer.append(cur)

        if road[cur] != prev:
            nxt = road[cur]
        else:
            nxt = mate[cur]

        prev, cur = cur, nxt

        if cur == 1:
            break

    print("Yes")
    print(*answer)


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