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 –

翻译：

给你一些多米诺骨牌，然后骨牌的两面均有一个数字，数字的范围是0~6，每个骨牌都可以翻转，然后让你排一个序列，这个序列必须保证前一个骨牌的背面的数字和后一个骨牌的前面的数字相同，然后按你所排的序列输出，先输出骨牌的序号，如果这个牌的状态和原来不一样，就输出一个’-‘，否则就输出’+’， 如果无解，那就输出’No solution’。

题解：

对于这个题，很显然这是一个一笔画的问题。
我们发现题目的意思可以理解为，找到一条路径使得恰好经过所有多米诺骨牌一次，于是乎想到了哈密顿路径，可是哈密顿路径的复杂度是O(n^2)的，显然对于这道只有0.25s的题目来说不可能。
我们换一种思路，因为数字只有7种，我们把数字作为点，骨牌作为连接两面数字的边，于是就得到了一张7个点，100条边的图，然后问题成了，找到一条路径，使得每条边恰好经过一次，这便转化成了欧拉回路的问题。

样例解释：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int n, s;
int fst[233], nxt[233], d[233], tot = 0, sum = 0;
int du[10];
bool used[233];
struct qer
{
    int f, t, d;
}es[233];
queue <int> q;
void build(int f, int t, int d)
{
    es[++tot] = (qer){f, t, d};
    nxt[tot] = fst[f];
    fst[f] = tot;
}
void dfs(int u)
{
    for (int i = fst[u]; i; i = nxt[i])
    {
        int v = es[i].t;
        if (!used[abs(es[i].d)])
        {
            used[abs(es[i].d)] = 1;
            dfs(v);
            d[++sum] = es[i].d;
        }
    }
}
bool check()
{
    int ls = 0;
    for (int i = 0; i <= 6; i++)
        if (du[i]&1)
            ls++, s = i;
    if (ls == 1 || ls > 2)
        return 0;
    if (ls == 2)
        return 1;
    for (int i = 0; i <= 6; i++)
        if (du[i] > 0)
        {
            s = i;
            break;
        }
    return 1;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int f, t;
        scanf("%d%d", &f, &t);
        build(f, t, i);
        build(t, f, -i);
        du[f]++;
        du[t]++;
    }
    if (!check())
    {
        puts("No solution");
        return 0;
    }
    dfs(s);
    for (int i = 1; i <= n; i++)
    {
        if (!used[i])
        {
            puts("No solution");
            return 0;
        }
    }
    for (int i = sum; i >= 1; i--)
        if (d[i] > 0)
            cout << d[i] << " +" << endl;
        else
            cout << -d[i] << " -" << endl;
    return 0;
}