10824 | 2024-04-16 00:09:28 | 42 | Vasútépítés | python3 | Accepted 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()
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 18ms | 12056 KiB | ||||
2 | Accepted | 18ms | 12416 KiB | ||||
3 | Accepted | 20ms | 13640 KiB | ||||
subtask2 | 40/40 | ||||||
4 | Accepted | 314ms | 92272 KiB | ||||
5 | Accepted | 305ms | 92776 KiB | ||||
6 | Accepted | 300ms | 92976 KiB | ||||
7 | Accepted | 307ms | 93172 KiB | ||||
8 | Accepted | 316ms | 93272 KiB | ||||
9 | Accepted | 305ms | 93048 KiB | ||||
10 | Accepted | 303ms | 93460 KiB | ||||
11 | Accepted | 17ms | 13744 KiB | ||||
subtask3 | 60/60 | ||||||
12 | Accepted | 314ms | 92272 KiB | ||||
13 | Accepted | 305ms | 92776 KiB | ||||
14 | Accepted | 300ms | 92976 KiB | ||||
15 | Accepted | 307ms | 93172 KiB | ||||
16 | Accepted | 316ms | 93272 KiB | ||||
17 | Accepted | 305ms | 93048 KiB | ||||
18 | Accepted | 303ms | 93460 KiB | ||||
19 | Accepted | 17ms | 13744 KiB | ||||
20 | Accepted | 303ms | 93256 KiB | ||||
21 | Accepted | 300ms | 93464 KiB | ||||
22 | Accepted | 310ms | 93640 KiB | ||||
23 | Accepted | 298ms | 93776 KiB | ||||
24 | Accepted | 312ms | 93992 KiB | ||||
25 | Accepted | 312ms | 93956 KiB | ||||
26 | Accepted | 310ms | 94008 KiB | ||||
27 | Accepted | 310ms | 94064 KiB | ||||
28 | Accepted | 18ms | 14160 KiB | ||||
29 | Accepted | 19ms | 15160 KiB | ||||
30 | Accepted | 17ms | 14672 KiB | ||||
31 | Accepted | 75ms | 94368 KiB |