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 = map(int, input().split())
info = sorted([list(map(int, input().split())) for _ in range(m)])

q = []
t = m
append = q.append
for i in range(m):
	if info[i][0] == 1:
		append(info[i][1])
	else:
		t = i
		break

for j in range(t, m):
	if info[j][1] == n:
		if info[j][0] in q:
			print("POSSIBLE")
			break
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
info = sorted([list(map(int, input().split())) for _ in range(m)])

q = []
t = m
for i in range(m):
	if info[i][0] == 1:
		q.append(info[i][1])
	else:
		t = i
		break

for j in range(t, m):
	if info[j][0] in q:
		if info[j][1] == n:
			print("POSSIBLE")
			break
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
info = sorted([list(map(int, input().split())) for _ in range(m)])

q = []
for r in info:
	if r[0] == 1:
		q.append(r[1])

	elif (r[0] in q) and r[1] == n:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(m)]
info = sorted(info, key=lambda x: x[0])

q = []
for r in info:
	if r[0] == 1:
		q.append(r[1])
		continue

	elif (r[0] in q) and r[1] == n:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(m)]
info = sorted(info, key=lambda x: x[0])

queue = []
for regular in info:
	if regular[0] == 1:
		queue.append(regular[1])

	elif (regular[0] in queue) and regular[1] == n:
		print("POSSIBLE")
		break
else:
	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())

first = []
second = []
for i in range(m):
    if a[i] == 1:
        first.append(b[i])

    if b[i] == n:
        second.append(a[i])
ans = 'IMPOSSIBLE'
for i in first:
    if i in second:
        ans = 'POSSIBLE'
print(ans)

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())

first = []
for i in range(m):
    if a[i] == 1:
        first.append(b[i])
second = []
ans = 'IMPOSSIBLE'
for i in range(m):
    if a[i] in first:
        second.append(b[i])

for i in second:
    if i == n:
        ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1.append(b)
    elif b == N:
        to_N.append(a)
        
from_1.sort()
to_N.sort()
flg = 0

for i in range(len(from_1)):
    if from_1[i] in to_N:
        flg = 1
        break
        
if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


v = Dijkstra(n)
for _ in range(m):
    a, b = map(int, input().split())
    v.addEdge(a-1, b-1, 1)
    v.addEdge(b-1, a-1, 1)

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if self.dist[v] < cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


v = Dijkstra(n)
for _ in range(m):
    a, b = map(int, input().split())
    v.addEdge(a-1, b-1, 1)
    v.addEdge(b-1, a-1, 1)

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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


INF = 10**9


def BellmanFord(edges, num_v, source):
      # グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source-1] = 0

    # 辺の緩和
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
                if i == num_v-1:
                    return -1

    return dist


edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a-1, b-1, 1))
    edges.append((b-1, a-1, 1))


if BellmanFord(edges, n, 0)[-2] < 3:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
TO = set([])
FM = set([])
ans = 'IMPOSSIBLE'
for i in range(M):
    f,t = map(int, input().split())
    if f == 1:
        TO.add(t)
    elif t == N:
        FM.add(f)
#    print(TO,FM,TO & FM)
    if len(TO & FM)>0:
      ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ans = "IMPOSSIBLE"
f = []
s = []
for i in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    if a == 0:
        f.append(b)
    if b == N-1:
        s.append(a)
if len(f) > len(s):
    for i in range(len(s)):
        if s[i] in f:
            ans = "POSSIBLE"
            break
else:
    for i in range(len(f)):
        if f[i] in s:
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
li = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    li[a][b] = 1
    li[b][a] = 1

ans = False
for i in range(1,n-1):
    if li[0][i] and li[i][n-1]:
        ans = True
        break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    if  a == 1 or b== N:
        AB.append((a,b))
AB = set(AB)
for ab in AB:
    if ab[0] == 1:
        for  cd in AB:
            if cd[1] == N and ab[1] == cd[0]:
                    print("POSSIBLE")
                    exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    if  a == 1 or b== N:
        AB.append([a,b])
AB.sort()
for ab in AB:
    if ab[0] == 1:
        for  cd in AB:
            if cd[1] == N and ab[1] == cd[0]:
                    print("POSSIBLE")
                    exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import copy
from operator import itemgetter
N, M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
mid = []
AB.sort()
CD = copy.deepcopy(AB)
CD = sorted(CD, key=itemgetter(1,0),reverse = True)
for ab in AB:
    if ab[0] == 1:
        for  cd in CD:
            if cd[1] == N:
                if ab[1] == cd[0]:
                    print("POSSIBLE")
                    exit()
            else:
                break
    else:
        break
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
mid = []
AB.sort()
for ab in AB:
    if ab[0] == 1:
        for  cd in AB:
            if ab[1] == cd[0] and cd[1] == N:
                print("POSSIBLE")
                exit()
    else:
        break
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
mid = []
AB.sort()
for ab in AB:
    if ab[0] == 1:
        for  cd in AB:
            if ab[1] == cd[0] and cd[1] == N:
                print("POSSIBLE")
                exit()
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 = []
d = []
ans = "IMPOSSIBLE"
for i in range(M):
    if ab[i][0] == 1:
        c.append(ab[i][1])
    elif ab[i][1] == N:
        d.append(ab[i][0])
for i in range(len(c)):
    if c[i] in d:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=[] #最初の候補地

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    if b[i] not in c:
      c.append(b[i])
    
for j in range(M):
  if a[j]!=1:
    if a[j] in c:
      if b[j]==N:
        print("POSSIBLE")
        break
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=[] #最初の候補地

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(m)]
    S=[]
    for l in L:
        if l[0]==1: S.append(l[1])
    for l in L:
        if l[0] in S and l[1]==n:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
main()

Submission status: Time Limit Exceeded

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

ship_list1 = []
ship_list2 = []
count = 0
loop = False

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i])
    if ab[i][1] == n:
        ship_list2.append(ab[i])

for ship1 in ship_list1:
    for ship2 in ship_list2:
        if ship1[1] == ship2[0]:
            print('POSSIBLE')
            count += 1
            loop = True
            break
    if loop:
        break

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

Submission status: Time Limit Exceeded

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

ship_list1 = []
ship_list2 = []
count = 0

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i])
    if ab[i][1] == n:
        ship_list2.append(ab[i])

for ship1 in ship_list1:
    for ship2 in ship_list2:
        if ship1[1] == ship2[0]:
            print('POSSIBLE')
            count += 1
            break
        else:
            continue

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

Submission status: Time Limit Exceeded

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

ship = []
count = 0

for i in range(m):
    if count != 0:
        break
    if ab[i][1] == n:
        for j in range(m):
            if i == j:
                continue
            elif ab[i][0] == ab[j][1] and ab[j][0] == 1:
                print('POSSIBLE')
                count += 1
                break
            else:
                continue

if count == 0:
    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())

ans = 'IMPOSSIBLE'
for i in range(M):
    if(A[i] == 1):
        for j in range(M):
            if(B[i] == A[j] and B[j] == N):
                ans = 'POSSIBLE'
                break

print(ans)

Submission status: Time Limit Exceeded

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

ship = []
count = 0

for i in range(m):
    if ab[i][1] == n:
        ship.append(ab[i])

for j in range(len(ship)):
    for i in range(m):
        if ab[i][1] == ship[j][0] and ab[i][0] == 1:
            print('POSSIBLE')
            count += 1
            break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
x = deque()
y = deque()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        x.append(b)
    elif 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())

start = []
goal = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
    
for i in range(len(start)):
    if start[i] in goal:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:


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

es = [[] for _ in range(N+1)]

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


for i in range(2,N):
    if i in es[1] and N in es[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for _ in range(m):
    s, e = map(int, input().split())

    if s == 1:
        start_list.append(e)
    if e == n:
        end_list.append(s)

possible = False
for i in end_list:
    if i in start_list:
        possible = True
        break        

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
K=[]
A=[]
B=[]
answer='IMPOSSIBLE'
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    A +=[b]
  if b==N:
    B += [a]
for x in B:
  if x in A:
    answer='POSSIBLE'
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
K=[]
A=[]
B=[]
answer='IMPOSSIBLE'
for i in range(M):
  a,b=map(int,input().split())
  A +=[a]
  B += [b]
  if a==1 and b==N:
    answer='POSSIBLE'
  if a==1:
    K +=[b]
for i in range(M):
  if A[i] in K and B[i]==N:
    answer='POSSIBLE'
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
b = []
ans = ""
for i in range(m):
    tmp1,tmp2 = map(int,input().split())
    a.append(tmp1)
    b.append(tmp2)

xton = []
#nへ向かう便が出てる島を確認する
for i in range(m):
    if b[i] == n:
        xton.append(a[i])
#nへ向かう便が出ている島へ1から向かう便があるか確認する
for i in range(m):
    if a[i] == 1 and b[i] in xton:
        ans = "POSSIBLE"
        break
    else:
        ans = "IMPOSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
x=[]
f=0
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        if b in x:
            print("POSSIBLE")
            break
        x.append(b)
    if b==n:
        if a in x:
            print("POSSIBLE")
            break
        x.append(a)
else:
    print("IMPOSSIBLE")

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)

for i in x:
    if i in y:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M = map(int,sys.stdin.readline().split())
ab = []
start = []
goal = []
for i in range(M):
    ab.append(list(map(int,sys.stdin.readline().split())))
for i in ab:
    if i[0] == 1:
        start.append(i[1])
    if i[1] == N:
        goal.append(i[0])
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:
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:
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 start:
    if i in goal:
        ans = 'POSSIBLE'
        break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = []
s_N = []
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        if i[1] in s_N:
            print("POSSIBLE")
            sys.exit()
        s_1.append(i[1])
    if i[1] == N:
        if i[0] in s_1:
            print("POSSIBLE")
            sys.exit()
        s_N.append(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = []
s_N = []
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        s_1.append(i[1])
    if i[1] == N:
        s_N.append(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:


from collections import defaultdict

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


for i in range(2,N):

    if i in es[1] and N in es[i]:
        print("POSSIBLE")
        exit()


print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append((a,b))
#print(ab)
     
mid=[]
for (i,j) in ab:
  if i==1:
    mid.append(j)

for (i,j) in ab:
  if i in mid and j==n:
    print("POSSIBLE");exit()
    
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal2 = []
goal1 = []
for i in range(M):
    if A[i][1] == N:
        goal2.append(A[i][0])
    elif A[i][0] == 1:
        goal1.append(A[i][1])
    else:
        pass

for k in range(len(goal1)):
    if goal1[k] in goal2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal2 = []
goal1 = []
for i in range(M):
    if A[i][1] == N:
        goal2.append(A[i][0])
    else:
        pass

for j in range(M):
    if A[j][0] == 1:
        goal1.append(A[j][1])
    else:
        pass


for k in range(len(goal1)):
    if goal1[k] in goal2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal = []
for i in range(M):
    if A[i][1] == N:
        goal.append(A[i][0])
    else:
        pass

for i in range(len(goal)):
    for j in range(M):
        if A[j][1] == goal[i]:
            if A[j][0] == 1:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

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


def dfs(t, c, used):
    if c != 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        if g in used:
            continue
        next_used = used[:]
        next_used.append(g)
        flag = dfs(g, c - 1, next_used)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2, [x]):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

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


def dfs(t, c, used):
    if c != 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        if g in used:
            continue
        next_used = used[:]
        next_used.append(g)
        flag = dfs(g, c - 1, next_used)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2, []):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

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


def dfs(t, c):
    if c != 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        flag = dfs(g, c - 1)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
foo=[]
bar=[]
judge=0
a=[list(map(int,input().split()))for i in range(m)]
for j in a:
    if j[0]==1:
        foo.append(j[1])
    if j[1]==n:
        bar.append(j[0])
for k in foo:
    if k in bar:
        judge=1
        break
if judge==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
foo=[]
bar=[]
judge=0
a=[list(map(int,input().split()))for i in range(m)]
for j in range(m):
    if a[j][0]==1:
        foo.append(a[j][1])
    if a[j][1]==n:
        bar.append(a[j][0])
for k in range(len(foo)):
    for l in range(len(bar)):
        if foo[k]==bar[l]:
            judge=1
            break
    else:
        continue
    break
if judge==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]

a = sorted(a,key = lambda x:-x[1])

#print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] < n:
        break
    else:
        c.append(a[i][0])

a = sorted(a,key = lambda x:x[0])
for i in range(m):
    if a[i][0] > 1:
        break
    if a[i][1] in c:
            print("POSSIBLE")
            sys.exit()
        
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]

#print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] == n:
        c.append(a[i][0])
for i in range(m):
    if a[i][0]==1:
        if a[i][1] in c:
            print("POSSIBLE")
            sys.exit()
        
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# N: 島の数
# M: 定期便のルート
N, M = input().split()

a = []
b = []
# 船のルートを記録
for m in range(int(M)):
    _a, _b = input().split()
    a.append(_a)
    b.append(_b)


for i in [i for i, x in enumerate(a) if x == '1']:
    for l in [i for i, x in enumerate(b) if x == N]:
        if a[l] == b[i] and b[l] == N:
            print("POSSIBLE")
            sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# N: 島の数
# M: 定期便のルート
N, M = map(int, input().split())

a = {}
b = {}
# 船のルートを記録
for m in range(M):
    a[m], b[m] = map(int, input().split())


for i in range(M):
    if a[i] == 1:
        for l in range(M):
            if a[l] != b[i]:
                continue
            else:
                if b[l] == N:
                    print("POSSIBLE")
                    sys.exit()
    else:
        continue

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# N: 島の数
# M: 定期便のルート
N, M = map(int, input().split())

a = {}
b = {}
# 船のルートを記録
for m in range(M):
    a[m], b[m] = map(int, input().split())


for i in range(M):
    if a[i] == 1:
        for l in range(M):
            if a[l] == b[i] and b[l] == N:
                print("POSSIBLE")
                sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dic = {}
for i in range(m):
  a,b = map(int,input().split())
  if a not in dic:
    dic[a]=[b]    
  else:    
    if b not in dic[a]:
      dic[a].append(b)      
      
  if b not in dic:
    dic[b]=[a]
    if a not in dic[b]:
      dic[b].append(a)
      
ans = 'IMPOSSIBLE'
for i in dic[1]:   
  if n in dic[i]:
    ans = 'POSSIBLE'
    break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dic = {}
for i in range(m):
  a,b = map(int,input().split())
  if a not in dic:
    dic[a]=[b]    
  else:    
    if b not in dic[a]:
      dic[a].append(b)      
      
  if b not in dic:
    dic[b]=[a]
    if a not in dic[b]:
      dic[b].append(a)
      
islands = set()
for i in dic[1]:
  islands.add(i)
  for j in dic[i]:
    islands.add(j)
    
if n in islands:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

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

inf = 10**10

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[inf for i in range(n)] for i in range(n)] 

for i in range(m):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    d[x-1][y-1] = 1
    d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0

li = warshall_floyd(d)

if li[0][n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

li.sort()

mi = []
ma = []

for i in li:
    if i[0] == 1:
        mi.append(i[1])
    if i[1] == n:
        ma.append(i[0])

for s in mi:
    for k in ma:
        if s == k:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
li.sort()

lin = []

for i in li:
    if i[1] == n:
        lin.append(i[0])
for j in li:
    for k in lin:
        if j == [1,k]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = []

for i in li:
    if i[1] == n:
        lin.append(i[0])
for j in lin:
    if [1,j] in li:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")