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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.ByteArrayOutputStream;
import java.util.Collection;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Queue;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    G solver = new G();
    solver.solve(1, in, out);
    out.close();
  }

  static class G extends SimpleSavingChelperSolution {
    private List<List<Integer>> directedEdges;
    private List<List<Integer>> undirectedEdgeIds;
    private int[][] undirectedEdges;
    private int n;
    private int m;
    private int s;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      wrapSolve(testNumber, in, out);
    }


    public void solve(int testNumber) {
      n = in.nextInt();
      m = in.nextInt();
      s = in.nextInt() - 1;

      directedEdges = new ArrayList<>();
      undirectedEdgeIds = new ArrayList<>();

      int M = 0;
      undirectedEdges = new int[m][2];

      for (int i = 0; i < n; i++) {
        directedEdges.add(new ArrayList<>());
        undirectedEdgeIds.add(new ArrayList<>());
      }

      for (int i = 0; i < m; i++) {
        int t = in.nextInt();
        int a = in.nextInt() - 1;
        int b = in.nextInt() - 1;

        if (t == 1) { // directed
          directedEdges.get(a).add(b);
        } else {
          undirectedEdges[M][0] = a;
          undirectedEdges[M][1] = b;

          undirectedEdgeIds.get(a).add(M);
          undirectedEdgeIds.get(b).add(M);

          M++;
        }
      }

      boolean[] maxDirs = new boolean[M];
      int maxCount = bfs(maxDirs, true);
      out.println(maxCount);
      for (int i = 0; i < M; i++) {
        out.print(maxDirs[i] ? '+' : '-');
      }
      out.println();

      boolean[] minDirs = new boolean[M];
      int minCount = bfs(minDirs, false);
      out.println(minCount);
      for (int i = 0; i < M; i++) {
        out.print(minDirs[i] ? '+' : '-');
      }
      out.println();
    }

    int bfs(boolean[] dirs, boolean invade) {
      Queue<Integer> queue = new LinkedList<>();
      queue.add(s);

      boolean[] visited = new boolean[n];
      visited[s] = true;

      int count = 1;

      while (!queue.isEmpty()) {
        int v = queue.poll();

        for (int i : undirectedEdgeIds.get(v)) {
          int u = undirectedEdges[i][0] == v ? undirectedEdges[i][1] : undirectedEdges[i][0];

          if (!invade) {
            dirs[i] = undirectedEdges[i][0] != v;
            continue;
          }

          if (!visited[u]) {
            dirs[i] = undirectedEdges[i][0] == v;
            visited[u] = true;
            queue.add(u);
            count++;
          }
        }

        for (int u : directedEdges.get(v)) {
          if (!visited[u]) {
            visited[u] = true;
            queue.add(u);
            count++;
          }
        }
      }
      return count;
    }

  }

  static abstract class SimpleSavingChelperSolution extends SavingChelperSolution {

    public String processOutputPreCheck(int testNumber, String output) {
      return output;
    }


    public String processOutputPostCheck(int testNumber, String output) {
      return output;
    }

  }

  static abstract class SavingChelperSolution {
    protected int testNumber;
    public InputReader in;
    public OutputWriter out;
    private OutputWriter toFile;
    private boolean local = new File("chelper.properties").exists();
    public OutputWriter debug;

    {
      if (local) {
        debug = new OutputWriter(System.out);
      } else {
        debug = new OutputWriter(new OutputStream() {

          public void write(int b) {
          }
        });
      }
    }

    public SavingChelperSolution() {
      try {
        toFile = new OutputWriter("last_test_output.txt");
      } catch (FileNotFoundException e) {
        throw new RuntimeException(e);
      }
    }

    public abstract void solve(int testNumber);

    public abstract String processOutputPreCheck(int testNumber, String output);

    public abstract String processOutputPostCheck(int testNumber, String output);

    public void wrapSolve(int testNumber, InputReader in, OutputWriter out) {
      this.testNumber = testNumber;

      ByteArrayOutputStream substituteOutContents = new ByteArrayOutputStream();
      OutputWriter substituteOut = new OutputWriter(substituteOutContents);

      this.in = in;
      this.out = substituteOut;

      solve(testNumber);
      substituteOut.flush();

      String result = substituteOutContents.toString();

      result = processOutputPreCheck(testNumber, result);
      out.print(result);
      out.flush();

      if (local) {
        debug.flush();

        result = processOutputPostCheck(testNumber, result);
        toFile.print(result);
        toFile.flush();
      }
    }

  }

  static class InputReader {
    private BufferedReader br;
    private StringTokenizer in;

    public InputReader(String fileName) {
      try {
        br = new BufferedReader(new FileReader(fileName));
      } catch (IOException e) {
        throw new RuntimeException(e);
      }
    }

    public InputReader(InputStream inputStream) {
      br = new BufferedReader(new InputStreamReader(inputStream));
    }

    private boolean hasMoreTokens() {
      while (in == null || !in.hasMoreTokens()) {
        String s = nextLine();
        if (s == null) {
          return false;
        }
        in = new StringTokenizer(s);
      }
      return true;
    }

    public String nextString() {
      return hasMoreTokens() ? in.nextToken() : null;
    }

    public String nextLine() {
      try {
        in = null;
        return br.readLine();
      } catch (Exception e) {
        e.printStackTrace();
        return null;
      }
    }

    public int nextInt() {
      return Integer.parseInt(nextString());
    }

  }

  static class OutputWriter extends PrintWriter {

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

    public OutputWriter(String fileName) throws FileNotFoundException {
      super(fileName);
    }

    public OutputWriter(OutputStream outputStream) {
      super(outputStream);
    }

    public OutputWriter(Writer writer) {
      super(writer);
    }

  }
}