from itertools import*
j=''.join
def f(x):
for l in count(1):
for i in product(x,repeat=l):
*b,=zip(*i);c=j(b[0])
if c==j(b[1]):print(c,j(str(x.index(k)+1)for k in i));return
f((('0','110'),('11','1'),('001','100')))
ZnJvbSBpdGVydG9vbHMgaW1wb3J0KgpqPScnLmpvaW4KZGVmIGYoeCk6CiBmb3IgbCBpbiBjb3VudCgxKToKICBmb3IgaSBpbiBwcm9kdWN0KHgscmVwZWF0PWwpOgogICAqYiw9emlwKCppKTtjPWooYlswXSkKICAgaWYgYz09aihiWzFdKTpwcmludChjLGooc3RyKHguaW5kZXgoaykrMSlmb3IgayBpbiBpKSk7cmV0dXJuCgpmKCgoJzAnLCcxMTAnKSwoJzExJywnMScpLCgnMDAxJywnMTAwJykpKQ==