import sage.graphs.graph_list as graphs_list
from itertools import product,combinations
from math import ceil

#The supporting lemma for the algorithm implemented in this code is available at https://www.cs.upc.edu/~sedthilk/twointer/supporting_lemma.pdf

def delete_edge(G,e):
    H=G.copy()
    H.delete_edge(e)
    return H

def contract_edge(G,e):
    H=G.copy()
    u,v=e
    v_edges=[(v,x) for x in G[u]]
    for edge in v_edges:
        if edge[0]==edge[1]:
            v_edges.remove(edge)
    H.delete_vertex(u)
    H.add_edges(v_edges)
    return H

def is_pairwise_intersecting(f):
    for s1 in range(len(f)):
        for s2 in range(s1+1,len(f)):
            if not set(f[s1]).intersection(f[s2]):
                return False
    return True

def strict_bramble(G,order):
    options=[]
    V=G.vertices()
    for S in combinations(V,order-1):
        options.append([])
        H=G.copy()
        H.delete_vertices(S)
        for cc in H.connected_components_subgraphs():
            if cc.order()>=order:
                options[-1].append(cc.vertices())
        if not options[-1]:
            return None
    for f in product(*options):
        if is_pairwise_intersecting(f):
            return f
    return None

def sbn(G):
    for order in range(ceil(G.order()/2),1,-1):
        if strict_bramble(G,order) is not None:
            return order
    return 1

def is_obstruction(G,n):
    if sbn(G)!=n+1:
        return False
    for e in G.edges(labels=False):
        if strict_bramble(contract_edge(G,e),n+1) is not None or strict_bramble(delete_edge(G,e),n+1) is not None:
            return False
    return True

GL=graphs_list.from_graph6(r'''FFzfw
FFzvo
FUZ~o
FUxvw
FUzro
G?zTb{
G?zTf[
G?zTrg
G?zVdw
G?zVfW
G?zfew
GCqjfS
GCqjfo
GCrb`o
GCrbdS
GCxvf_
GEhbtg
GEhfe[
GEhfew
GEhffS
GEhffo
GEhuSw
GEhuUW
GEhvFc
H?Bczpu
H?Becw}
H?Becxy
H?Bedo}
H?Bedpm
H?Bedqm
H?BedrM
H?Bee[~
H?Betp[
H?`vAo]
H?`vApM
H?`vAqV
H?`vAq{
H?`vArK
H?`vBqU
H?bBTiy
H?bBTjQ
H?bBTps
H?bBTqV
H?bBTqu
H?bBV`u
H?bBVaU
H?bDJr[
H?bDrif
H?bDthu
H?bDtjq
H?bDv`u
H?bFBiy
H?bFBrU
H?bFEmz
H?bFMiz
H?bavbE
H?bavba
H?be`om
H?be`qT
H?be`rF
H?beb_x
H?bebrE
H?o~D_N
H?o~Dab
H?q`qgN
H?q`qh]
H?q`qhi
H?q`tra
H?q`uiM
H?q`vAp
H?qbDoz
H?qbDqq
H?qbazE
H?re`oN
HCQeHqY
HCQeHqi
HCQeHqk
HCQeHrR
HCQeHr`
HCQeHrg
HCQeJah
HCQe`ps
HCQe`rF
HCQe`rK
HCQebii
HCQebjK
HCQebjg
HCQebom
HCQeeXe
HCQeeZb
HCQf?zK
HCQf?zS
HCQf@YZ
HCQf@pd
HCQf@pk
HCQf@qM
HCRV@p[
HCp`fbo
HCpbPjS
I??FCtVJw
I??FCt{To
I??FCvSJw
I?ABeTkDw
I?AEDelUw
I?AEDhkUo
I?AEDiyYo
I?AEDjwYo
I?AEF`iFg
I?AEF`ifW
I?AEFaifW
I?AFAiwYO
I?AFAiwao
I?AFAjKMw
I?AFE`MMw
I?AFE`Yjg
I?AFEaYjg
I?B@lPWr?
I?B@t`gT_
I?BD@g]Qo
I?BD@g]VO
I?BD@hYVO
I?BD@jIMg
I?BD@jWF_
I?BDB_{Jg
I?BDB`MF_
I?BDB`[Jg
I?BDB`[iW
I?BDKp[kg
I?BDM`gMo
I?BDM`gUo
I?BDf?[JO
I?BDf?[MO
I?BDf?[bO
I?BDf@Wb_
I?`DEFX\g
I?`DEFovG
I?`DEO{\_
I?`DEPY\g
I?`DEPYlO
I?`DEPY|?
I?`DEPwLo
I?`DEPw\_
I?`DEQt\_
I?`DERR\g
I?`DERp\_
I?`DEesqW
I?`DEqUHw
I?`DF?]v?
I?`DF@YfO
I?`DF@Yv?
I?`DF@qvG
I?`DFBQfO
I?`DFBQvG
I?`DF_uqW
I?`DbRcSo
I?`Df?[L?
I?`FAoscg
I?`FE_w`g
I?`adGw`o
I?`adGwgo
I?`adGwh_
I?`adGwu?
I?`adITf_
I?`adITuG
I?`adI[`w
I?`adJWFO
I?`aeJBn_
I?`af?wEo
I?`af?ww_
I?`afASUO
I?`afASuG
I?b@dHWi_
I?b@dIi\o
I?b@dIwTo
I?b@f?[m?
I?b@f@Sig
I?b@f@SmO
I?b@f@Um?
I?bB@RWEw
I?bB@RW[W
I?bBDHWk_
ICOedHgb_
ICOedHgio
ICOedHgww
ICOedPKL?
J?ABAqWLCS?
J?`@E_wDdG?
J?ABCdWlCR?
J?`@E`gJ`b?
J?B@cXgT`U?
J?`DAaQqRk?
J?AEDFSYQp_
J?BDA_mooz?
J?B@cXeEoN_
''')

for G in GL:
    print(is_obstruction(G,3))