Problem:


Score : 300 points

Problem Statement

In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.

There are M kinds of regular boat services between these islands.
Each service connects two islands. The i-th service connects Island a_i and Island b_i.

Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.

Help him.

Constraints

3 ≤ N ≤ 200 000

1 ≤ M ≤ 200 000

1 ≤ a_i < b_i ≤ N

(a_i, b_i) \neq (1, N)

If i \neq j, (a_i, b_i) \neq (a_j, b_j).

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

You have to use three boat services to get to Island 4.

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

5 5
1 3
4 5
2 3
2 4
1 4

Sample Output 4

POSSIBLE

You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=list(map(int,input().split()))
N_l=set()
one_l=set()
for i in range(M):
   A,B=list(map(int,input().split()))
   if A == 1:
      one_l.add(B)
   elif B==N:
      N_l.add(A)
if len(N_l & one_l) > 0:
   print("POSSIBLE")
else:
   print("IMPOSSIIBLE")

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
a=[0]*M
b=[0]*M
start=[]
goal=[]
for i in range(0,M):
    a[i],b[i]=list(map(int,input().split()))
    if a[i]==1:
        start.append(b[i])
    elif b[i]==N:
        goal.append(a[i])
for i in range(0,len(start)):
    if goal.count(start[i])>0:
        print('Yes')
        exit()
print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
E=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
dist=[10**7]*n
dist[0]=0
seen=[0]*n
seen[0]=1
stack=[0]
while stack:
  u=stack.pop(-1)
  for v in E[u]:
    if seen[v]!=1:
      dist[v]=min(dist[u]+1,dist[v])
      seen[v]=1
      stack.append(v)
if dist[n-1]==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
E=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
dist=[10**7]*n
dist[0]=0
seen=[0]*n
seen[0]=1
stack=[0]
while stack:
  u=stack.pop()
  for v in E[u]:
    if seen[v]!=1:
      dist[v]=min(dist[u]+1,dist[v])
      seen[v]=1
      stack.append(v)
if dist[n-1]==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
E=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
dist=[0]*n
stack=[0]
while stack:
  u=stack.pop()
  for v in E[u]:
    if v!=0 and dist[v]==0:
      dist[v]=dist[u]+1
      stack.append(v)
if dist[n-1]==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
graph = {i+1:[]  for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for value in graph[1]:
    if(N in graph[value]):
        print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ships = sorted([list(map(int,input().split())) for i in range(M)])

ans = "IMPOSSIBLE"

con = 0

for i in range(M):
  if ships[i][0] == 1:
    con += 1

for i in range(0,min(M,con + 1)):
  ship = ships[i][1]
  for j in range(con,M):
    if ships[j][0] == ship and ships[j][1] == N:
      ans = "POSSIBLE"
      break
  else:
    continue
      
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = {}
for _ in range(m):
    a, b = map(int, input().split())
    if not a in ab:
        ab[a] = []
    if not b in ab:
        ab[b] = []
    ab[a].append(b)
    ab[b].append(a)

def dfs(i: int, l:list) -> bool:
    if i > 2:
        return False

    for _l in l:
        if n in ab[_l]:
            return True

        return dfs(i+1, ab[_l])

print("POSSIBLE" if dfs(1, ab[1]) else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))


connections = dict()
answer = {
    'true': 'POSSIBLE',
    'false': 'IMPOSSIBLE'
}


def add_to_set(a, b):
    if a in connections:
        connections[a].add(b)
    else:
        connections[a] = set([b])

    if b in connections:
        connections[b].add(a)
    else:
        connections[b] = set([a])


for i in range(m):
    a, b = list(map(int, input().split()))
    add_to_set(a, b)

island_1 = connections.get(1)
island_N = connections.get(n)


for e in island_1:
    if island_N and e in island_N:
        print(answer['true'])
    else:
        print(answer['false'])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())

islands = [0 for i in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  
  if a == 1:
    if islands[b-1] == 2:
      print('Possible')
      break
    islands[b-1] = 1
  if b == n:
    if islands[a-1] == 1:
      print('Possible')
      break
    islands[a-1] = 2
    
  if i == m-1:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
# 10 5
# 1 2
# 1 3
# 1 4
# 8 10
# 1 8

n, m = map(int, input().split())

ends = []
starts = []
possible = False
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        starts.append([a, b])
    elif b == n:
        ends.append([a, b])

starts.sort(key=lambda x: x[1])
ends.sort(key=lambda x: x[0])
if not (starts and ends):
    print("IMPOSSIBLE")
    import sys
    sys.exit()




i = 0
j = 0
while i != len(starts) and j != len(ends):
    to = starts[i][1]
    fr = ends[j][0]

    if to == fr:
        possible = True
        break

    if to > fr:
        i += 1
    elif fr > to:
        j += 1

while j != len(ends):
    fr = ends[j][0]
    if to == fr:
        possible = True
        break

    j += 1

while i != len(starts):
    to = starts[i][1]
    if to == fr:
        possible = True
        break

    i += 1

print("POSSIBLE") if possible else print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

ends = []
starts = []
possible = False
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        starts.append([a, b])
    elif b == n:
        ends.append([a, b])

starts.sort(key=lambda x: x[1])
ends.sort(key=lambda x: x[0])

i = 0
j = 0
while i != len(starts) and j != len(ends):
    to = starts[i][1]
    fr = ends[j][0]

    if to == fr:
        possible = True
        break

    if to > fr:
        i += 1
    if fr > to:
        j += 1

print("POSSIBLE") if possible else print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split()))for i in[0]*b]
d=[]
e=[]
for i in c:
  if i[0]==1:d+=[i[1]]
  elif i[1]==a:e+=[i[0]]
print((set(d)&set(e)=={})*'IM'+'POSSIBLE')

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split()))for i in[0]*b]
for i in range(3,a+1):
  if[1,i]in c and[i,a]in c:print('POSSIBLE');exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
a=g[0]
print(a)
for i in a:
	if N-1 in g[i]:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
a=g[0]
for i in a:
	if N-1 not in g[i]:
		print('IMPOSSIBLE')
		break
else:
	print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
a=g[0]
for i in a:
	if N-1 not in g[i]:
		print('IMPOSSIBLE')
		break
else:
	print('IPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
from_1 = [False]*N
to_N = [False]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a-1 == 0:
        from_1[b-1] = True
    elif b-1 == 0:
        to_N[a-1] = True
for i in range(1, N):
    if from_1[i] and to_N[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ab = [[int(i) for i in input().split()] for _ in range(M)]

A = []
B = [0]*N
for a,b in ab:
  if a==1:
    A.append(a)
  if b==N:
    B[a]=1

for a in A:
  if B[a]==1:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import bisect
n,m = (int(i) for i in input().split())
a = []
for i in range(m):
 tmp1,tmp2 = (int(i) for i in input().split())
 a.append([tmp1,tmp2])
start = sorted(a, key=lambda x: x[0])
start = start[0:bisect.bisect_right(start[0],1)+1]

cand = []
for c,b in enumerate(start):
  if [b[1],n] in a:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
flag = False
v=[]
x=[]
y=[]
for i in range(M):
    a,b=map(int,input().split())
    v.append((a,b))
    if a==1:
        x.append(b)
    if b==N:
        y.append(a)
for i in x:
    for j in y:
        if x==y:
            flag=True
            break
    if flag:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
x=set()
y=set()
for i in range(m):
    a,b=map(int, input().split())
    if a==1:x.add(b)
    if b==n:y.add(a)
if x&y:print('POSSIBLE')
else:print('IMPOSSILE')

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
n, m = s[0], s[1]
ton = set()
tom = set()
if n == m:
    ton = {1, 2, 3}
    tom = {1, 2, 3}    
for i in range(m):
    s = list(map(int, input().split()))
    if s[0] == m:
        tom |= set(s)
    elif s[1] == m:
        tom |= set(s)
    elif s[1] == n:
        ton |= set(s)
    elif s[0] == n:
        ton |= set(s) 
ton -= {n, m}
tom -= {n, m}   
if ton & tom == set():
    print("IMPOSSIBLE")
else:
    print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
n, m = s[0], s[1]
ton = set()
tom = set()
if n == m:
    ton = {1, 2, 3}
    tom = {1, 2, 3}    
for i in range(m):
    s = list(map(int, input().split()))
    if s[0] == m:
        tom |= set(s)
    elif s[1] == m:
        tom |= set(s)
    elif s[1] == n:
        ton |= set(s)
    elif s[0] == n:
        ton |= set(s) 
ton -= {n, m}
print(ton)
tom -= {n, m}   
print(tom)
print(ton & tom)     
if ton & tom == set():
    print("IMPOSSIBLE")
else:
    print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
n, m = s[0], s[1]
ton = set()
tom = set()
for i in range(m):
    s = list(map(int, input().split()))
    if s[0] == m:
        tom |= set(s)
    elif s[1] == m:
        tom |= set(s)
    elif s[1] == n:
        ton |= set(s)
    elif s[0] == n:
        ton |= set(s) 
ton -= {n, m}
tom -= {n, m}       
if ton & tom == set():
    print("IMPOSSIBLE")
else:
    print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
n, m = s[0], s[1]
ton = set()
tom = set()
for i in range(m):
    s = list(map(int, input().split()))
    if s[0] == m:
        tom | set(s)
    if s[1] == m:
        tom | set(s)
    if s[1] == n:
        ton | set(s)
    if s[0] == n:
        ton | set(s) 
if ton & tom == {}:
    print("IMPOSSIBLE")
else:
    print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int, input().split())
a= []
b=[]
for i in range(m):
  ai,bi=map(int, input().split())
  a.append(ai)
  b.append(bi)
d=deque()
for i in range(m):
  if a[i]==1:
    d.append(b[i])
  if b[i]==1:
    d.append(a[i])
if(len(d)>0):
  c=d.pop()
  for i in range(m):
    if a[i]==c:
      if b[i]==n:
        print("POSSIBLE")
        exit()
      else:
        d.append(b[i])
    if b[i]==c:
      if a[i]==n:
        print("POSSIBLE")
        exit()
      else:
        d.append(a[i])
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=input().split()
a,b,z=[],[],0
for j in range(int(m)):
	x,y=input().split()
	a.append(int(x))
	b.append(int(y))
n = int(n)
for j in range(len(b)):
	if b[j]==n:
		z=a[j]
null=0
for j in range(len(b)):
	if b[j]==z and a[j]==1:
		print('POSSIBLE')
		break
	else:
		null+=1
if null==len(b):
	print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
class UnionFind():
	def __init__(self,size):
		self.table = [-1 for _ in range(size)]

	def find(self,x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def unite(self,x,y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] != self.table[s2]:
				if self.table[s1] < self.table[s2]:
					self.table[s2] = s1
				else:
					self.table[s1] = s2
			else:
				self.table[s1] += -1
				self.table[s2] = s1
		return

	def same(self,x,y):
		return self.find(x) == self.find(y)


N, M = map(int,input().split())
edges = [[] for _ in range(N)]

for i in range(M):
	a, b = map(int,input().split())
	if a == 0 or a == N or b == 0 or b == N:
		edges[a-1] += [b-1]
		edges[b-1] += [a-1]

uf = UnionFind(N)

for u in edges[0]:
	if N-1 not in edges[0]:
		uf.unite(0,u)

for v in edges[N-1]:
	if 0 not in edges[N-1]:
		uf.unite(N-1,v)

print("POSSIBLE" if uf.same(0,N-1) == True else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())

f = dict()
for i in range(m):
    a, b = map(int, raw_input().split())
    f[a] = b

if m == 1:
    print("IMPOSSIBLE")
    exit()
for k, v in f.iteritems():
    if k == 1:
        if v not in f:
            continue
        if f[v] == n:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())

f = dict()
for i in range(m):
    a, b = map(int, raw_input().split())
    f[a] = b

if m == 1:
    print("IMPOSSIBLE")
    exit()

for k, v in f.iteritems():
    if k == 1:
        if v not in f:
            continue
        if f[v] == n:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
x = input().split(" ")
n = int(x[0])
m = int(x[1])

probInit = set([])
probEnd  = set([])

for i in range(m):
    edge = input().split(" ")
    if edge[0] == 0:
        probInit.add(edge[1])

    if edge[1] == n - 1:
        probEnd.add(edge[0])

sec = probEnd.intersection(probInit)
if (len(sec) == 0):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
x = input().split(" ")
n = int(x[0])
m = int(x[1])

probInit = set([])
probEnd  = set([])

for i in range(m):
    edge = input().split(" ")
    if edge[0] == 0:
        probInit.add(edge[1])

    if edge[1] == n - 1:
        probEnd.add(edge[0])

union = probEnd.union(probInit)
if (len(union) == 0):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
x = input().split(" ")
n = int(x[0])
m = int(x[1])

probInit = set([])
probEnd  = set([])

for i in range(m):
    edge = input().split(" ")
    if edge[0] == 0:
        probInit.add(edge[1])

    if edge[1] == n - 1:
        probEnd.add(edge[0])

union = probEnd.union(probInit)
if (union == set([])):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys;
lines = sys.stdin.readlines();
n = {};
can = "";
max = 1;
for i, line in enumerate(lines):
    start,goal = line.split();
    start = int (start);
    goal  = int (goal);
    if not start in n :
        n[start] = [];
    if (max < start):
        max = start;
    if (max < goal):
        max = goal;
    n[start].append(goal);
if(n.has_key(1)):
    for w in n[1]:
        if w is not None and w == max:
            can = "POSSIBLE";
            break;
        elif w is not None and w in n:
            for i in n[w]:
                if i == max:
                    can = "POSSIBLE";
                    break;

if can == "":
    print ("IMPOSSIBLE");
else:
    print(can);

Submission status: Wrong Answer

Solution code:
import sys;
lines = sys.stdin.readlines();
n = {};
can = "";
max = 1;
for i, line in enumerate(lines):
    start,goal = line.split();
    start = int (start);
    goal  = int (goal);
    if not start in n :
        n[start] = [];
    if (max < start):
        max = start;
    if (max < goal):
        max = goal;
    n[start].append(goal);

for w in n[1]:
    if w is not None and w == max:
        can = "POSSIBLE";
        break;
    elif w is not None and w in n:
        for i in n[w]:
            if i == max:
                can = "POSSIBLE";
                break;

if can == "":
    print ("IMPOSSIBLE");
else:
    print(can);

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys

teikibin = {}
ans = False

n, m = sys.stdin.readline().strip().split(" ")
n = int(n)
m = int(m)

for i in range(m):
    a, b = sys.stdin.readline().strip().split(" ")
    a = int(a)
    b = int(b)
    
    if a in teikibin:
        teikibin[a].append(b)
    else:
        teikibin[a] = [b]

    if a == 1:
        target = b
        if b in teikibin[1]:
            if b in teikibin.keys():
                if n in teikibin[b]:
                    ans = True

    else:
        target = a

        if 1 in teikibin.keys():
            if a in teikibin[1]:
                if target in teikibin.keys():
                    if n in teikibin[target]:
                        ans = True

if (not ans):
    print"INPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys

teikibin = {}
ans = False

n, m = sys.stdin.readline().strip().split(" ")
n = int(n)
m = int(m)

for i in range(m):
    a, b = sys.stdin.readline().strip().split(" ")
    a = int(a)
    b = int(b)
    
    if a in teikibin:
        teikibin[a].append(b)
    else:
        teikibin[a] = [b]

    if a == 1:
        target = b

        if target in teikibin[1]:
            if n in teikibin[1]:
                ans = True
    else:
        target = a

        if target in teikibin.keys():
            if b in teikibin[target]:
                ans = True



#    if a in teikibin:
#        teikibin[a].append(b)
#    else:
#        teikibin[a] = [b]
#    
#    if a == 1:
#        if b in teikibin:
#            for _b in teikibin[b]:
#                if _b == n:
#                    ans = True
#    else:
#        if 1 in teikibin:
#            teikibin[a] in teikibin.keys()
#            if b in teikibin[1] or b in teikibin[:
#                ans = True
#
        

#print (n, m, teikibin, ans)
if (not ans):
    print("IN", sep="")
print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
s = input().split()
s = [int(i) for i in s]
N = s[0]
M = s[1]

FROM = []
TO = []
for i in range(M) : 
    s = input().split()
    s = [int(i) for i in s]
    FROM.append(  s[0])
    TO.append( s[1])

#1 から Nに行きたい
# N に行ける定期便を探す　仮に中間地点INDとする
def search():
    IND = []
    IND2 = []
    END = False
    for i in range(M) : 
        if TO[i] == N :
            if FROM[i] in IND2 : return "POSSIBLE"
            IND.append(FROM[i])
        if FROM[i] == 1 : 
            if TO[i] in IND : return "POSSIBLE"
            IND2.append(TO[i])
    
    for i in IND : 
        if i in IND2 : return "POSSIBLE"
    return "INPOSSIBLE"

print(search())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    D = dd(list)

    for m in range(M):
        a, b = map(int, input().split())
        D[a-1].append(b-1)

    for d in D.keys():
        if N-1 in D[d]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    # global stime
    # stime = time.clock()
    main()

Submission status: Wrong Answer

Solution code:
s = input().split()
s = [int(i) for i in s]
N = s[0]
M = s[1]

FROM = []
TO = []
for i in range(M) : 
    s = input().split()
    s = [int(i) for i in s]
    FROM.append(  s[0])
    TO.append( s[1])

#1 から Nに行きたい
# N に行ける定期便を探す　仮に中間地点INDとする
IND = []
IND2 = []
END = False
for i in range(M) : 
    if TO[i] == N :IND.append(FROM[i])
    if FROM[i] == 1 : 
        if TO[i] in IND : 
            FLAG = True
            break
        IND2.append(TO[i])
if i == (M - 1 ) : END = True

if END: 
    # IND2にあるやつがINDにあれば行ける
    FLAG = False
    for i in IND2 :
        if i in IND : 
            FLAG = True
            break

if FLAG : print("POSSIBLE")
else : print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # グラフのノード数
        #dist = [float('inf') for i in range(N)] # 始点から各頂点までの最短距離を格納する
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        count=0
        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            count+=1
            if count==2:
                break
                
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist




def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    n,m=spaceinput()
    g=myGraph()

    for i in range(10**6):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),1)
    res=g.dijkstra(start=1)
    #print(res)
    if n in res and res[n]<=2:
        if res[n]==1:
            if len(set(g.adj[1]).union(g.adj[n]))>0:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        else:
            print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
a=[0]*(200001)


N = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(N[1])]

print(N,x)

for i in x:
    if i[0]==1 :
        if a[i[1]]==1:
            print('POSSIBLE')
            quit()
        a[i[1]]=1
    if i[1]==N[0]:
        if a[i[0]]==1:
            print('POSSIBLE')
            quit()
        a[i[0]]=1

print('IMPOSSIBLE')
quit()

Submission status: Wrong Answer

Solution code:
import math
inf=float('inf')
a=[0]*(200001)


N = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(N[1])]

print(N,x)

for i in x:
    if i[0]==1 :
        if a[i[1]]==1:
            print('OK')
            quit()
        a[i[1]]=1
    if i[1]==N[0]:
        if a[i[0]]==1:
            print('OK')
            quit()
        a[i[0]]=1

print('NG')
quit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math

N, M = list(map(int, sys.stdin.readline().rstrip().split()))


Ss = set()
Es = set()
for _ in range(M):
    a_orig, b_orig = list(map(int, sys.stdin.readline().rstrip().split()))
    for a, b in [(a_orig, b_orig), (b_orig, a_orig)]:
        if a== 1:
            Ss.add(b)
        if a == N:
            Es.add(b)

if len(Ss and Es):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
exit(0)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = []
g = []

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.append(b)
    elif b == n:
        g.append(a)

for i in s:
    if i in g:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

A = []
B = []
for _ in range(m):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)

C = []
for k, v in enumerate(A):
    if v == 1:
        C.append(B[k])

for k, v in enumerate(A):
    if v in C:
        if B[k] == n:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
flag = 0 

possibleships1 = list(filter(lambda x: x[0] == 1, list_ships))
possibleships2 = list(filter(lambda x: x[1] == N, list_ships))
midisland1 = [possibleships1[i][1] for i in range(len(possibleships1))]
midisland2 = [possibleships2[i][0] for i in range(len(possibleships2))]
midisland1.sort()
midisland2.sort()

for i in range(len(midisland1)):
  for j in range(len(midisland2)):
    L1 = midisland1[i]
    L2 = midisland2[j]
    if(L1 == L2):
      print("POSSIBLE")
      flag = 1
      break
    if(L1 < L2):
      break
  if(flag == 1):
    break
    
if(flag == 0):
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
flag = 0 

possibleships1 = list(filter(lambda x: x[0] == 1, list_ships))
possibleships2 = list(filter(lambda x: x[1] == N, list_ships))
midisland1 = [possibleships1[i][1] for i in range(len(possibleships1))]
midisland2 = [possibleships2[i][0] for i in range(len(possibleships2))]
midisland1.sort()
midisland2.sort()

for i in range(len(midisland1)):
  for j in range(len(midisland2)):
    L1 = midisland1[i]
    L2 = midisland2[j]
    if(L1 == L2):
      print("POSSIBLE")
      flag = 1
      break
    if(L1 < L2):
      break
    
if(flag == 0):
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
flag = 0 

possibleships1 = list(filter(lambda x: x[0] == 1, list_ships))
possibleships2 = list(filter(lambda x: x[1] == N, list_ships))
L1 = []
L2 = []

for i in range(len(possibleships1)):
  L1.append(possibleships1[i][1])

for j in range(len(possibleships2)):
  L2.append(possibleships2[j][0])
  
L = L1+ L2  
M = max(L)
m = min(L)

for i in range(m, M+ 1):
  if(L.count(i)>= 2):
    print("POSSIBLE")
    flag = 1
    break
    
if(flag == 0):
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
flag = 0 

possibleships1 = list(filter(lambda x: x[0] == 1, list_ships))
possibleships2 = list(filter(lambda x: x[1] == N, list_ships))

for i in range(2, N):
  if((1, i) in possibleships1 and (i, N) in possibleships2):
    print("POSSIBLE")
    flag = 1
    break
    
if(flag == 0):
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
flag = 0 

for i in range(2, N):
  if((1, i) in list_ships and (i, N) in list_ships):
    print("POSSIBLE")
    flag = 1
    break
    
if(flag == 0):
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
possibleships1 = list(filter(lambda x: x[0] == 1, list_ships))
possibleships2 = list(filter(lambda x: x[1] == N, list_ships))

L1 = len(possibleships1)
L2 = len(possibleships2)
flag = 0

for i in range(L1- 1, -1, -1):
  for j in range(L2- 1, -1, -1):
    if(possibleships1[i][1] == possibleships2[j][0]):
      print("POSSIBLE")
      flag = 1
      break
  if(flag == 1):
    break
    
if(flag == 0):
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list_ships = []
for i in range(M):
  S = tuple(map(int, input().split()))
  list_ships.append(S)
  
possibleships1 = list(filter(lambda x: x[0] == 1, list_ships))
possibleships2 = list(filter(lambda x: x[1] == N, list_ships))

L1 = len(possibleships1)
L2 = len(possibleships2)
flag = 0

for i in range(L1):
  for j in range(L2):
    if(possibleships1[i][1] == possibleships2[j][0]):
      print("POSSIBLE")
      flag = 1
      break
  if(flag == 1):
    break
    
if(flag == 0):
  print("IMPOSSIBLE")