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 + \dots + 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 \le n \le 2\cdot10^5, n-1 \le m \le 2\cdot10^5, 1 \le k \le 2\cdot10^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 \cdot k \le 10^6$.

The following $m$ lines describe the roads, one road per line. Each line contains two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne 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 \le t \le 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 \cdot k \le 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

Difficulty: HARD
Tags: Complete search

Graph algorithms

Graph traversal

Shortest paths
Skill types: Complete search

Starter code:

Solutions:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
	q = deque()
	q.append(s)
	dist = [-1] * (n + 1)
	dist[s] = 0
	while q:
		i = q.popleft()
		di = dist[i]
		for (j, c) in G[i]:
			if dist[j] == -1:
				dist[j] = di + 1
				q.append(j)
	return dist
(n, m, k) = map(int, input().split())
G = [[] for _ in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	G[a].append((b, i))
	G[b].append((a, i))
dist = bfs(1)
parent = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	di = dist[i]
	for (j, c) in G[i]:
		if dist[j] == di - 1:
			parent[i].append(c)
t = 1
for s in parent:
	t *= max(1, len(s))
	if t > k:
		t = k
		break
print(t)
x = [0] * (n - 1)
l = [len(parent[i]) for i in range(2, n + 1)]
ans = ['0'] * m
for i in range(n - 1):
	ans[parent[i + 2][x[i]]] = '1'
print(''.join(ans))
for i in range(t - 1):
	ans = ['0'] * m
	for i in range(n - 1):
		if x[i] + 1 < l[i]:
			x[i] += 1
			break
		x[i] += 1
		x[i] %= l[i]
	for i in range(n - 1):
		ans[parent[i + 2][x[i]]] = '1'
	print(''.join(ans))


from math import inf
import heapq
(n, m, k) = map(int, input().split(' '))
edge = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split(' '))
	edge[a - 1].append((i, b - 1))
	edge[b - 1].append((i, a - 1))
d = [inf for _ in range(n)]
d[0] = 0
q = [0 for _ in range(n)]
f = 0
r = 1
while f < r:
	i = q[f]
	f += 1
	for (_, j) in edge[i]:
		if d[j] == inf:
			d[j] = d[i] + 1
			q[r] = j
			r += 1
pre = [[] for _ in range(n)]
for i in range(n):
	for (ind, j) in edge[i]:
		if d[j] == d[i] - 1:
			pre[i].append((ind, j))
s = [0 for _ in range(n)]
top = n
sol = []
while top > 0:
	if top == n:
		u = ['0' for _ in range(m)]
		for i in range(1, n):
			u[pre[i][s[i]][0]] = '1'
		sol.append(''.join(u))
		if len(sol) == k:
			break
		top -= 1
	else:
		s[top] += 1
		if s[top] == len(pre[top]):
			top -= 1
		else:
			top += 1
			if top < n:
				s[top] = -1
print(len(sol))
for x in sol:
	print(x)


import sys
import os

class Path:

	def __init__(self, idx, s, d):
		self.idx = idx
		self.s = s
		self.d = d

	def __eq__(self, rhs):
		return self.s == rhs.s and self.d == rhs.d

	def __hash__(self):
		return self.s * 100000 + self.d

def shortestPath(n, k, paths):
	ps = dict()
	for p in paths:
		if p.s not in ps:
			ps[p.s] = [p]
		else:
			ps[p.s].append(p)
		if p.d not in ps:
			ps[p.d] = [p]
		else:
			ps[p.d].append(p)
	d = set()
	open = set()
	d.add(1)
	for e in paths:
		if e.s == 1 or e.d == 1:
			open.add(e)
	general_edges = []
	general_choices = []
	while len(d) < n:
		newd = set()
		choices = dict()
		for e in open:
			oe = e.s
			if e.s in d:
				oe = e.d
			newd.add(oe)
			if oe not in choices:
				choices[oe] = [e.idx]
			else:
				choices[oe].append(e.idx)
		d.update(newd)
		for (oe, p) in choices.items():
			if len(p) > 1:
				general_choices.append(p)
			else:
				general_edges.append(p[0])
		open = set()
		for node in newd:
			for p in ps[node]:
				if (p.s in d) != (p.d in d):
					open.add(p)
	maxk = 1
	for choice in general_choices:
		maxk *= len(choice)
	k = min(k, maxk)
	print(k)
	output = ['0'] * len(paths)
	for e in general_edges:
		output[e] = '1'
	for e in general_choices:
		output[e[0]] = '1'
	for i in range(k):
		print(''.join(output))
		for choice in general_choices:
			done = False
			for i in range(len(choice) - 1):
				if output[choice[i]] == '1':
					output[choice[i]] = '0'
					output[choice[i + 1]] = '1'
					done = True
					break
			if done:
				break
			output[choice[len(choice) - 1]] = '0'
			output[choice[0]] = '1'

def main():
	(n, m, k) = (int(x) for x in input().split())
	paths = []
	for i in range(m):
		path = [int(x) for x in input().split()]
		paths.append(Path(i, path[0], path[1]))
	shortestPath(n, k, paths)

def __starting_point():
	main()
__starting_point()


from math import inf
nmk = list(map(int, input().split(' ')))
n = nmk[0]
m = nmk[1]
k = nmk[2]
a = []
for i in range(m):
	a.append(list(map(int, input().split(' '))))
smej = [[] for j in range(n)]
nums = {}
t = 0
for i in a:
	nums.update({(i[0], i[1]): t})
	t += 1
	smej[i[0] - 1].append(i[1] - 1)
	smej[i[1] - 1].append(i[0] - 1)
dists = [inf for i in range(n)]
dists[0] = 0
q = [0]
while len(q) > 0:
	u = q.pop(0)
	for i in smej[u]:
		if dists[i] == inf:
			q.append(i)
			dists[i] = dists[u] + 1
p = [[] for i in range(n)]
for i in range(1, n):
	for j in smej[i]:
		if dists[j] == dists[i] - 1:
			try:
				p[i].append(nums[j + 1, i + 1])
			except:
				p[i].append(nums[i + 1, j + 1])
am = 1
p.pop(0)
for i in range(len(p)):
	am *= len(p[i])
if am < k:
	print(am)
else:
	print(k)
f = [0 for i in range(len(p))]
ans = []
for i in range(k):
	s = ['0' for i in range(m)]
	for j in range(len(p)):
		s[p[j][f[j]]] = '1'
	s = ''.join(s)
	ans.append(s)
	ok = False
	first = True
	for j in range(len(p) - 1, -1, -1):
		if first:
			first = False
			if f[j] + 1 == len(p[j]):
				if j == 0:
					ok = True
					break
				f[j] = 0
				f[j - 1] += 1
			else:
				f[j] += 1
				break
		elif f[j] == len(p[j]):
			if j == 0:
				ok = True
				break
			else:
				f[j] = 0
				f[j - 1] += 1
	if ok:
		break
for j in range(len(ans)):
	print(ans[j])


(n, m, k) = [int(x) for x in input().split()]
E = [[] for _ in range(n)]
for i in range(m):
	(a, b) = [int(x) for x in input().split()]
	E[a - 1].append((b - 1, i))
	E[b - 1].append((a - 1, i))
Q = [0]
INFTY = n + 1
levels = [INFTY] * n
levels[0] = 0
E_min = [[] for _ in range(n)]
while len(Q) > 0:
	city = Q.pop(0)
	for (adj, i) in E[city]:
		if levels[city] + 1 <= levels[adj]:
			if levels[adj] == INFTY:
				Q.append(adj)
			levels[adj] = levels[city] + 1
			E_min[adj].append(i)

def gen_poss(city, selected, all_poss, next_choice, poss):
	if len(all_poss) >= k:
		return
	if poss >= k:
		all_poss.append(''.join(selected))
		return
	if city == n:
		all_poss.append(''.join(selected))
	else:
		for i in E_min[city]:
			selected[i] = '1'
			next_city = next_choice[city]
			gen_poss(next_city, selected, all_poss, next_choice, poss * len(E_min[city]))
			selected[i] = '0'
next_choice = [0] * n
selected = ['0'] * m
nc = n
for i in range(n - 1, -1, -1):
	next_choice[i] = nc
	if len(E_min[i]) > 1:
		nc = i
	if len(E_min[i]) >= 1:
		selected[E_min[i][0]] = '1'
all_poss = []
gen_poss(next_choice[0], selected, all_poss, next_choice, 1)
print('{}\n{}'.format(len(all_poss), '\n'.join(all_poss)))


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(200001)
(n, m, k) = map(int, input().split())
edge = [[] for _ in range(n)]
di = {}
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a > b:
		(a, b) = (b, a)
	di[a, b] = i
	edge[a].append(b)
	edge[b].append(a)
d = [10 ** 10] * n
d[0] = 0
root = [set() for _ in range(n)]
queue = [0]
for node in queue:
	for mode in edge[node]:
		if d[mode] != 10 ** 10:
			if d[mode] + 1 == d[node]:
				root[node].add(mode)
			elif d[mode] == d[node] + 1:
				root[mode].add(node)
			continue
		d[mode] = d[node] + 1
		queue.append(mode)
for i in range(n):
	root[i] = list(root[i])
t = 1
for i in range(1, n):
	t *= len(root[i])
print(min(t, k))
for i in range(min(t, k)):
	ans = ['0'] * m
	for j in range(1, n):
		(i, jj) = divmod(i, len(root[j]))
		ans[di[min(j, root[j][jj]), max(j, root[j][jj])]] = '1'
	print(''.join(ans))


import sys
import io, os
input = sys.stdin.buffer.readline
(n, m, k) = map(int, input().split())
AB = []
g = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	g[b].append(a)
	AB.append((a, b))
from collections import deque
q = deque([])
q.append(0)
d = [-1] * n
d[0] = 0
while q:
	v = q.popleft()
	for u in g[v]:
		if d[u] == -1:
			d[u] = d[v] + 1
			q.append(u)
inc = [[] for _ in range(n)]
for (i, (a, b)) in enumerate(AB):
	if d[a] + 1 == d[b]:
		inc[b].append(i)
	if d[b] + 1 == d[a]:
		inc[a].append(i)
F = [0] * n
res = []
for i in range(k):
	s = ['0'] * m
	for j in range(1, n):
		s[inc[j][F[j]]] = '1'
	res.append(''.join(s))
	flag = False
	for j in range(1, n):
		if F[j] + 1 < len(inc[j]):
			flag = True
			F[j] += 1
			break
		else:
			F[j] = 0
	if not flag:
		break
print(len(res))
print(*res, sep='\n')