Submission #24508145

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import copy
MOD = 10**9+7
N,M = map(int,input().split())
if M == 0:
  print(0)
  exit()
mat = []
for i in range(M):
  A,B = map(int,input().split())
  mat.append([A,B])
  mat.append([B,A])
  
mat.sort()
#print(mat)
def nibutan_ika(NUM,MAT):
  MIN = 0
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import copy

MOD = 10**9+7
N,M = map(int,input().split())

if M == 0:
  print(0)
  exit()

mat = []

for i in range(M):
  A,B = map(int,input().split())
  mat.append([A,B])
  mat.append([B,A])
  
mat.sort()
#print(mat)

def nibutan_ika(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP][0] <= NUM:
      MIN = TMP
    elif MAT[TMP][0] > NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MAX][0] <= NUM:
    MIN = MAX
  return MIN #,MAT[MIN]

def nibutan_ijyou(NUM,MAT):
  MIN = 0
  MAX = len(MAT)-1
  while True:
    TMP = (MIN+MAX)//2
    if MAT[TMP][0] < NUM:
      MIN = TMP
    elif MAT[TMP][0] >= NUM:
      MAX = TMP
    if MAX-MIN <= 1:
      break
  if MAT[MIN][0] >= NUM:
    MAX = MIN
  return MAX #,MAT[MIN]

#print(nibutan_ijyou(2,mat), nibutan_ika(2,mat))

check = [0]*(N+1)
check[1] = 1
ans = [0]*(N+1)
ans[1] = 1

old = []
new = [1]

while True:
  old = copy.deepcopy(new)
  new = []
  #print(old)
  #print(ans)
  for i in range(len(old)):
    #print(nibutan_ijyou(old[i],mat), nibutan_ika(old[i],mat)+1)
    for j in range(nibutan_ijyou(old[i],mat), nibutan_ika(old[i],mat)+1):
      if check[mat[j][1]] == 0:
        #print(mat[j][0],"->",mat[j][1])
        ans[mat[j][1]] = (ans[mat[j][1]] + ans[mat[j][0]]) % MOD
  for i in range(len(old)):
    for j in range(nibutan_ijyou(old[i],mat), nibutan_ika(old[i],mat)+1):
      if check[mat[j][1]] == 0:
        check[mat[j][1]] = 1
        new.append(mat[j][1])
  if new == []:
    break
  if ans[-1] != 0:
    break
    
print(ans[-1])

Submission Info

Judge Result