10824 2024. 04. 16 00:09:28 42 Vasútépítés python3 Elfogadva 100/100 316ms 94368 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)
            try: deg[len(graph[u])].add(u)
            except: deg[len(graph[u])]={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 18ms 12056 KiB
2 Elfogadva 18ms 12416 KiB
3 Elfogadva 20ms 13640 KiB
subtask2 40/40
4 Elfogadva 314ms 92272 KiB
5 Elfogadva 305ms 92776 KiB
6 Elfogadva 300ms 92976 KiB
7 Elfogadva 307ms 93172 KiB
8 Elfogadva 316ms 93272 KiB
9 Elfogadva 305ms 93048 KiB
10 Elfogadva 303ms 93460 KiB
11 Elfogadva 17ms 13744 KiB
subtask3 60/60
12 Elfogadva 314ms 92272 KiB
13 Elfogadva 305ms 92776 KiB
14 Elfogadva 300ms 92976 KiB
15 Elfogadva 307ms 93172 KiB
16 Elfogadva 316ms 93272 KiB
17 Elfogadva 305ms 93048 KiB
18 Elfogadva 303ms 93460 KiB
19 Elfogadva 17ms 13744 KiB
20 Elfogadva 303ms 93256 KiB
21 Elfogadva 300ms 93464 KiB
22 Elfogadva 310ms 93640 KiB
23 Elfogadva 298ms 93776 KiB
24 Elfogadva 312ms 93992 KiB
25 Elfogadva 312ms 93956 KiB
26 Elfogadva 310ms 94008 KiB
27 Elfogadva 310ms 94064 KiB
28 Elfogadva 18ms 14160 KiB
29 Elfogadva 19ms 15160 KiB
30 Elfogadva 17ms 14672 KiB
31 Elfogadva 75ms 94368 KiB