Problem: You have a set of dominoes. Each domino is a rectangular tile with a line dividing its face into two square ends. Can you put all dominoes in a line one by one from left to right so that any two dominoes touched with the sides that had the same number of points? You can rotate the dominoes, changing the left and the right side (domino "1-4" turns into "4-1").

Input

The first line contains number n (1 ≤ n ≤ 100). Next n lines contains the dominoes. Each of these lines contains two numbers — the number of points (spots) on the left and the right half, correspondingly. The numbers of points (spots) are non-negative integers from 0 to 6.

Output

Print "No solution", if it is impossible to arrange the dominoes in the required manner. If the solution exists, then describe any way to arrange the dominoes. You put the dominoes from left to right. In each of n lines print the index of the domino to put in the corresponding position and then, after a space, character "+" (if you don't need to turn the domino) or "–" (if you need to turn it).

Examples

Input

5
1 2
2 4
2 4
6 4
2 1


Output

2 -
1 -
5 -
3 +
4 -

Solution (in JAVA):

Solution:
/**
 * Created by andywu on 7/28/14.
 */


import com.sun.java_cup.internal.runtime.virtual_parse_stack;

import java.util.*;
public class Solution {
    public static void main(String[] args){
        new Solution().solve();
    }

    class Edge{
        ArrayList<Integer> dIdx = new ArrayList<Integer>();
    }

    private void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Edge[][] g = new Edge[7][7];
        int nEdge = 0;
        int[][] edges = new int[n][2];
        for(int i = 0; i < n; ++i){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            edges[i][0] = a; edges[i][1] = b;
            if(g[a][b] == null){
                Edge e = new Edge();
                e.dIdx.add(i);
                g[a][b] = e;
                g[b][a] = e;
            }else{
                g[a][b].dIdx.add(i);
            }
            nEdge+=1;
        }
        int nodd = 0;
        int nv = 0;
        int start = -1;
        int odd = -1;
        for(int i = 0; i < 7; ++i){
            int d = 0;
            boolean ing = false;
            for(int j = 0; j < 7; j++){
                if (i != j)
                    d+=g[i][j] == null? 0 :g[i][j].dIdx.size();
                if(g[i][j]!= null && g[i][j].dIdx.size()>0){
                    start = i;
                    ing = true;
                }
            }
            if(ing) nv++;
            if(d%2==1) {
                nodd++;
                odd = i;
            }
        }
        if(nEdge == 1){
            System.out.println("1 +");
            return;
        }
        if(nodd != 2 && nodd != 0 && nv > 1){
            System.out.println("No solution");
            return;
        }
        if(nodd == 2) start = odd;
        if(start < 0) {
            System.out.println("No solution");
            return;
        }
        boolean[] visited = new boolean[7];
        dfs(start, g, visited);
        int nVi = 0;
        for(boolean v : visited){
            if(v) nVi++;
        }
        if(nVi < nv){
            System.out.println("No solution");
            return;
        }
        ArrayList<String> res = new ArrayList<String>();
        euler_path(start, g, res, edges, nEdge);
        if(res.size() < nEdge){
            System.out.println("No solution");
            return;
        }
        for(String r : res){
            System.out.println(r);
        }
    }

    private void dfs(int start, Edge[][] g, boolean[] visited) {
        if(visited[start] ) return;
        visited[start] = true;
        for(int j = 0; j < 7; j++){
            if(g[start][j] != null && g[start][j].dIdx.size() > 0){
                dfs(j, g, visited);
            }
        }
    }

    private void euler_path(int start, Edge[][] g, ArrayList<String> res, int[][] edges, int nEdge) {
        for(int j = 0; j < 7; j++){
            if(g[start][j] != null && g[start][j].dIdx.size() > 0){
                int edgeNum = g[start][j].dIdx.get(0)+1;
                String sign = edges[edgeNum-1][0] == start ? " +" : " -";
                res.add(String.valueOf(edgeNum) + sign);
                int backup = g[start][j].dIdx.get(0);
                g[start][j].dIdx.remove(0);
                euler_path(j, g, res,edges, nEdge);
                if(res.size() < nEdge){
                    g[start][j].dIdx.add(0, backup);
                    res.remove(res.size() - 1);
                }else{
                    return;
                }
            }
        }
    }

    /*class Node{
        int idx; int val;

        Node(int idx, int val) {
            this.idx = idx;
            this.val = val;
        }

        ArrayList<Integer> next;
    }
    private void solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] al = new Node[n*2];
        for(int i = 0; i < n; i++){
            Node left = new Node(2*i, scanner.nextInt());
            left.next = new ArrayList<Integer>();
            Node right = new Node(2*i+1, scanner.nextInt());
            right.next = new ArrayList<Integer>();
            //left.next.add(right.idx);right.next.add(left.idx);
            for(int j = 0; j < 2*i; j++){
                if(al[j].val == left.val){
                    al[j].next.add(left.idx);
                    left.next.add(j);
                }
                if(al[j].val == right.val){
                    al[j].next.add(right.idx);
                    right.next.add(j);
                }
            }
            al[2*i] = left; al[2*i+1] = right;
        }
        for(int i = 0; i < 2*n; i++){
            boolean[] visited = new boolean[2*n];
            found = false;
            dfs(i, -1, al, 0, 2*n, visited);
            if(found){
                break;
            }
        }
        if(!found){
            System.out.println("No solution");
        }
    }

    boolean found = false;

    private void dfs(int idx, int from, Node[] al, int depth, int target, boolean[] visited) {
        if(!visited[idx]){
            depth++;
            visited[idx] = true;
            if(depth == target){
                found = true;
            }else{
                if(from >= 0 && idx/2 == from/2){
                    for(int n : al[idx].next){
                        if(found) continue;
                        dfs(n, idx, al, depth, target, visited);
                    }
                }else{
                    dfs(idx%2 == 0? idx+1 : idx - 1, idx, al, depth, target, visited);
                }
            }
        }
        if(found){
            //System.out.println(al[idx].val);
            if(depth % 2 == 1){
                int pIdx = (idx / 2) + 1;
                if(idx % 2 == 1){
                    System.out.println(pIdx + " " + "+");
                }else{
                    System.out.println(pIdx + " " + "-");
                }
            }
        }else{
            visited[idx] = false;
        }
    }*/
}