-
Notifications
You must be signed in to change notification settings - Fork 7
/
grandopening.py
31 lines (31 loc) · 1.02 KB
/
grandopening.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys; input = sys.stdin.readline
V, E = map(int, input().split())
animals = []
currs = []
for _ in range(V):
ani, _, *curr = input().strip().split()
animals.append(ani), currs.append(curr)
rev = {e:i for i,e in enumerate(animals)}
g = [[] for _ in range(V)]
di, do = [0]*V, [0]*V
for i in range(V):
for j in currs[i]:
if animals[i] != j: do[i] += 1; di[rev[j]] += 1; g[i].append(rev[j]), g[rev[j]].append(i)
if sum(di) == sum(do) == 0: print('FALSE ALARM'), exit(0)
for i in range(V):
if g[i]:
stack, vis = [i], set()
while stack:
u = stack.pop()
if u in vis: continue
vis.add(u)
for v in g[u]: stack.append(v)
break
cc = 0
for i in range(V):
if g[i]: cc += 1
p1, m1, same = [], [], []
l = [same, p1, m1]
for i in range(V):
if -1<=di[i]-do[i]<=1: l[di[i]-do[i]].append(i)
print(['IMPOSSIBLE', 'POSSIBLE'][len(vis) == cc and (len(p1), len(m1), len(same)) in [(0, 0, V), (1, 1, V-2), (1, 0, V-1), (0, 1, V-1)]])