El graf de la FME (1) P62285


Statement
 

pdf   zip

thehtml

Un novato està encuriosit per saber què és el famós graf de la FME. Després de dies intentant esbrinar-ho, aconsegueix que li expliquin a la festa dels novatos. (És un graf no dirigit on els vèrtexos són els alumnes de la FME, i hi ha una aresta entre x i y si en algun moment x i y es van embolicar. Considereu que no hi ha més d’una aresta entre cada parell x i y, ni arestes del tipus x x.) La pregunta que es fa tot alumne de primer immediatament després de saber què és, és com deu ser el graf en qüestió.

Suposeu que algú només us en diu el nombre de vèrtexos n i el nombre d’arestes m. Amb aquesta informació, podeu assegurar que el graf és connex, o que no ho és, o que us estan enredant?

Entrada

L’entrada consisteix en diversos casos. Cada cas té el suposat nombre de vèrtexos i d’arestes d’un graf no dirigit. Podeu assumir 2 ≤ n ≤ 109 i 0 ≤ m ≤ 109.

Sortida

Per a cada cas, digueu si es pot assegurar que el graf és connex, si es pot assegurar que el graf no és connex, si és impossible que aquest graf existeixi, o si no es compleix cap de les anteriors situacions.

Public test cases
  • Input

    4 4
    142857 42
    2 2
    1000000000 1000000000
    

    Output

    connected
    disconnected
    you've been trolled
    impossible to know
    
  • Information
    Author
    Ferran Alet
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++