Problem: There are n cities in Berland. Some pairs of cities are connected by roads. All roads are bidirectional. Each road connects two different cities. There is at most one road between a pair of cities. The cities are numbered from 1 to n.

It is known that, from the capital (the city with the number 1), you can reach any other city by moving along the roads.

The President of Berland plans to improve the country's road network. The budget is enough to repair exactly n-1 roads. The President plans to choose a set of n-1 roads such that:

  * it is possible to travel from the capital to any other city along the n-1 chosen roads, 
  * if d_i is the number of roads needed to travel from the capital to city i, moving only along the n-1 chosen roads, then d_1 + d_2 + ... + d_n is minimized (i.e. as minimal as possible). 



In other words, the set of n-1 roads should preserve the connectivity of the country, and the sum of distances from city 1 to all cities should be minimized (where you can only use the n-1 chosen roads).

The president instructed the ministry to prepare k possible options to choose n-1 roads so that both conditions above are met.

Write a program that will find k possible ways to choose roads for repair. If there are fewer than k ways, then the program should output all possible valid ways to choose roads.

Input

The first line of the input contains integers n, m and k (2 ≤ n ≤ 2⋅10^5, n-1 ≤ m ≤ 2⋅10^5, 1 ≤ k ≤ 2⋅10^5), where n is the number of cities in the country, m is the number of roads and k is the number of options to choose a set of roads for repair. It is guaranteed that m ⋅ k ≤ 10^6.

The following m lines describe the roads, one road per line. Each line contains two integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — the numbers of the cities that the i-th road connects. There is at most one road between a pair of cities. The given set of roads is such that you can reach any city from the capital.

Output

Print t (1 ≤ t ≤ k) — the number of ways to choose a set of roads for repair. Recall that you need to find k different options; if there are fewer than k of them, then you need to find all possible different valid options.

In the following t lines, print the options, one per line. Print an option as a string of m characters where the j-th character is equal to '1' if the j-th road is included in the option, and is equal to '0' if the road is not included. The roads should be numbered according to their order in the input. The options can be printed in any order. All the t lines should be different.

Since it is guaranteed that m ⋅ k ≤ 10^6, the total length of all the t lines will not exceed 10^6.

If there are several answers, output any of them.

Examples

Input

4 4 3
1 2
2 3
1 4
4 3


Output

2
1110
1011


Input

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


Output

1
101001


Input

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


Output

2
111100
110110

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.util.Arrays;
import java.io.BufferedWriter;
import java.util.Collection;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Queue;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author out_of_the_box
 */
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);
        FBerlandAndTheShortestPaths solver = new FBerlandAndTheShortestPaths();
        solver.solve(1, in, out);
        out.close();
    }

    static class FBerlandAndTheShortestPaths {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            List<Pair<Integer, Integer>> roads = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                roads.add(Pair.of(a - 1, b - 1));
            }
            List<String> options = solve(n, m, k, roads);
            out.println(options.size());
            options.forEach(out::println);
        }

        private List<String> solve(int n, int m, int k, List<Pair<Integer, Integer>> roads) {
            Graph graph = new AdjacencyList(n);
            for (Pair<Integer, Integer> road : roads) {
                graph.addEdge(road.getLeft(), road.getRight());
            }
            if (graph.edgeCount() != m) {
                throw new RuntimeException("Edge count not getting calculated correctly");
            }
            MyBFS myBFS = new MyBFS();
            myBFS.traverse(graph, 0);
            List<List<Integer>> possibleParents = myBFS.getPossibleParents();
            List<Integer> state = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                state.add(0);
            }
            int cnt = 0;
            List<String> options = new ArrayList<>();
            boolean nextPossible;
            do {
                String option = getOption(state, possibleParents, roads);
                options.add(option);
                nextPossible = nextState(state, possibleParents, n);
                cnt++;
            } while (cnt < k && nextPossible);
            return options;
        }

        private boolean nextState(List<Integer> state, List<List<Integer>> possibleParents, int n) {
//        System.err.println("PossibleParents");
//        int ppSize = possibleParents.size();
//        for (int i = 0; i < ppSize; i++) {
//            List<Integer> pps = possibleParents.get(i);
//            System.err.print(i + " -> ");
//            pps.stream().forEach(ppi -> System.err.print(ppi + " "));
//            System.err.println();
//        }
            for (int i = n - 1; i > 0; i--) {
                int currInd = state.get(i);
                int maxInd = possibleParents.get(i).size() - 1;
                if (currInd < maxInd) {
                    state.set(i, currInd + 1);
                    return true;
                } else if (currInd == maxInd) {
                    state.set(i, 0);
                } else {
                    throw new RuntimeException("currInd is illegal. currInd = " + currInd + ", maxInd = " + maxInd);
                }
            }
            return false;
        }

        private String getOption(List<Integer> state, List<List<Integer>> possibleParents, List<Pair<Integer, Integer>> roads) {
            StringBuilder stringBuilder = new StringBuilder();
            for (Pair<Integer, Integer> road : roads) {
//            System.err.println("possibleParents.size() = " + possibleParents.size());
//            System.err.println("road.getRight() = " + road.getRight());
//            System.out.println("road.getLeft() = " + road.getLeft());
//            System.out.println("state.size() = " + state.size());
                if (check(road.getLeft(), road.getRight(), state, possibleParents)) {
                    stringBuilder.append('1');
                } else {
                    stringBuilder.append('0');
                }
            }
            return stringBuilder.toString();
        }

        private boolean check(int i, int j, List<Integer> state, List<List<Integer>> pp) {
            if (j != 0 && pp.get(j).get(state.get(j)).equals(i)) {
                return true;
            }
            if (i != 0 && pp.get(i).get(state.get(i)).equals(j)) {
                return true;
            }
            return false;
        }

        private class MyBFS extends BFSTraversal {
            private List<Integer> dis;
            private List<List<Integer>> possibleParents;

            public List<List<Integer>> getPossibleParents() {
                return possibleParents;
            }


            protected void init(int vertexCount) {
                super.init(vertexCount);
                dis = new ArrayList<>(vertexCount);
                for (int i = 0; i < vertexCount; i++) {
                    dis.add(Integer.MAX_VALUE);
                }
                possibleParents = new ArrayList<>(vertexCount);
                for (int i = 0; i < vertexCount; i++) {
                    possibleParents.add(new ArrayList<>());
                }
            }


            protected void processEdge(int i, int j) {
                super.processEdge(i, j);
                int currDis = dis.get(j);
                int possDis = dis.get(i) + 1;//Will not be MAX_VALUE
                if (possDis < currDis) {
                    dis.set(j, possDis);
                    List<Integer> possiblePar = new ArrayList<>();
                    possiblePar.add(i);
                    possibleParents.set(j, possiblePar);
                } else if (possDis == currDis) {
                    possibleParents.get(j).add(i);
                }
            }


            protected void processVertexEarly(int i) {
                super.processVertexEarly(i);
                if (parent[i] == -1) {
                    //if (parent.get(i) == -1) {
                    dis.set(i, 0);
                }
            }

        }

    }

    static interface GraphTraversal {
    }

    static abstract class BaseGraphTraversal implements GraphTraversal {
        private Queue<Integer> unprocessedVertices;
        protected BaseGraphTraversal.VertexState[] state;
        protected int[] parent;

        protected void init(int vertexCount) {
            this.unprocessedVertices = supplyQueue();
            this.state = new BaseGraphTraversal.VertexState[vertexCount];
            this.parent = new int[vertexCount];
            //this.state = new ArrayList<>(vertexCount);
            //this.parent = new ArrayList<>(vertexCount);
            Arrays.fill(parent, -1);
            for (int i = 0; i < vertexCount; i++) {
                state[i] = BaseGraphTraversal.VertexState.UNDISCOVERED;
                //state.add(VertexState.UNDISCOVERED);
                //parent.add(-1);
            }
        }


        public void traverse(Graph graph, int source) {
            int vertexCount = graph.vertexCount();
            init(vertexCount);
            state[source] = BaseGraphTraversal.VertexState.DISCOVERED;
            //state.set(source, VertexState.DISCOVERED);
            unprocessedVertices.add(source);
            while (!unprocessedVertices.isEmpty()) {
                int vertex = unprocessedVertices.remove();
                processVertexEarly(vertex);
                state[vertex] = BaseGraphTraversal.VertexState.PROCESSED;
                //state.set(vertex, VertexState.PROCESSED);
                List<Integer> edges = graph.getAdjacentVertices(vertex);
                for (Integer edge : edges) {
                    if (state[edge] != BaseGraphTraversal.VertexState.PROCESSED || graph.isDirected()) {
                        //if (state.get(edge) != VertexState.PROCESSED || graph.isDirected()) {
                        processEdge(vertex, edge);
                    }
                    if (state[edge] == BaseGraphTraversal.VertexState.UNDISCOVERED) {
                        //if (state.get(edge) == VertexState.UNDISCOVERED) {
                        state[edge] = BaseGraphTraversal.VertexState.DISCOVERED;
                        //state.set(edge, VertexState.DISCOVERED);
                        parent[edge] = vertex;
                        //parent.set(edge, vertex);
                        unprocessedVertices.add(edge);
                    }
                }
                processVertexLate(vertex);
            }
        }

        protected abstract Queue<Integer> supplyQueue();

        protected void processVertexEarly(int i) {
        }

        protected void processEdge(int i, int j) {
        }

        protected void processVertexLate(int i) {
        }

        protected enum VertexState {
            UNDISCOVERED,
            DISCOVERED,
            PROCESSED,;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(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 nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int 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 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;
        }

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

        }

    }

    static class BFSTraversal extends BaseGraphTraversal {

        protected Queue<Integer> supplyQueue() {
            return new LinkedList<>();
        }

    }

    static class Pair<L, R> {
        private L left;
        private R right;

        private Pair(L left, R right) {
            this.left = left;
            this.right = right;
        }

        public L getLeft() {
            return left;
        }

        public R getRight() {
            return right;
        }

        public static <A, B> Pair<A, B> of(A a, B b) {
            return new Pair<>(a, b);
        }

    }

    static interface Graph {
        int vertexCount();

        long edgeCount();

        default boolean isDirected() {
            return false;
        }

        void addEdge(int i, int j);

        List<Integer> getAdjacentVertices(int index);

    }

    static class AdjacencyList implements Graph {
        private boolean isDirected;
        private List<List<Integer>> edges;
        private int vertexCount;
        private int edgeCount;
        private int[] degree;

        public AdjacencyList(int vertexCount) {
            init(vertexCount, false);
        }

        public AdjacencyList() {
            init(0, false);
        }

        public AdjacencyList(int vertexCount, boolean isDirected) {
            init(vertexCount, isDirected);
        }

        private void init(int vertexCount, boolean isDirected) {
            this.vertexCount = vertexCount;
            this.isDirected = isDirected;
            edges = new ArrayList<>(vertexCount);
            for (int i = 0; i < vertexCount; i++) {
                edges.add(new LinkedList<>());
            }
            degree = new int[vertexCount];
        }


        public int vertexCount() {
            return vertexCount;
        }


        public long edgeCount() {
            return edgeCount;
        }


        public void addEdge(int i, int j) {
            edges.get(i).add(j);
            degree[i]++;
            if (!isDirected()) {
                edges.get(j).add(i);
                degree[j]++;
            }
            edgeCount++;
        }


        public List<Integer> getAdjacentVertices(int index) {
            return edges.get(index);
        }


        public boolean isDirected() {
            return isDirected;
        }

    }

    static 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 println(Object... objects) {
            print(objects);
            writer.println();
        }

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

        public void println(int i) {
            writer.println(i);
        }

    }
}