Problem p03726 (python)

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    kk = None
    for _ in range(n-1):
        a,b = LI()
        kk = [a,b]
        d[a].add(b)
        d[b].add(a)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                vt = list(v)[0]
                if len(d[vt]) == 1:
                    continue
                for vv in d[vt]:
                    if vv == k:
                        continue
                    if vt in d[vv]:
                        d[vv].remove(vt)
                d[vt] = set([k])
                tt = True
            elif len(v) == 0:
                return 'First'
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    kk = None
    for _ in range(n-1):
        a,b = LI()
        kk = [a,b]
        d[a].add(b)
        d[b].add(a)

    if sum(kk) > 10**5*1.5:
        raise 't'


    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                vt = list(v)[0]
                if len(d[vt]) == 1:
                    continue
                for vv in d[vt]:
                    if vv == k:
                        continue
                    if vt in d[vv]:
                        d[vv].remove(vt)
                d[vt] = set([k])
                tt = True
            elif len(v) == 0:
                return 'First'
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    kk = None
    for _ in range(n-1):
        a,b = LI()
        kk = [a,b]
        d[a].add(b)
        d[b].add(a)

    if sum(kk) > 10**5*1.5:
        raise 't'


    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                vt = list(v)[0]
                if len(d[vt]) == 1:
                    continue
                for vv in d[vt]:
                    if vv == k:
                        continue
                    d[vv].remove(vt)
                d[vt] = set([k])
                tt = True
            elif len(v) == 0:
                return 'First'
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    kk = None
    for _ in range(n-1):
        a,b = LI()
        kk = [a,b]
        d[a].add(b)
        d[b].add(a)

    if sum(kk) > 10**5*1.5:
        raise 't'

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    if n > 10**4*9.9:
        raise 't'

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    if n > 10**4*9:
        raise 't'

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    if n > 10**4:
        n /= 0

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    if n > 10**4:
        raise 't'

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t]:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    tt = True
    gf = collections.defaultdict(bool)
    while tt:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        tt = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                tt = True
    return 'Second'


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    d = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        d[a].add(b)
        d[b].add(a)

    f = collections.defaultdict(bool)
    rf = False
    def g(s, h, m):
        t = list(d[s] - set([m]))[-1]
        if len(d[t]) > 2:
            if h:
                if f[t] and not rf:
                    return True
                f[t] = True
            else:
                d[t].remove(s)
                d[s].remove(t)
                rf = True
            return False
        if len(d[t]) == 1:
            return not h
        return g(t,not h,s)

    t = True
    gf = collections.defaultdict(bool)
    while t:
        if rf:
            gf = collections.defaultdict(bool)
            f = collections.defaultdict(bool)
            rf = False
        t = False
        for k,v in list(d.items()):
            if len(v) == 1:
                if gf[k]:
                    continue
                gf[k] = True
                res = g(k, True, -1)
                if res:
                    return 'First'
                t = True
    return 'Second'


print(main())