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

101. Domino

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The blocks usually are called bones, dominoes, or pieces and sometimes men, stones, or even cards.
The face of each piece is divided, by a line or ridge, into two squares, each of which is marked as would be a pair of dice...

The principle in nearly all modern dominoes games is to match one end of a piece to another that is identically or reciprocally numbered.

ENCYCLOPÆDIA BRITANNICA


Given a set of domino pieces where each side is marked with two digits from 0 to 6. Your task is to arrange pieces in a line such way, that they touch through equal marked sides. It is possible to rotate pieces changing left and right side.


Input

The first line of the input contains a single integer N (1 ≤ N ≤ 100) representing the total number of pieces in the domino set. The following N lines describe pieces. Each piece is represented on a separate line in a form of two digits from 0 to 6 separated by a space.


Output

Write “No solution” if it is impossible to arrange them described way. If it is possible, write any of way. Pieces must be written in left-to-right order. Every of N lines must contains number of current domino piece and sign “+” or “-“ (first means that you not rotate that piece, and second if you rotate it).


Sample Input

5
1 2
2 4
2 4
6 4
2 1
Sample Output

2 -
5 +
1 +
3 +
4 -

<|response|>
1. Abridged Problem Statement
Given N domino pieces, each with two numbers (0–6). You may flip a piece, swapping its ends. Arrange all pieces in a single chain so that adjacent numbers match. If possible, output one valid ordering: for each piece, print its 1-based index and “+” if kept as given or “-” if flipped. If impossible, print “No solution”.

2. Key Observations
- Model each number 0–6 as a vertex, each domino as an undirected edge between its two numbers.
- A valid chain using every domino exactly once corresponds to an Eulerian trail (or circuit) in this multigraph.
- An undirected graph has an Eulerian trail if and only if it is connected (ignoring isolated vertices) and has exactly 0 or 2 vertices of odd degree.
  • 0 odd-degree vertices ⇒ Eulerian circuit (starts and ends at same vertex)
  • 2 odd-degree vertices ⇒ Eulerian trail (starts at one odd vertex, ends at the other)
- We can use Hierholzer’s algorithm to construct the trail/circuit in O(N) time for N dominoes.
- To handle the “0 odd” and “2 odd” cases uniformly, we can pair up the two odd vertices with one “fake” edge, making all degrees even, find an Eulerian circuit, and then remove the fake edge to recover the single required trail.

3. Full Solution Approach
1. Read N and the list of dominos (pairs u,v).
2. Build a graph with vertices 0…6. For each domino i:
   - Create two half-edges with IDs 2*i and 2*i+1.
   - Add (v, 2*i) to adj[u] and (u, 2*i+1) to adj[v].
   - Track degrees deg[u]++, deg[v]++.
3. Collect all vertices of odd degree.
4. Pair odd vertices and add one fake edge per pair; this makes all degrees even, so an Eulerian circuit exists.
5. Prepare for Hierholzer’s algorithm:
   - used[e] = false for each original or fake edge index e.
   - ptr[u] = 0 for each vertex to track which adjacency entry to explore next.
6. For each vertex u with adj[u] nonempty, run a DFS traversal:
   - While ptr[u] < adj[u].size():
     • Let (v, heid) = adj[u][ptr[u]++].
     • Let eidx = heid >> 1. If used[eidx] is false:
       – Mark used[eidx]=true.
       – Recurse on v, then append heid to the current path.
   - Each call generates one cycle (in reverse).
7. For each found cycle, rotate it so that if there is any fake half-edge in it, it appears first.
   - Then split the cycle at fake half-edges into maximal sub-sequences of real half-edges. Collect these trails.
8. If exactly one trail is produced, it covers all dominoes and is our solution. Otherwise, print “No solution”.
9. To output the solution trail: for each half-edge ID heid in order:
   - Let idx = (heid >> 1) + 1 be the domino’s 1-based index.
   - Determine orientation: compare the oriented edge to the stored input pair to decide “+” or “−”.
10. Print lines “idx +” or “idx −” in the chain order.

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;
};

class EulerianPaths {
  private:
    int n, m;
    vector<vector<pair<int, int>>> adj;
    vector<pair<int, int>> edges;
    vector<int> deg;

    void dfs(int u, vector<int>& path, vector<bool>& used, vector<int>& po) {
        for(; po[u] < (int)adj[u].size();) {
            int idx = po[u]++;
            if(!used[adj[u][idx].second >> 1]) {
                used[adj[u][idx].second >> 1] = true;
                dfs(adj[u][idx].first, path, used, po);
                path.push_back(adj[u][idx].second);
            }
        }
    }

  public:
    EulerianPaths(int _n) : n(_n), m(0) {
        adj.assign(n + 1, {});
        deg.assign(n + 1, 0);
    }

    void add_edge(int u, int v) {
        adj[u].push_back({v, m * 2});
        adj[v].push_back({u, m * 2 + 1});
        edges.push_back({u, v});
        deg[u]++;
        deg[v]++;
        m++;
    }

    vector<vector<int>> find_paths() {
        vector<bool> used(m, false);
        vector<int> po(n + 1, 0);

        vector<int> odd_vertices;
        for(int i = 0; i <= n; i++) {
            if(deg[i] % 2 == 1) {
                odd_vertices.push_back(i);
            }
        }

        int total_edges = m;
        for(int i = 0; i < (int)odd_vertices.size() / 2; i++) {
            int u = odd_vertices[2 * i], v = odd_vertices[2 * i + 1];
            adj[u].push_back({v, 2 * total_edges});
            adj[v].push_back({u, 2 * total_edges + 1});
            total_edges++;
            used.push_back(false);
            edges.push_back({u, v});
        }

        vector<vector<int>> paths;
        for(int u = 0; u <= n; u++) {
            if(!adj[u].empty()) {
                vector<int> path;
                dfs(u, path, used, po);
                if(!path.empty()) {
                    // Rotate the path so that we always start with a fake edge
                    // if there is at least one.
                    auto it = find_if(path.begin(), path.end(), [&](int x) {
                        return x >= 2 * m;
                    });
                    if(it != path.end()) {
                        rotate(path.begin(), it, path.end());
                    }

                    vector<int> current_path;
                    for(int x: path) {
                        if(x < 2 * m) {
                            current_path.push_back(x);
                        } else if(!current_path.empty()) {
                            paths.push_back(current_path);
                            current_path.clear();
                        }
                    }
                    if(!current_path.empty()) {
                        paths.push_back(current_path);
                    }
                }
            }
        }

        return paths;
    }

    pair<int, int> get_edge(int edge_i) {
        if(edge_i & 1) {
            return edges[edge_i >> 1];
        } else {
            return {edges[edge_i >> 1].second, edges[edge_i >> 1].first};
        }
    }

    vector<pair<int, int>> get_path_edges(const vector<int>& path) {
        vector<pair<int, int>> result;
        for(int edge_i: path) {
            result.push_back(get_edge(edge_i));
        }
        return result;
    }
};

int m;
vector<pair<int, int>> dominos;

void read() {
    cin >> m;
    dominos.resize(m);
    cin >> dominos;
}

void solve() {
    // - Model the domino set as a multigraph on vertices 0..6 (the pip
    //   values), where each domino (a, b) is an undirected edge a-b. Arranging
    //   all dominoes in a chain that matches touching halves is exactly an
    //   Eulerian path that uses every edge once.
    //
    // - EulerianPaths pairs up odd-degree vertices with extra fake edges so an
    //   Eulerian circuit always exists, runs Hierholzer's algorithm, then cuts
    //   the circuit at the fake edges to recover the real path segments. A
    //   single segment covering all dominoes means a valid line exists;
    //   otherwise there is no solution.
    //
    // - For each used edge we print its 1-based domino index and a sign: '+'
    //   if traversed in the stored orientation, '-' if reversed.

    EulerianPaths ep(6);
    for(int i = 0; i < m; i++) {
        ep.add_edge(dominos[i].first, dominos[i].second);
    }

    auto paths = ep.find_paths();
    if(paths.size() == 1) {
        for(int edge_i: paths[0]) {
            cout << (edge_i >> 1) + 1 << ' '
                 << (ep.get_edge(edge_i) == dominos[edge_i >> 1] ? '+' : '-')
                 << '\n';
        }
    } else {
        cout << "No solution\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 with Detailed Comments
```python
import sys
sys.setrecursionlimit(10**7)

def read_input():
    N = int(sys.stdin.readline())
    dominos = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    return N, dominos

class Eulerian:
    def __init__(self, max_vertex):
        self.V = max_vertex        # vertices numbered 0..max_vertex
        self.adj = [[] for _ in range(self.V+1)]
        self.deg = [0]*(self.V+1)
        self.edges = []            # list of (u,v) for each edge
        self.M = 0                 # number of real domino edges

    def add_edge(self, u, v):
        """
        Add an undirected edge by creating two half-edge IDs:
          2*M and 2*M+1 for the M-th edge.
        """
        he1, he2 = 2*self.M, 2*self.M+1
        self.adj[u].append((v, he1))
        self.adj[v].append((u, he2))
        self.edges.append((u, v))
        self.deg[u] += 1
        self.deg[v] += 1
        self.M += 1

    def find_trail(self):
        # 1) Collect odd-degree vertices
        odd = [u for u in range(self.V+1) if self.deg[u] % 2 == 1]
        if len(odd) > 2:
            return None

        # 2) Prepare used flags for original edges
        used = [False]*self.M
        total_edges = self.M

        # 3) If exactly 2 odd vertices, add one fake edge between them
        if len(odd) == 2:
            u, v = odd
            he1, he2 = 2*total_edges, 2*total_edges+1
            self.adj[u].append((v, he1))
            self.adj[v].append((u, he2))
            self.edges.append((u, v))
            used.append(False)
            total_edges += 1

        # 4) Hierholzer setup
        ptr = [0]*(self.V+1)
        trail_seq = []

        def dfs(u):
            while ptr[u] < len(self.adj[u]):
                v, heid = self.adj[u][ptr[u]]
                ptr[u] += 1
                eidx = heid >> 1
                if not used[eidx]:
                    used[eidx] = True
                    dfs(v)
                    trail_seq.append(heid)

        # 5) Run DFS from any vertex with edges
        for u in range(self.V+1):
            if ptr[u] < len(self.adj[u]):
                dfs(u)
        if not trail_seq:
            return None

        # 6) Rotate so fake edge (if any) is first
        fake_start = 2*self.M
        for i, he in enumerate(trail_seq):
            if he >= fake_start:
                trail_seq = trail_seq[i:] + trail_seq[:i]
                break

        # 7) Split at fake edges into one or more trails of real edges
        result = []
        cur = []
        for he in trail_seq:
            if he < 2*self.M:
                cur.append(he)
            else:
                if cur:
                    result.append(cur)
                    cur = []
        if cur:
            result.append(cur)

        # 8) Check we have exactly one trail of length M
        if len(result) == 1 and len(result[0]) == self.M:
            return result[0]
        else:
            return None

    def oriented(self, heid):
        """
        Given half-edge ID, return the oriented (u,v).
        If heid is even: u->v as stored; if odd: v->u.
        """
        idx = heid >> 1
        u, v = self.edges[idx]
        if heid & 1:
            return (v, u)
        else:
            return (u, v)

def main():
    N, dominos = read_input()
    solver = Eulerian(6)
    for u, v in dominos:
        solver.add_edge(u, v)

    trail = solver.find_trail()
    if trail is None:
        print("No solution")
        return

    # Output each domino index and orientation
    for heid in trail:
        idx = (heid >> 1) + 1
        u, v = solver.oriented(heid)
        # If (u,v) matches the input, it's '+', else '-'
        if (u, v) == dominos[heid>>1]:
            print(idx, '+')
        else:
            print(idx, '-')

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

Explanation Highlights:
- We transform the domino arrangement problem into finding an Eulerian trail.
- We allow fake edges to turn the odd-degree case into an all-even case, find a circuit, and then remove the fake edges.
- Hierholzer’s algorithm efficiently constructs the trail in linear time O(N).
- Tracking half-edge IDs lets us recover both the order of dominos and their required orientation (‘+’ or ‘−’).
