108242024-04-16 00:09:2842Vasútépítéspython3Accepted 100/100316ms94368 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()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted18ms12056 KiB
2Accepted18ms12416 KiB
3Accepted20ms13640 KiB
subtask240/40
4Accepted314ms92272 KiB
5Accepted305ms92776 KiB
6Accepted300ms92976 KiB
7Accepted307ms93172 KiB
8Accepted316ms93272 KiB
9Accepted305ms93048 KiB
10Accepted303ms93460 KiB
11Accepted17ms13744 KiB
subtask360/60
12Accepted314ms92272 KiB
13Accepted305ms92776 KiB
14Accepted300ms92976 KiB
15Accepted307ms93172 KiB
16Accepted316ms93272 KiB
17Accepted305ms93048 KiB
18Accepted303ms93460 KiB
19Accepted17ms13744 KiB
20Accepted303ms93256 KiB
21Accepted300ms93464 KiB
22Accepted310ms93640 KiB
23Accepted298ms93776 KiB
24Accepted312ms93992 KiB
25Accepted312ms93956 KiB
26Accepted310ms94008 KiB
27Accepted310ms94064 KiB
28Accepted18ms14160 KiB
29Accepted19ms15160 KiB
30Accepted17ms14672 KiB
31Accepted75ms94368 KiB