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: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().split()))
start=[]
goal=[]
ans=0
for i in range(0,M):
    a,b=list(map(int,input().split()))
    if a==1:
        start.append(b)
        if goal.count(b)>0:
            ans=1
    elif b==N:
        goal.append(a)
        if start.count(a)>0:
            ans=1
if ans==1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
def main():
  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)):
    if ships[i][0] == 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
      break
        
  print(ans)
  
main()

Submission status: Time Limit Exceeded

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)):
  if ships[i][0] == 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
    break
      
print(ans)

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
for i in range(1,N+1):
    if i in start and i in goal:
        ans = 'POSSIBLE'
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
# input処理を高速化する
input = sys.stdin.readline
N,M=map(int,input().split())

#l=[[] for i in range(N)]
l1=[]
ln=[]

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        if b in ln:
            print("POSSIBLE")
            exit()
        l1.append(b)
    elif b==N:
        if a in l1:
            print("POSSIBLE")
            exit()
        ln.append(a)

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
# input処理を高速化する
input = sys.stdin.readline
N,M=map(int,input().split())

#l=[[] for i in range(N)]
l1=[]
ln=[]

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        l1.append(b)
    elif b==N:
        ln.append(a)

for st in l1:
    for fi in ln:
        if st==fi:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

#l=[[] for i in range(N)]
l1=[]
ln=[]

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        l1.append(b)
    elif b==N:
        ln.append(a)

for st in l1:
    for fi in ln:
        if st==fi:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

#l=[[] for i in range(N)]
l1=[]
ln=[]

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        if b in ln:
            print("POSSIBLE")
            exit()
        l1.append(b)
    elif b==N:
        if a in l1:
            print("POSSIBLE")
            exit()
        ln.append(a)

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m=map(int,input().split())
  a=[0]*m
  b=a[:]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
  p=[y for (x,y) in zip(a,b) if x==1]
  q=[y for (x,y) in zip(a,b) if x==n]
  q+=[x for (x,y) in zip(a,b) if y==n]
  for i in p:
    if i in q:
      print("POSSIBLE")
      return
  print("IMPOSSIBLE")
main()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1 or a == n:
            d[a] += [b]
        if b == 1 or b == n:
            d[b] += [a]
    if 1 in d and n in d:
        for i in d[1]:
            for j in d[n]:
                if i == j:
                    print("POSSIBLE")
                    exit()
    print("IMPOSSIBLE ")


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

bridge1 = []
bridge2 = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        bridge1.append((a, b))
    if b == N:
        bridge2.append((a, b))

if len(bridge1) == 0 or len(bridge2) == 0:
    print('IMPOSSIBLE')
    exit()

for b1 in bridge1:
    for b2 in bridge2:
        if b1[1] == b2[0]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

bridge1 = []
bridge2 = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        bridge1.append((a, b))
    if b == N:
        bridge2.append((a, b))

for b1 in bridge1:
    for b2 in bridge2:
        if b1[1] == b2[0]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
C1 = []
C2 = []

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        C1.append(b)
    if b == N:
        C2.append(a)

for i in C1:
    if i in C2:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)

E = []
for v in G[0]:
    if v in E:
        continue
    E.append(v)
    for v2 in G[v]:
        if v2 in E:
            continue
        E.append(v2)

if (N-1) in E:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			exit()
	print('IMPOSSIBLE')

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def can(ab,f,n):
	for i in ab:
		if(i[0]==f and i[1]==n):
			print('POSSIBLE')
			sys.exit()

n,m = map(int,input().split())
ab = []
for i in range(m):
	ab.append(list(map(int,input().split())))
for i in ab:
	if(i[0]==1):
		can(ab,i[1],n)

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

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

for a in A:
  if a in B:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/24
Solved on 2019/2/
@author: shinjisu
"""


# ARC 079 C Voyage
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


# fromNodeからtoNodeまでルートがあるかどうかを調べる
def find(graph, fromNode, toNode, route):  # -1: NG, >=OK、評価値
    dmp((fromNode, toNode), 'f-t')
    if fromNode in route:
        return -1
    else:
        route = route + [fromNode]  # +=だとrouteを書き換えてしまう
        if fromNode == toNode:
            return 0
        if len(route) > 2:
            return -1
        for edge in graph:
            if edge[0] == fromNode:  # graphのソート、一旦fromが見つかった後の中断
                val = find(graph, edge[1], toNode, route)
                dmp((route, edge[1], toNode), 'found')
                if val == 0:
                    return 0
        dmp((fromNode, toNode), 'cannot')
        return -1

    
def probC():
    N, M = getIntList()
    dmp((N, M))
    graph = getIntMat(M)
    dmp(graph)
    for i in range(M):
        graph.append([graph[i][1], graph[i][0]])
    dmp(graph)
    route = []
    if find(graph, 1, N, route) >= 0:
        return 'POSSIBLE'
    else:
        return 'IMPOSSIBLE'

"""
    count = 0
    for i in range(m):
        new = org[:i] + org[i+1:]
        db(('cut',org[i]))
        db(('new',new))
        for j in range(m-1):
            graph[j*2] = new[j]
            graph[j*2+1] = [new[j][1], new[j][0]]
        graph.sort()
        db(('new graph',graph))
        route = []
        if find(graph, org[i][0], org[i][1], route)<0: count += 1
    print(count)
    return 123
"""


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = (int(i) for i in input().split())
a = []
a2 = []
for i in range(m):
 tmp1,tmp2 = (int(i) for i in input().split())
 a.append([tmp1,tmp2])
 a2.append(tmp1)
query = sorted(a, key=lambda x: x[0])
start = sorted(a2)
query2 = query[0:bisect.bisect_right(start,1)]
cand = []
for c,b in enumerate(query2):
  if [b[1],n] in a:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
for i in cand_1:
    for j in cand_2:
        if i == j:
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
for i in cand_1:
    for j in cand_2:
        if i == j:
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
for i in cand_1:
    for j in cand_2:
        if i == j:
            ans = "POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 i==j:
            flag=True
            break
    if flag:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a][b]=1
fl=False
for i in range(N):
    if graph[1][i]==1 and graph[i][N]==1:
        fl=True
if fl:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split())
main_list=list()
list2=list()
k=1
for i in range(m):
    a,b=map(int, input().split())
    list2.append(a)
    list2.append(b)
    main_list.append(list2)
    list2=[]
for i in range(m):
    if main_list[i][0]==1:
        for j in range(m):
            if (main_list[i][1]==main_list[j][0])and(main_list[j][1]==n):
                k=0
                print("POSSIBLE")
                break
if k!=0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a = []
b = []
for i in range(m):
    aa,bb = list(map(int,input().split()))
    a.append(aa)
    b.append(bb)
c = []
d = []
for i in range(m):
    if a[i] == 1:
        c.append(b[i])
    elif a[i] == n:
        d.append(b[i])
    elif b[i] == n:
        d.append(a[i])

ans = 'IMPOSSIBLE'

for i in c:
    if i in d:
        ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

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

a = []
b = []
for i in range(m):
    aa,bb = list(map(int,input().split()))
    a.append(aa)
    b.append(bb)
c = []
for i in range(m):
    if a[i] == 1:
        c.append(b[i])

ans = 'IMPOSSIBLE'
for i in range(m):
    if a[i] in c and b[i] == n:
        ans = 'POSSIBLE'
    elif b[i] in c and a[i] == n:
        ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

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])
while(len(d)>0):
  c=d.pop()
  for i in range(m):
    if a[i]==c:
      if b[i]==n:
        print("POSSIBLE")
        exit()
    if b[i]==c:
      if a[i]==n:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
for i in range(0,M):
	c,d=map(int,input().split())
	a.append(c)
	b.append(d)

pos=0
i=0
e=[]
f=[]
k=0
l=0
for i in range(0,M):
	if a[i] == 1:
		e.append(b[i])
		k=k+1
	if b[i] == 1:
		e.append(a[i])
		k=k+1
	if a[i] == N:
		f.append(b[i])
		l=l+1
	if b[i] == N:
		f.append(a[i])
		l=l+1
for i in range(0,k):
	for j in range(0,l):
		if e[i]==f[j]:
			pos = 1
			break
if pos == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
for i in range(0,M):
	c,d=map(int,input().split())
	a.append(c)
	b.append(d)

pos=0
i=0
e=[]
f=[]
k=0
l=0
for i in range(0,M):
	if a[i] == 1:
		e.append(b[i])
		k=k+1
	if b[i] == 1:
		e.append(a[i])
		k=k+1
	if a[i] == N:
		f.append(b[i])
		l=l+1
	if b[i] == N:
		f.append(a[i])
		l=l+1
for i in range(0,k):
	for j in range(0,l):
		if e[i]==f[j]:
			pos = 1
if pos == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
for i in range(0,M):
	c,d=map(int,input().split())
	a.append(c)
	b.append(d)

pos=0
i=0
while pos==0 and i<M:
	if a[i] == 1:
		c=b[i]
		for j in range(1, M):
			if (a[j]==c and b[j]==N) or (a[j]==N and b[j]==c):
				pos=1
	if b[i] == 1:
		c=a[i]
		for j in range(1, M):
			if (a[j]==c and b[j]==N) or (a[j]==N and b[j]==c):
				pos=1
	i=i+1
if pos == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = True

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:


        return array_result

arr_data = getinputdata()

#島数
n = arr_data[0][0]
m = int(arr_data[0][1])

arr01 = []
arr02 = []
for i in range(1, 1 + m):

    if arr_data[i][0] == "1":
        
        arr01.append(arr_data[i][1])

    if arr_data[i][1] == n:
        
        arr02.append(arr_data[i][0])

chkflg = False
for v in arr01:
    
    if v in arr02:
        
        chkflg = True
        break
        
print("POSSIBLE" if chkflg else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

res = False
for u in edges[0]:
	if u in edges[N-1]:
		res = True
		break

print("POSSIBLE" if res == True else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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 == 1 or a == N or b == 1 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: Time Limit Exceeded

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())
	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: Time Limit Exceeded

Solution code:
from itertools import combinations


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

f = combinations(ferris, 2)
flag = 0
for f_ in f:
    if (f_[0][0]==1 and f_[1][1]==N and f_[0][1]==f_[1][0]) or (f_[1][0]==1 and f_[0][1]==N and f_[0][0]==f_[1][1]):
        print('POSSIBLE')
        flag = 1
        break

if flag==0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

f1 =[]
fN = []
flag = 0

for f in ferris:
    if f[0]==1:
        f1.append(f)
    if f[1]==N:
        fN.append(f)

for f_1 in f1:
    if flag==0:
        for f_N in fN:
            if f_1[1]==f_N[0]:
                print('POSSIBLE')
                flag = 1
                break
            else:
                pass

if flag==0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
[n, m] = [int(num) for num in input().split()];
a = [];
b = [];
for i in range(m):
	[t1, t2] = [int(num) for num in input().split()];
	a.append(t1);
	b.append(t2);
	
start = [];
end = [];
for i in range(m):
	if a[i] == 1:
		start.append(b[i]);
	if b[i] == n:
		end.append(a[i]);

flag = False;		
for i in range(1, n + 1):
	if (i in start) & (i in end):
		flag = True;
		
if (flag):
	print('POSSIBLE');
else:
	print('IMPOSSIBLE');

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = [int(x) for x in sys.stdin.readline().split()]

s = []
d = []

for i in range(m):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	if a == 1:
		if b not in s:
			if b in d:
				print('POSSIBLE')
				break
			else:
				s.append(b)
	if b == n:
		if a not in d:
			if a in s:
				print('POSSIBLE')
				break
			else:
				d.append(a)
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = [int(x) for x in sys.stdin.readline().split()]

s = []
d = []

for i in range(m):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	if a == 1:
		s.append(b)
		if b in d:
			print('POSSIBLE')
			break
	if b == n:
		d.append(a)
		if a in s:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = [int(x) for x in sys.stdin.readline().split()]

s = []
d = []

for i in range(m):
	a, b = [int(x) for x in sys.stdin.readline().split()]
	if a == 1:
		s.append(b)
	if b == n:
		d.append(a)

for x in s:
	if x in d:
		print('POSSIBLE')
		break
	else:
		pass
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m,*T=map(int,open(0).read().split());*S,=zip(T[::2],T[1::2]);s=lambda e:set(sum([s for s in S if e in s],()));print("IM"*(len(s(1)&s(n))<1)+"POSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,raw_input().split())
a=[]
next=[]
bef=[]
for i in range(m):
    a1,b1=map(int,raw_input().split())
    a=a+[[a1,b1]]
    if a1==1:
        next.append(b1)
    if b1==n:
        bef.append(a1)
ans=0
for j in next:
 if j in bef:
     ans=1
if ans==1:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Submission status: Time Limit Exceeded

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"IMPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

from_one = []
to_n = [] 

for i in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        from_one.append(b)
    elif b == N or a == N:
        to_n.append(a)

pos = "IMPOSSIBLE"

for island in from_one:
    if island in to_n:
        pos = "POSSIBLE"

print(pos)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

from_one = []
to_n = []

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_one.append(b)
    elif b == N:
        to_n.append(a)

pos = "IMPOSSIBLE"

for island in from_one:
    if island in to_n:
        pos = "POSSIBLE"

print(pos)

Submission status: Time Limit Exceeded

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 "IMPOSSIBLE"

print(search())

Submission status: Time Limit Exceeded

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 = []
for i in range(M) : 
    if TO[i] == N :IND.append(FROM[i])
    if FROM[i] == 1 : IND2.append(TO[i])

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

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