Submission #41572028

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from itertools import combinations
from collections import defaultdict
N, M = map(int, input().split())
S = [input() for _ in range(N)]
edge = defaultdict(list)
for i, j in combinations(range(N), 2):
  cnt = sum(1 for c1, c2 in zip(S[i], S[j]) if c1 != c2)
  if cnt == 1:
    edge[i].append(j)
    edge[j].append(i)
    
odd = 0
eve = 0
for i in range(N):
  deg = len(edge[i])
  if deg == 0:
    print("No")
    exit()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from itertools import combinations
from collections import defaultdict

N, M = map(int, input().split())

S = [input() for _ in range(N)]

edge = defaultdict(list)
for i, j in combinations(range(N), 2):
  cnt = sum(1 for c1, c2 in zip(S[i], S[j]) if c1 != c2)
  if cnt == 1:
    edge[i].append(j)
    edge[j].append(i)
    
odd = 0
eve = 0
for i in range(N):
  deg = len(edge[i])
  if deg == 0:
    print("No")
    exit()
  if deg % 2:
    odd += 1
  else:
    eve += 1
    
if (odd == 0 and eve == N) or (odd == 2 and eve == N - 2):
  print("Yes")
else:
  print("No")
    

Submission Info

Judge Result