# -*- coding: utf-8 -*-
 
from __future__ import print_function
from itertools import islice, cycle, chain, izip, repeat
 
 
class iterator_keeping_value(object):
    '''Holds the iterator and keeps the last val returned by the iterator'''
    def __init__(self,iterable):          
        self.it = iter(iterable)
        self.val = next(self.it) #get the first value on initializing
 
    def next(self):
        self.val = next(self.it)
        return self.val
 
    def __iter__(self):
        return self
 
 
def detect_cycle(iterable):
    '''Detect a cycle in iterable object.
    Iterable must return an independend iterator on iter(iterable)'''
 
    tortoise = iterator_keeping_value(iterable)
    hare = iterator_keeping_value(islice(iter(iterable),None,None,2))  #two steps at a time
 
    for tortoise_val, hare_val in izip(tortoise,hare):
        if tortoise_val==hare_val:
            break
 
    hare = tortoise #put hare in the place of tortoise
    tortoise = iterator_keeping_value(iterable) #start tortoise from the very beginning
    mu = 0
    for tortoise_val, hare_val in chain(repeat((tortoise.val, hare.val),1),izip(tortoise,hare)):
        #begin with the current val of hare.val and the value of tortoise which is in the first position
        if tortoise_val==hare_val:
            break
        mu += 1
 
    lamb = 0
    tortoise_val = tortoise.val #save the value of tortoise since the object is reassigned to hare
    hare = tortoise
    for hare_val in hare:
        lamb += 1
        if hare_val == tortoise_val: #check AFTER the first step by hare
            break
 
    print('mu: {0}'.format(mu))
    print('lamb: {0}'.format(lamb))
 
 
if __name__ == '__main__':
 
    class iterable(object):
        '''Emulate the object returning iterators having cycles'''
        def __init__(self,beginning,cycling):
            '''
beginning: the beginning part with no cycles (its length corresponds to mu)
cycling: the part which will be cycling (its length corresponds to lamb)
'''
            self.beginning = beginning
            self.cycling = cycling
 
        def __iter__(self):
            return chain(iter(self.beginning),cycle(iter(self.cycling)))
 
    detect_cycle(iterable('1234','678'))
 

IyAtKi0gY29kaW5nOiB1dGYtOCAtKi0KCmZyb20gX19mdXR1cmVfXyBpbXBvcnQgcHJpbnRfZnVuY3Rpb24KZnJvbSBpdGVydG9vbHMgaW1wb3J0IGlzbGljZSwgY3ljbGUsIGNoYWluLCBpemlwLCByZXBlYXQKCgpjbGFzcyBpdGVyYXRvcl9rZWVwaW5nX3ZhbHVlKG9iamVjdCk6CiAgICAnJydIb2xkcyB0aGUgaXRlcmF0b3IgYW5kIGtlZXBzIHRoZSBsYXN0IHZhbCByZXR1cm5lZCBieSB0aGUgaXRlcmF0b3InJycKICAgIGRlZiBfX2luaXRfXyhzZWxmLGl0ZXJhYmxlKTogICAgICAgICAgCiAgICAgICAgc2VsZi5pdCA9IGl0ZXIoaXRlcmFibGUpCiAgICAgICAgc2VsZi52YWwgPSBuZXh0KHNlbGYuaXQpICNnZXQgdGhlIGZpcnN0IHZhbHVlIG9uIGluaXRpYWxpemluZwoKICAgIGRlZiBuZXh0KHNlbGYpOgogICAgICAgIHNlbGYudmFsID0gbmV4dChzZWxmLml0KQogICAgICAgIHJldHVybiBzZWxmLnZhbAoKICAgIGRlZiBfX2l0ZXJfXyhzZWxmKToKICAgICAgICByZXR1cm4gc2VsZgoKCmRlZiBkZXRlY3RfY3ljbGUoaXRlcmFibGUpOgogICAgJycnRGV0ZWN0IGEgY3ljbGUgaW4gaXRlcmFibGUgb2JqZWN0LgogICAgSXRlcmFibGUgbXVzdCByZXR1cm4gYW4gaW5kZXBlbmRlbmQgaXRlcmF0b3Igb24gaXRlcihpdGVyYWJsZSknJycKCiAgICB0b3J0b2lzZSA9IGl0ZXJhdG9yX2tlZXBpbmdfdmFsdWUoaXRlcmFibGUpCiAgICBoYXJlID0gaXRlcmF0b3Jfa2VlcGluZ192YWx1ZShpc2xpY2UoaXRlcihpdGVyYWJsZSksTm9uZSxOb25lLDIpKSAgI3R3byBzdGVwcyBhdCBhIHRpbWUKCiAgICBmb3IgdG9ydG9pc2VfdmFsLCBoYXJlX3ZhbCBpbiBpemlwKHRvcnRvaXNlLGhhcmUpOgogICAgICAgIGlmIHRvcnRvaXNlX3ZhbD09aGFyZV92YWw6CiAgICAgICAgICAgIGJyZWFrCiAgICAKICAgIGhhcmUgPSB0b3J0b2lzZSAjcHV0IGhhcmUgaW4gdGhlIHBsYWNlIG9mIHRvcnRvaXNlCiAgICB0b3J0b2lzZSA9IGl0ZXJhdG9yX2tlZXBpbmdfdmFsdWUoaXRlcmFibGUpICNzdGFydCB0b3J0b2lzZSBmcm9tIHRoZSB2ZXJ5IGJlZ2lubmluZwogICAgbXUgPSAwCiAgICBmb3IgdG9ydG9pc2VfdmFsLCBoYXJlX3ZhbCBpbiBjaGFpbihyZXBlYXQoKHRvcnRvaXNlLnZhbCwgaGFyZS52YWwpLDEpLGl6aXAodG9ydG9pc2UsaGFyZSkpOgogICAgICAgICNiZWdpbiB3aXRoIHRoZSBjdXJyZW50IHZhbCBvZiBoYXJlLnZhbCBhbmQgdGhlIHZhbHVlIG9mIHRvcnRvaXNlIHdoaWNoIGlzIGluIHRoZSBmaXJzdCBwb3NpdGlvbgogICAgICAgIGlmIHRvcnRvaXNlX3ZhbD09aGFyZV92YWw6CiAgICAgICAgICAgIGJyZWFrCiAgICAgICAgbXUgKz0gMQoKICAgIGxhbWIgPSAwCiAgICB0b3J0b2lzZV92YWwgPSB0b3J0b2lzZS52YWwgI3NhdmUgdGhlIHZhbHVlIG9mIHRvcnRvaXNlIHNpbmNlIHRoZSBvYmplY3QgaXMgcmVhc3NpZ25lZCB0byBoYXJlCiAgICBoYXJlID0gdG9ydG9pc2UKICAgIGZvciBoYXJlX3ZhbCBpbiBoYXJlOgogICAgICAgIGxhbWIgKz0gMQogICAgICAgIGlmIGhhcmVfdmFsID09IHRvcnRvaXNlX3ZhbDogI2NoZWNrIEFGVEVSIHRoZSBmaXJzdCBzdGVwIGJ5IGhhcmUKICAgICAgICAgICAgYnJlYWsKCiAgICBwcmludCgnbXU6IHswfScuZm9ybWF0KG11KSkKICAgIHByaW50KCdsYW1iOiB7MH0nLmZvcm1hdChsYW1iKSkKICAgICAKCmlmIF9fbmFtZV9fID09ICdfX21haW5fXyc6CiAgICAKICAgIGNsYXNzIGl0ZXJhYmxlKG9iamVjdCk6CiAgICAgICAgJycnRW11bGF0ZSB0aGUgb2JqZWN0IHJldHVybmluZyBpdGVyYXRvcnMgaGF2aW5nIGN5Y2xlcycnJwogICAgICAgIGRlZiBfX2luaXRfXyhzZWxmLGJlZ2lubmluZyxjeWNsaW5nKToKICAgICAgICAgICAgJycnCmJlZ2lubmluZzogdGhlIGJlZ2lubmluZyBwYXJ0IHdpdGggbm8gY3ljbGVzIChpdHMgbGVuZ3RoIGNvcnJlc3BvbmRzIHRvIG11KQpjeWNsaW5nOiB0aGUgcGFydCB3aGljaCB3aWxsIGJlIGN5Y2xpbmcgKGl0cyBsZW5ndGggY29ycmVzcG9uZHMgdG8gbGFtYikKJycnCiAgICAgICAgICAgIHNlbGYuYmVnaW5uaW5nID0gYmVnaW5uaW5nCiAgICAgICAgICAgIHNlbGYuY3ljbGluZyA9IGN5Y2xpbmcKCiAgICAgICAgZGVmIF9faXRlcl9fKHNlbGYpOgogICAgICAgICAgICByZXR1cm4gY2hhaW4oaXRlcihzZWxmLmJlZ2lubmluZyksY3ljbGUoaXRlcihzZWxmLmN5Y2xpbmcpKSkKCiAgICBkZXRlY3RfY3ljbGUoaXRlcmFibGUoJzEyMzQnLCc2NzgnKSkK