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 = input().split()
N = int(N)
M = int(M)

# 2 boat
boat = 2
ab = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    ab.append((a,b))
import numpy as np
ab = np.array(ab)
ok = "IMPOSSIBLE"
for a1 in ab[ab.T[0]==1]:
    # 1 to target N-> ok
  
    for abbb in ab[ab.T[0]==a1[1]]:
        
        if abbb[1] == N:
            ok = "POSSIBLE"
print(ok)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
path = [LIST() for _ in range(M)]

# graph = [[] for _ in range(N)]

# for a, b in path:
# 	graph[a - 1].append(b - 1)
# 	graph[b - 1].append(a - 1)

# print(graph)

# for i in range(len(graph[0])):
# 	if graph[graph[0][i]][len(graph[graph[0][i]]) - 1] == N - 1:
# 		print("POSSIBLE")
# 		exit()

# print("IMPOSSIBLE")

graph = [[0]*N for _ in range(N)]

for i in range(M):
	graph[path[i][0] - 1][path[i][1] - 1] = 1
	graph[path[i][1] - 1][path[i][0] - 1] = 1

for i in range(N):
	if graph[0][i] == 1:
		if graph[i][N - 1] == 1:
			print("POSSIBLE")
			exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
hune=[]
for a in range(M):
    a,b=input().split()
    hune.append(int(a))
    hune.append(int(b))
number=0
indexes=[i for i, x in enumerate(hune) if x==1]
numbers=[]
for z in indexes:
    numbers.append(hune[z+1])
for y in numbers:
    for x in range(0,2*M-1,2):
        if y==hune[x] and hune[x+1]==N:
            print('POSSIBLE')
            number+=1
            break
    for w in range(1,2*M,2):
        if y==hune[w] and hune[w-1]==N:
            print('POSSIBLE')
            number+=1
            break
if number==0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
hune=[]
for a in range(M):
    a,b=input().split()
    hune.append(int(a))
    hune.append(int(b))
number=0
for a in range(0,2*M-1,2):
    if hune[a]==1:
        c=hune[a+1]
        for z in range(0,2*M-1,2):
            if hune[z]==c and hune[z+1]==N:
                print('POSSIBLE')
                number+=1
                break
        for y in range(1,2*M,2):
            if hune[z]==c and hune[z-1]==N:
                print('POSSIBLE')
                number+=1
                break
if number==0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
hune=[]
for a in range(M):
    list=[]
    a,b=input().split()
    list.append(int(a))
    list.append(int(b))
    hune.append(list)
number=0
for a in range(M):
    if hune[a][0]==1:
        c=hune[a][1]
        for b in range(M):
            if hune[b][0]==c and hune[b][1]==N:
                print('POSSIBLE')
                number+=1
                break
            elif hune[b][1]==c and hune[b][0]==N:
                print('POSSIBLE')
                number+=1
                break
if number==0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

c = [ab[i][1] for i in range(M) if ab[i][0] == 1]
d = set()
for i in range(M) :
    if ab[i][0] in c :
        d.add(ab[i][1])

if N in d :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

c = [ab[i][1] for i in range(M) if ab[i][0] == 1]
d = set()
for i in range(M) :
    for k in c :
        if ab[i][0] == k :
            d.add(ab[i][1])

if N in d :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
c = 0
B = []
C = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        B.append(b)
    elif b == n:
        C.append(a)
for i in B:
    if i in C:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
Ton = []
Fr1 = []
for i in range(m):
    a, b = map(int, input().split())
    if b==n:
        Ton.append(a)
    if a==1:
        Fr1.append(b)

r = 'IMPOSSIBLE'
for a in Fr1:
    if a in Ton:
        r = 'POSSIBLE'
print(r)

Submission status: Time Limit Exceeded

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

start = []
goal = []

import sys

for i in range(M):
    if ab[i][0] == 1:
        start.append(ab[i])
    if ab[i][1] == N:
        goal.append(ab[i])
        
for i in range(len(start)):
    for j in range(len(goal)):
        if len(set(start[i]) | set(goal[j])) == 3:
            print('POSSIBLE')
            sys.exit()
            
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
for i in range(M):
  a[i], b[i] = map(int, input().split())
c = []
for i in range(M):
  if b[i] == N:
    c.append(a[i])
if len(c) != 0:
  for i in range(M):
    if a[i] == 1:
      for j in range(len(c)):
        if b[i] == c[j]:
          print("POSSIBLE")
          exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    x,y = [], []
    for _ 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')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    g = [[] for _ in range(n)] 
    for _ in range(m):
        a,b = map(int, input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    for i in g[0]:
        if i in g[-1]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    g = [[] for _ in range(n)] 
    for _ in range(m):
        a,b = map(int, input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    for i in g[0]:
        if i in g[-1]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

perm = permutations(ship, 2)
for i in list(perm):
    if i[0][0] == 1 and i[0][1] == i[1][0] and i[1][1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

m = [tuple(sorted(map(int, input().split()))) for _ in range(m) ]

for i in range(2, n+1):
  route1 = (1, i)
  route2 = (i, n)
  if route1 in m and route2 in m:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
ab = [[] for _ in range(n+2)]

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

if any((i in ab[n]) for i in ab[1]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[[0,0]]*m
t=[0]*m
tc=0
a=False
f=0
for k in range(m):
  l[k]=list(map(int,input().split()))
l.sort()
for k in l:
  if (k[0]!=1 and f==0):
    del t[tc:]
    f=1
  if k[0]==1:
    t[tc]=k[1]
    tc+=1
  elif k[1]==n:
    if k[0] in t:
      a=True
      break
if a:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

one2 = []
toN = []

for _ in range(M):
    a, b = map(int, input().split())

    if a == 1:
        one2.append(b)

    if b == N:
        toN.append(a)

flag = False
for a in one2:
    if a in toN:
        flag = True
        break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


if __name__ == "__main__":
    n, m = map(int, input().split())

    g1 = Graph()

    for i in range(m):
        a, b = map(int, input().split())
        g1.add_edge(a-1, b-1)
        g1.add_edge(b-1, a-1)

    d = Dijkstra(g1, 0)

    if d.dist[n-1] == 2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a,b=[0]*m,[0]*m
for i in range(m):
    a[i],b[i] = map(int,input().split())
    
for i in range(m):
    if a[i]==1:
        p=b[i]
        for j in range(m):
            if a[j]==p and b[j]==n:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(M)]
l=[]
for x in a:
    if x[0]==1:l.append(x[1])
for x in a:
    if x[0] in l and x[1]==N:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
e = []
for d in ab:
    if d[1] == N:
        c.append(d[0])
    elif d[0] == 1:
        e.append(d[1])

for f in e:
    if f in c:
        possible = True
        break

if possible:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
for d in ab:
    if d[1] == N:
        c.append(d[0])

for d in ab:
    if d[1] in c and d[0] == 1:
        possible = True

if possible:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    
c = []
for i, d in enumerate(ab):
    if d[1] == N:
        c.append(d[0])
        del ab[i]
    elif d[0] != 1:
        del ab[i]

for d in ab:
    if d[1] in c and d[0] == 1:
        possible = True

if possible:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    
c = []
for d in ab:
    if d[1] == N:
        c.append(d[0])

for d in ab:
    if d[1] in c and d[0] == 1:
        possible = True

if possible:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = []
e = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == N:
    e.append(a)
ans = 'IMPOSSIBLE'
for k in s:
  if k in e:
    ans = 'POSSIBLE'
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

a = []
b = []

for i in li:
  if i[1] == N:
    b.append(i[0])

  if i[0] == 1:
    a.append(i[1])
    
if len(a) == 0 or len(b) == 0:
  print("IMPOSSIBLE")
  sys.exit()
    
for i in a:
  if i in b:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

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

a = []

for i in li:
  if i[0] == N:
    a.append(i[1])

  if i[1] == N:
    a.append(i[0])

for i in li:
  if i[0] == 1 and i[1] in a:
    print("POSSIBLE")
    sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

for x in lst1:
    if lst2.count(x) >= 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def takahasi(n , m , a):

    ans = "IMPOSSIBLE"
    list1 = []
    listn = []

    for i in range(m):
        if a[i][0] == 1:
            list1.append(a[i][1])
        elif a[i][1] == n:
            listn.append(a[i][0])
    
    for i in range(len(list1)):
        if listn.count(list1[i]) != 0:
            ans = "POSSIBLE"

    return ans

def main():
    n , m = map(int , input().split())
    a = [list(map(int,input().split())) for i in range(m)]
    print(takahasi(n , m , a))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from1 = []
toN = []
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1.append(a if a!=1 else b)
  if a == N or b == N:
    toN.append(a if a!=N else b)

F = False

for i in from1:
  for j in toN:
    if i == j:
      F = True
      break
  if F:
    break
print("POSSIBLE" if F else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

#O(M)

flag = False
for idx in a:
    if idx in b:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

s=[]
g=[]
#O(M)
for i in range(M):
    if a[i]==1:
        s.append(b[i])
    if b[i]==N:
        g.append(a[i])
flag = False
for idx in s:
    if idx in g:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

s=[]
g=[]
for i in range(M):
    if a[i]==1:
        s.append(b[i])
    if b[i]==N:
        g.append(a[i])
flag = False
for idx in s:
    if idx in g:
        flag=True

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(m):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

DISTANCE = {i:-1 for i in range(1, n + 1)}
DISTANCE[1] = 0
QUEUE = [1]
while QUEUE:
    now = QUEUE.pop(0)
    for v in GRAPH[now]:
        if DISTANCE[v] != -1:
            continue
        DISTANCE[v] = DISTANCE[now] + 1
        QUEUE.append(v)

print("POSSIBLE" if DISTANCE[n] == 2 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
if len(bb)==0:
	print("IMPOSSIBLE")
	sys.exit()
for k in range(len(bb)):
	for l in range(len(a)):
		if bb[k]==a[l] and b[l]==n :
			print("POSSIBLE")
			sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
if len(bb)==0:
	print("IMPOSSIBLE")
	sys.exit()
for k in range(len(bb)):
	for l in range(len(a)):
		if bb[k]==a[l] and b[l]==n :
			print("POSSIBLE")
			sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
one_to = []
to_N = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        one_to.append(b)
    if b == N:
        to_N.append(a)
one_to.sort()
to_N.sort()
ans = 0 
for i in one_to:
    count = 0
    for j in range(len(to_N)):
        if i == to_N[j]:
            ans = 1
            break
        if i > to_N[j]:
            count += 1
        if i < to_N[j]:
            break
    to_N = to_N[count:]
    if ans == 1:
        break
if ans == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
one_to = []
to_N = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        one_to.append(b)
    if b == N:
        to_N.append(a)
ans = 0 
for i in one_to:
    if i in to_N:
        ans = 1
        break
if ans == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Time Limit Exceeded

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

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append((a, b))
  if b == n:
    e.append((a, b))
    
for a, b in s:
  for a2, b2 in e:
    if b == a2:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ship_list = []
start_list = []
goal_list = []
last_list = []
ans = "IMPOSSIBLE"

# 定期船の一覧をリストに格納
for i in range(m):
    ship_list.append(list(map(int, input().split())))
ship_list.sort(key=lambda x: (x[0], x[1]))

for i in range(len(ship_list)):
    _start, _goal = ship_list[i][0], ship_list[i][1]
    if _start == 1:
        last_list.append([_start, _goal])
        goal_list.append(_goal)
    elif _start in goal_list:
        last_list.append([_start, _goal])
        
for i in range(len(last_list)):
    if last_list[i][0] == 1:
        for j in range(i, len(last_list)):
            if last_list[j][0] == last_list[i][1] and last_list[j][1] == n:
                ans = "POSSIBLE"
                break

print(ans)

Submission status: Time Limit Exceeded

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

ship_list = []
ans = "IMPOSSIBLE"

# 定期船の一覧をリストに格納
for i in range(m):
    ship_list.append(list(map(int, input().split())))
ship_list.sort(key=lambda x: (x[0], x[1]))

for i in range(m):
    if ship_list[i][0] == 1:
        for j in range(i, m):
            if ship_list[j][0] == ship_list[i][1] and ship_list[j][1] == n:
                ans = "POSSIBLE"
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,M=map(int,input().split())
L=[]
B=[]
flg=0
cnt=0
for i in range(M):
    a,b=list(map(int,input().split()))
    L.append([a,b])
    if a==1:
        B.append(b)
        cnt+=1
#print(L)
ans=[]
for i in range(M):
    for j in range(cnt):
        if L[i][0]==B[j]:
            ans.append(L[i][1])
#print(ans)
if N in ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = []
b = []
for i in range(m):
    a_, b_ = map(int, input().split())
    if a_ == 1 or a_ == n or b_ == 1 or b_ == n:
        a.append(a_)
        b.append(b_)

for i in range(len(a)):
    if a[i] == 1 or b[i] == 1:
        x = max(a[i], b[i])
        for j in range(len(a)):
            if a[j] == x or b[j] == x:
                if max(a[j], b[j]) == n:
                    print("POSSIBLE")
                    exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,M=map(int,input().split())
G=[[] for i in range(N+1)]

for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

flg=False

near=[]

for i in range(len(G[1])):
    near.append(G[1][i])

for i in range(len(G[N])):
    if G[N][i] in near:
        flg=True

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

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

mat = [[0] * n for i in range(n)]
path = []
for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])
    mat[a[i]-1][b[i]-1] = 1
    if a[i] == 1:
        path.append(b[i]-1)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True
            break

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

mat = [[0] * n for i in range(n)]

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])
    mat[a[i]-1][b[i]-1] = 1
    #mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True
            break

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])

mat = [[0] * n for i in range(n)]

for i in range(m):
    mat[a[i]-1][b[i]-1] = 1
    #mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True
            break

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])

mat = [[0] * n for i in range(n)]

for i in range(m):
    mat[a[i]-1][b[i]-1] = 1
    mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True
            break

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [0] * m
b = [0] * m

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])

mat = [[0] * n for i in range(n)]

for i in range(m):
    mat[a[i]-1][b[i]-1] = 1
    mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
for i in D[-1]:
  for j in D[0]:
    if i==j:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
for i in D[-1]:
  for j in D[0]:
    if i==j:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

starts = {}
goals = {}
for i in range(len(A)):
    s_num = A[i][0]
    g_num = A[i][1]
    if s_num == '1':
        starts[A[i][1]] = 0
    elif g_num == str(N):
        goals[A[i][0]] = 0

is_ok = False
for s in starts:
    for g in goals:
        if s == g:
            is_ok = True
            break
    if is_ok:
        break


# is_ok = False
# for j in range(len(start)):
#     for k in range(len(goal)):
#         if start[j][1] == goal[k][0]:
#             is_ok = True
#             break
#     if is_ok:
#         break

if is_ok:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

start = []
goal = []
for i in range(len(A)):
    if A[i][0] == '1':
        start.append(A[i])
    elif A[i][1] == str(N):
        goal.append(A[i])

is_ok = False
for j in range(len(start)):
    for k in range(len(goal)):
        if start[j][1] == goal[k][0]:
            is_ok = True
            break
    if is_ok:
        break

if is_ok:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = 0
for i in first:
  if i in second:
    ans = 1
    break
if ans:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
dest,num =map(int,input().split())
l= [[int(i) for i in input().split()] for num in range(num)]
s=[]
p=[]
for x in l:
    if x[0]==1:s.append(x[1])
    if x[1]==dest:p.append(x[0])
for i in s:
    if i in p:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

#S.sort(key=lambda x:x[0])
S.sort()

first = []

for tmp in S:
    if tmp[0]!=1:
        break
    first.append(tmp[1])

for tmp in S:
    if tmp[1] == N and tmp[0] in first:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

#S.sort(key=lambda x:x[0])
S.sort()

first = []

for tmp in S:
    if tmp[0]!=1:
        break
    first.append(tmp[1])

for tmp in S:
    if tmp[0] in first:
        if tmp[1] == N:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")