Problem: Vasya has a graph containing both directed (oriented) and undirected (non-oriented) edges. There can be multiple edges between a pair of vertices.

Vasya has picked a vertex s from the graph. Now Vasya wants to create two separate plans:

  1. to orient each undirected edge in one of two possible directions to maximize number of vertices reachable from vertex s; 
  2. to orient each undirected edge in one of two possible directions to minimize number of vertices reachable from vertex s. 



In each of two plans each undirected edge must become directed. For an edge chosen directions can differ in two plans.

Help Vasya find the plans.

Input

The first line contains three integers n, m and s (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105, 1 ≤ s ≤ n) — number of vertices and edges in the graph, and the vertex Vasya has picked.

The following m lines contain information about the graph edges. Each line contains three integers ti, ui and vi (1 ≤ ti ≤ 2, 1 ≤ ui, vi ≤ n, ui ≠ vi) — edge type and vertices connected by the edge. If ti = 1 then the edge is directed and goes from the vertex ui to the vertex vi. If ti = 2 then the edge is undirected and it connects the vertices ui and vi.

It is guaranteed that there is at least one undirected edge in the graph.

Output

The first two lines should describe the plan which maximizes the number of reachable vertices. The lines three and four should describe the plan which minimizes the number of reachable vertices.

A description of each plan should start with a line containing the number of reachable vertices. The second line of a plan should consist of f symbols '+' and '-', where f is the number of undirected edges in the initial graph. Print '+' as the j-th symbol of the string if the j-th undirected edge (u, v) from the input should be oriented from u to v. Print '-' to signify the opposite direction (from v to u). Consider undirected edges to be numbered in the same order they are given in the input.

If there are multiple solutions, print any of them.

Examples

Input

2 2 1
1 1 2
2 2 1


Output

2
-
2
+


Input

6 6 3
2 2 6
1 4 5
2 3 4
1 4 1
1 3 1
2 2 3


Output

6
++-
2
+-+

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;

public class Main {
    private static FastReader sc = new FastReader(System.in);
    private static OutputWriter out = new OutputWriter(System.out);
    private static HashMap<Integer, ArrayList<Edge>> unGraph = new HashMap<>();
    private static HashMap<Integer, ArrayList<Integer>> diGraph = new HashMap<>();
    private static int source, n;
    private static boolean[] disc;
    private static ArrayList<Edge> undiEdges = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        n = sc.nextInt();
        int m = sc.nextInt();
        source = sc.nextInt() - 1;
        for (int i = 0; i < n; i++) {
            unGraph.put(i, new ArrayList<>());
            diGraph.put(i, new ArrayList<>());
        }

        int idx = 0;
        for (int i = 0; i < m; i++) {
            int type = sc.nextInt();
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            if (type == 1) diGraph.get(u).add(v);
            else {
                undiEdges.add(new Edge(u, v, idx));
                unGraph.get(u).add(new Edge(u, v, idx));
                unGraph.get(v).add(new Edge(v, u, idx));
                idx++;
            }
        }
        discovered();
        maximise();
        minimise();
        out.close();

    }

    private static void maximise() {
        Queue<Integer> q = new LinkedList<>();
        boolean[] marked = new boolean[n];
        q.add(source);
        marked[source] = true;
        char[] orient = new char[undiEdges.size()];
        Arrays.fill(orient, '*');
        while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : diGraph.get(u)) {
                if (!marked[v]) {
                    marked[v] = true;
                    q.add(v);
                }
            }

            for (Edge e : unGraph.get(u)) {
                if (orient[e.idx] != '*') continue;
                if (e.v == undiEdges.get(e.idx).v) orient[e.idx] = '+';
                else orient[e.idx] = '-';
                if (!marked[e.v]) {
                    marked[e.v] = true;
                    q.add(e.v);
                }
            }
        }

        int ans = 0;
        for (boolean b : marked) if (b) ans++;
        out.printLine(ans);
        for (char ch : orient) {
            if (ch != '*') out.print(ch);
            else out.print('+');
        }
        out.printLine();
    }

    private static void minimise() {
        int ans = 0;
        for (boolean b : disc) if (b) ans++;
        out.printLine(ans);
        for (Edge e : undiEdges) {
            if (disc[e.u] && disc[e.v]) out.print('+');
            else if (!disc[e.u] && !disc[e.v]) out.print('+');
            else if (disc[e.u] && !disc[e.v]) out.print('-');
            else out.print('+');
        }
        out.printLine();
    }

    private static void discovered() {
        disc = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(source);
        disc[source] = true;
        while (!q.isEmpty()) {
            int u = q.remove();
            for (int v : diGraph.get(u)) {
                if (!disc[v]) {
                    disc[v] = true;
                    q.add(v);
                }
            }
        }
    }
}

class Edge {
    int u, v, idx;

    public Edge(int u, int v, int i) {
        this.u = u;
        this.v = v;
        this.idx = i;
    }

    public String toString() {
        return u + " " + v + " " + idx;
    }
}

class FastReader {
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }

        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1) {
            return -1;
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c == ',') {
                c = read();
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public boolean isSpaceChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuilder buf = new StringBuilder();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r') {
                buf.appendCodePoint(c);
            }
            c = read();
        }
        return buf.toString();
    }

    public String nextLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String nextLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines) {
            return nextLine();
        } else {
            return readLine0();
        }
    }

    public BigInteger nextBigInteger() {
        try {
            return new BigInteger(nextString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char nextCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, nextInt());
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return nextString();
    }

    public SpaceCharFilter getFilter() {
        return filter;
    }

    public void setFilter(SpaceCharFilter filter) {
        this.filter = filter;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

    public void flush() {
        writer.flush();
    }

}