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.*;
public class G{

    static class Parser {
            final private int BUFFER_SIZE = 1 << 16;
            private DataInputStream din;
            private byte[] buffer;
            private int bufferPointer, bytesRead;

            public Parser(InputStream in) {
                din = new DataInputStream(in);
                buffer = new byte[BUFFER_SIZE];
                bufferPointer = bytesRead = 0;
            }

            public long nextLong() throws Exception {
                long ret = 0;
                byte c = read();
                while (c <= ' ') c = read();
                boolean neg = c == '-';
                if (neg) c = read();
                do {
                    ret = ret * 10 + c - '0';
                    c = read();
                } while (c > ' ');
                if (neg) return -ret;
                return ret;
            }

            //reads in the next string
            public String next() throws Exception {
                StringBuilder ret = new StringBuilder();
                byte c = read();
                while (c <= ' ') c = read();
                do {
                    ret = ret.append((char) c);
                    c = read();
                } while (c > ' ');
                return ret.toString();
            }

            public int nextInt() throws Exception {
                int ret = 0;
                byte c = read();
                while (c <= ' ') c = read();
                boolean neg = c == '-';
                if (neg) c = read();
                do {
                    ret = ret * 10 + c - '0';
                    c = read();
                } while (c > ' ');
                if (neg) return -ret;
                return ret;
            }

            private void fillBuffer() throws Exception {
                bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
                if (bytesRead == -1) buffer[0] = -1;
            }

            private byte read() throws Exception {
                if (bufferPointer == bytesRead) fillBuffer();
                return buffer[bufferPointer++];
            }
        }


    static class Print
    {
        private final BufferedWriter bw;
        public Print()
        {
            this.bw=new BufferedWriter(new OutputStreamWriter(System.out));
        }
        public void print(Object object)throws IOException
        {
            bw.append(""+object);
        }
        public void println(Object object)throws IOException
        {
            print(object);
            bw.append("\n");
        }
        public void close()throws IOException
        {
            bw.close();
        }
    }


    static long gcd(long a,long b){
        if(b==0)
            return a;
        return gcd(b,a%b);
    }

    static int ax[]={-1,-1,-1,0,0,1,1,1};
    static int ay[]={-1,0,1,-1,1,-1,0,1};


    static class Word{
        String s;
        int al[]=new int[26];
        Word(String s){
            this.s=s;
            for(int i=0;i<s.length();i++){
                char c=s.charAt(i);
                al[c-'a']=1;
            }
        }
    }


    static class Edge{
        int t,u,v;
        char c;
        Edge(int t,int u,int v){
            this.t=t;
            this.u=u;
            this.v=v;
        }
    }
    static int n,m,s;
    static Edge arr[];
    static HashMap<String,ArrayList<Integer>> adj_dir;
    static HashMap<String,ArrayList<Integer>> adj_u;
    static ArrayList<ArrayList<Integer>> adj;
    public static void main(String args[])throws Exception{
        //BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        //FastReader fr=new FastReader();
        Parser pr=new Parser(System.in);
        //PrintWriter out=new PrintWriter(System.out);
        Print out=new Print();
        n=pr.nextInt();
        m=pr.nextInt();
        s=pr.nextInt();

        arr=new Edge[m];

        for(int i=0;i<m;i++){
            int t=pr.nextInt();
            int u=pr.nextInt();
            int v=pr.nextInt();
            arr[i]=new Edge(t,u,v);
        }

        adj_dir=new HashMap<>();
        adj_u=new HashMap<>();
        adj=new ArrayList<>();
        for(int i=0;i<=n;i++){
            adj.add(new ArrayList<Integer>());
        }

        for(int i=0;i<m;i++){
            if(arr[i].t==1){

                String key=arr[i].u+" "+arr[i].v;
                if(adj_dir.containsKey(key)){
                    adj_dir.get(key).add(i);
                }
                else{
                    adj.get(arr[i].u).add(arr[i].v);
                    ArrayList<Integer> lis=new ArrayList<Integer>();
                    lis.add(i);
                    adj_dir.put(key,lis);
                }
            }
            else{
                String key=arr[i].u+" "+arr[i].v;
                if(adj_u.containsKey(key)){
                    adj_u.get(key).add(i);
                }
                else{
                    adj.get(arr[i].u).add(arr[i].v);
                    adj.get(arr[i].v).add(arr[i].u);
                    ArrayList<Integer> lis=new ArrayList<Integer>();
                    lis.add(i);
                    adj_u.put(key,lis);
                }

                /*key=arr[i].v+" "+arr[i].u;
                if(adj_u.containsKey(key)){
                    adj_u.get(key).add(i);
                }
                else{
                    ArrayList<Integer> lis=new ArrayList<Integer>();
                    lis.add(i);
                    adj_u.put(key,lis);
                }*/
            }
        }

        for(int i=0;i<m;i++){
            arr[i].c='+';
        }

        int cnt=bfsMax(s);

        out.println(cnt);
        for(int i=0;i<m;i++){
            if(arr[i].t==2){
                out.print(arr[i].c);
            }
        }
        out.println("");


        for(int i=0;i<m;i++){
            arr[i].c='+';
        }

        cnt=bfsMin(s);
        out.println(cnt);
        for(int i=0;i<m;i++){
            if(arr[i].t==2){
                out.print(arr[i].c);
            }
        }

        out.println("");

        out.close();
    }



    static int bfsMin(int src){
        int visited[]=new int[n+1];
        visited[src]=1;
        Queue<Integer> qu=new LinkedList<>();
        qu.add(src);
        while (!qu.isEmpty()){
            int node=qu.remove();
            for(int next : adj.get(node)){
                if(visited[next]==0) {
                    String key = node + " " + next;
                    String key_a=next+" "+node;
                    if(adj_dir.containsKey(key)){
                        visited[next]=1;
                        qu.add(next);
                    }
                    else{
                        if(!adj_u.containsKey(key)){
                            key=key_a;
                        }
                        if(adj_u.containsKey(key)){
                            ArrayList<Integer> lis=adj_u.get(key);
                            for(int index : lis){
                                Edge e=arr[index];
                                if(e.u==node){
                                    e.c='-';
                                }
                                else{
                                    e.c='+';
                                }
                            }
                        }
                    }
                }
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(visited[i]==1){
                cnt++;
            }
        }
        return cnt;
    }

    static int bfsMax(int src){
        int visited[]=new int[n+1];
        visited[src]=1;
        Queue<Integer> qu=new LinkedList<>();
        qu.add(src);
        while (!qu.isEmpty()){
            int node=qu.remove();
            for(int next : adj.get(node)){
                if(visited[next]==0) {
                    String key = node + " " + next;
                    String key_a=next+" "+node;
                    if(adj_dir.containsKey(key)){
                        visited[next]=1;
                        qu.add(next);
                    }
                    else{
                        if(!adj_u.containsKey(key)){
                            key=key_a;
                        }
                        if(adj_u.containsKey(key)){
                            ArrayList<Integer> lis=adj_u.get(key);
                            for(int index : lis){
                                Edge e=arr[index];
                                if(e.u==node){
                                    e.c='+';
                                }
                                else{
                                    e.c='-';
                                }
                            }
                            visited[next]=1;
                            qu.add(next);
                        }
                    }
                }
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(visited[i]==1){
                cnt++;
            }
        }
        return cnt;
    }

    static String simplify(String str){
        for(int i=str.length()-1;i>=1;i--){
            if(str.charAt(i)=='o' && str.charAt(i-1)=='o'){
                String str_dup=new String("");
                if(i!=1) {
                    str_dup= str.substring(0, i - 1);
                }
                str_dup=str_dup+"u";
                if(i!=str.length()-1) {
                    str_dup = str_dup + str.substring(i + 1, str.length());
                }
                str=str_dup;
            }
            else if(str.charAt(i)=='h' && str.charAt(i-1)=='k'){
                String str_dup=new String("");
                if(i!=1) {
                    str_dup= str.substring(0, i - 1);
                }
                str_dup=str_dup+"h";
                if(i!=str.length()-1) {
                    str_dup = str_dup + str.substring(i + 1, str.length());
                }
                str=str_dup;
            }
            else if(str.charAt(i)=='o' && str.charAt(i-1)=='u'){
                String str_dup=new String("");
                if(i!=1) {
                    str_dup= str.substring(0, i - 1);
                }
                str_dup=str_dup+"ou";
                if(i!=str.length()-1) {
                    str_dup = str_dup + str.substring(i + 1, str.length());
                }
                str=str_dup;
            }
        }
        return str;
    }

}