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.util.*;
import java.io.*;
import java.math.*;

/**
 *
 * @Har_Har_Mahadev
 */

/**
 * Main , Solution , Remove Public
 */
public class F {

	private static ArrayList<Pair>[] adj;
	private static ArrayList<Integer>[] tobecome;
	private static int n,m,k;
	private static int[] dis;
	private static int ans;
	private static StringBuilder res;

	public static void process() throws IOException {

		n = sc.nextInt();m =sc.nextInt();k =sc.nextInt();
		adj = new ArrayList[n+1];
		tobecome = new ArrayList[n+1];
		for(int i = 0; i<=n; i++) {
			adj[i] = new ArrayList<Pair>();
			tobecome[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i<m; i++) {
			int u = sc.nextInt(),v = sc.nextInt();
			adj[u].add(new Pair(v, i));
			adj[v].add(new Pair(u, i));
		}
		BFS(1);
		ans = 0;
		res = new StringBuilder();
		solve(new int[m],2);
		println(ans);
		println(res);
	}
	private static void solve(int[] is, int i) {
		if(i == n+1) {
			ans++;
			for (int x:is)res.append(x);
            res.append("\n");
            return;
		}
		for(int e : tobecome[i]) {
			is[e] = 1;
			solve(is, i+1);
			is[e] = 0;
			if(ans >= k)return;
		}
		
	}
	
	private static void BFS(int node) {
		dis = new int[n+1];
		Arrays.fill(dis, Integer.MAX_VALUE);
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(node);
		dis[node] = 0;
		while(!q.isEmpty()) {
			int curr = q.poll();
			for(Pair e : adj[curr]) {
				int child = e.x;
				if(dis[child] == Integer.MAX_VALUE) {
					dis[child] = dis[curr]+1;
					q.add(child);
				}
				if(dis[child] == dis[curr]+1) {
					tobecome[child].add(e.index);
				}
			}
		}
	}

	//=============================================================================
	//--------------------------The End---------------------------------
	//=============================================================================
	private static long INF = 2000000000000000000L, M = 1000000007, MM = 998244353;
	private static int N = 0;

	private static void google(int tt) {
		System.out.print("Case #" + (tt) + ": ");
	}

	static FastScanner sc;
	static PrintWriter out;

	public static void main(String[] args) throws IOException {
		boolean oj = true;
		if (oj) {
			sc = new FastScanner();
			out = new PrintWriter(System.out);
		} else {
			sc = new FastScanner(100);
			out = new PrintWriter("output.txt");
		}
		int t = 1;
//		t = sc.nextInt();
		int TTT = 1;
		while (t-- > 0) {
			//			google(TTT++);
			process();
		}
		out.flush();
		out.close();
	}

	static class Pair implements Comparable<Pair> {
		int x, index;

		Pair(int x, int y) {
			this.x = x;
			this.index = y;
		}

		@Override
		public int compareTo(Pair o) {
			return Integer.compare(this.x, o.x);
		}

		//		 @Override
		//		    public boolean equals(Object o) {
		//		        if (this == o) return true;
		//		        if (!(o instanceof Pair)) return false;
		//		        Pair key = (Pair) o;
		//		        return x == key.x && y == key.y;
		//		    }
		//		 
		//		    @Override
		//		    public int hashCode() {
		//		        int result = x;
		//		        result = 31 * result + y;
		//		        return result;
		//		    }
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////////////

	static void println(Object o) {
		out.println(o);
	}

	static void println() {
		out.println();
	}

	static void print(Object o) {
		out.print(o);
	}

	static void pflush(Object o) {
		out.println(o);
		out.flush();
	}

	static int ceil(int x, int y) {
		return (x % y == 0 ? x / y : (x / y + 1));
	}

	static long ceil(long x, long y) {
		return (x % y == 0 ? x / y : (x / y + 1));
	}

	static int max(int x, int y) {
		return Math.max(x, y);
	}

	static int min(int x, int y) {
		return Math.min(x, y);
	}

	static int abs(int x) {
		return Math.abs(x);
	}

	static long abs(long x) {
		return Math.abs(x);
	}

	static long sqrt(long z) {
		long sqz = (long) Math.sqrt(z);
		while (sqz * 1L * sqz < z) {
			sqz++;
		}
		while (sqz * 1L * sqz > z) {
			sqz--;
		}
		return sqz;
	}

	static int log2(int N) {
		int result = (int) (Math.log(N) / Math.log(2));
		return result;
	}

	static long max(long x, long y) {
		return Math.max(x, y);
	}

	static long min(long x, long y) {
		return Math.min(x, y);
	}

	public static int gcd(int a, int b) {
		BigInteger b1 = BigInteger.valueOf(a);
		BigInteger b2 = BigInteger.valueOf(b);
		BigInteger gcd = b1.gcd(b2);
		return gcd.intValue();
	}

	public static long gcd(long a, long b) {
		BigInteger b1 = BigInteger.valueOf(a);
		BigInteger b2 = BigInteger.valueOf(b);
		BigInteger gcd = b1.gcd(b2);
		return gcd.longValue();
	}

	public static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	public static int lcm(int a, int b) {
		return (a * b) / gcd(a, b);
	}

	public static int lower_bound(int[] arr, int x) {
		int low = 0, high = arr.length, mid = -1;

		while (low < high) {
			mid = (low + high) / 2;

			if (arr[mid] >= x)
				high = mid;
			else
				low = mid + 1;
		}

		return low;
	}

	public static int upper_bound(int[] arr, int x) {
		int low = 0, high = arr.length, mid = -1;

		while (low < high) {
			mid = (low + high) / 2;

			if (arr[mid] > x)
				high = mid;
			else
				low = mid + 1;
		}

		return low;
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////////////

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner() throws FileNotFoundException {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		FastScanner(int a) throws FileNotFoundException {
			br = new BufferedReader(new FileReader("input.txt"));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		String nextLine() throws IOException {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		int[] readArray(int n) throws IOException {
			int[] A = new int[n];
			for (int i = 0; i != n; i++) {
				A[i] = sc.nextInt();
			}
			return A;
		}

		long[] readArrayLong(int n) throws IOException {
			long[] A = new long[n];
			for (int i = 0; i != n; i++) {
				A[i] = sc.nextLong();
			}
			return A;
		}
	}

	static void ruffleSort(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
		Arrays.sort(a);
	}

	static void ruffleSort(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
		Arrays.sort(a);
	}
}