10823 2024. 04. 15 23:55:43 42 Vasútépítés python3 Futási hiba 0/100 312ms 93816 KiB 
from sys import stdin,stdout
input=stdin.readline

def main():
    N,M = list(map(int, input().split()))
    if M>N:
        print(-1)
        return
    graph={}
    for i in range(M):
        u,v = list(map(int, input().split()))
        try: graph[u].add(v)
        except: graph[u]={v}
        try: graph[v].add(u)
        except: graph[v]={u}
    if len(graph)<N:
        print(-1)
        return
    deg={}
    for key in graph:
        try: deg[len(graph[key])].add(key)
        except: deg[len(graph[key])]={key}
    #print(deg)
    #print(graph)
    # deg2 -> 1...1000
    # deg1 -> 1001...2000
    deg1,deg2=2000,1000
    inf=10**8
    matrix=[list(range(inf-i*1001-N-1,inf-i*1001)) for i in range(0,N+1)]
    #print(matrix)
    while deg[1]:
        v=deg[1].pop()
        u=graph.pop(v).pop()
        #print(v,u)
        matrix[u][v]=deg1
        matrix[v][u]=deg1
        deg1-=1
        if u in deg[1]:
            deg[1].remove(u)
            graph.pop(u)
        else:
            graph[u].remove(v)
            deg[len(graph[u])].add(u)
            if len(deg[len(graph[u])+1])==1:
                deg.pop(len(graph[u])+1)
            else:
                deg[len(graph[u])+1].remove(u)
            if len(graph[u])==1:
                deg[1].add(u)
    if 1 in deg:
        deg.pop(1)
    if len(deg)==0:
        for i in range(1,N):
            #print(*matrix[i][i+1:])
            for j in range(i+1,N+1):
                stdout.write(str(matrix[i][j])+' ')
            stdout.write('\n')
        return
    elif len(deg)>1 or 2 not in deg:
        print(-1)
        return
    #print(deg)
    #print(graph)
    while deg[2]:
        v=deg[2].pop()
        cur=[v]
        while cur[-1] in graph:
            szomsz=graph.pop(cur[-1])
            for u in szomsz:
                if u in deg[2]:
                    deg[2].remove(u)
                    cur.append(u)
                    break
        #print(cur)
        for i in range(len(cur)):
            u=cur[i]
            v=cur[i-1]
            matrix[u][v]=deg2
            matrix[v][u]=deg2
            deg2-=1
                
    #print(N,len(matrix),len(matrix[0]))
    for i in range(1,N):
        #print(*matrix[i][i+1:])
        for j in range(i+1,N+1):
            stdout.write(str(matrix[i][j])+' ')
        stdout.write('\n')
main()
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 19ms 11776 KiB
2 Elfogadva 18ms 12188 KiB
3 Elfogadva 21ms 13492 KiB
subtask2 0/40
4 Futási hiba 85ms 92268 KiB
5 Elfogadva 296ms 92132 KiB
6 Elfogadva 298ms 92372 KiB
7 Elfogadva 305ms 92772 KiB
8 Futási hiba 83ms 92588 KiB
9 Futási hiba 83ms 92512 KiB
10 Futási hiba 83ms 92760 KiB
11 Elfogadva 18ms 13220 KiB
subtask3 0/60
12 Futási hiba 85ms 92268 KiB
13 Elfogadva 296ms 92132 KiB
14 Elfogadva 298ms 92372 KiB
15 Elfogadva 305ms 92772 KiB
16 Futási hiba 83ms 92588 KiB
17 Futási hiba 83ms 92512 KiB
18 Futási hiba 83ms 92760 KiB
19 Elfogadva 18ms 13220 KiB
20 Elfogadva 312ms 92996 KiB
21 Futási hiba 83ms 93336 KiB
22 Elfogadva 296ms 92752 KiB
23 Futási hiba 83ms 93208 KiB
24 Elfogadva 298ms 93320 KiB
25 Elfogadva 310ms 93692 KiB
26 Elfogadva 300ms 93816 KiB
27 Futási hiba 100ms 93692 KiB
28 Elfogadva 18ms 13980 KiB
29 Elfogadva 19ms 14660 KiB
30 Elfogadva 17ms 13908 KiB
31 Elfogadva 75ms 93588 KiB