Atcoder ABC282 D問題　TLEの原因が分かりません

Atcoder ABC282 D問題
https://atcoder.jp/contests/abc282/tasks/abc282_d
TLEの原因が分かりません

以下のコードに対して、
(100000 0)のような(nの大きい)入力をするとTLEします。
col関数で計算量が多くなってしまっているのだろうとは思うのですが、
この入力に対して、各colは計算量O(１)ではないのでしょうか？

どなたか回答よろしくお願いします。

プログラムの概要：
・入力に対して、グラフの作成とunion-find木の作成を同時に行う。
・col関数で、各独立した木に対して(union-findで取得した根が属する木に対して)二分グラフの判定および白黒の割り当てを行う
・n*(n-1)//2から、辺の本数であるｍと二分グラフで得た白同士黒同士で結ぶことのできない組み合わせを引く

試したこと：
・sampleはすべて通る
・提出の結果、半分ほどがTLEになり、他はAC
・10000 0などの入力に対してTLEになることから、nが大きい場合に失敗すると考えている
・入力(10 0)でcol関数のwhileの直後にprint(keep)を行っても、無駄なループが発生している様子はない

Python
1from collections import deque
2
3def col(graph,x,size): #二分グラフの判定
4  l=[0,0]
5  check=[False]*size
6  color=[False]*size
7  check[x]=True
8  color[x]='b'
9  l[0]+=1
10  keep=deque([x])
11  while keep:
12    k=keep.popleft()
13    for i in graph[k]:
14      if check[i]:
15        if color[k]==color[i]:
16          return(0)
17      else:
18        check[i]=True
19        if color[k]=='w':
20          color[i]='b'
21          l[0]+=1
22        elif color[k]=='b':
23          color[i]='w'
24          l[1]+=1
25        keep.append(i)
26  return(l)
27      
28def find(x): #union-find
29  if roots[x]<0:
30    return(x)
31  else:
32    roots[x]=find(roots[x])
33    return(roots[x])
34    
35def union(x,y):
36  x=find(x)
37  y=find(y)
38  if x==y:
39    return
40  else:
41    if roots[x]>roots[y]:
42      x,y=y,x
43    roots[x]+=roots[y]
44    roots[y]=x
45    
46n,m=map(int,input().split())
47graph=[[] for _ in range(n)]
48roots=[-1]*n
49
50for _ in range(m): #グラフの作成
51  x,y=map(int,input().split())
52  x-=1
53  y-=1
54  graph[x].append(y)
55  graph[y].append(x)
56  union(x,y)
57
58ans=n*(n-1)//2-m
59for i in range(n): #根なら二分グラフ判定
60  if roots[i]<0:
61    l=col(graph,i,n)
62    if l==0:
63      print(0)
64      exit()
65    else:
66      ans-=l[0]*(l[0]-1)//2+l[1]*(l[1]-1)//2
67print(ans)